凸优化求解方法

首页摘要：

在推导出KKT条件后，如何利用它对不同的凸优化模型求解是本篇文章的主要介绍内容，本文从无约束优化、等式约束优化、不等式约束优化三个凸优化模型来进行介绍。

无约束优化问题

无约束优化问题求解思路非常简单，一般是对目标函数进行梯度计算的方法进行寻优，各类寻优的方法不同之处在于确定梯度方向和大小。

现在考虑无约束优化问题：

$$minimize\ \ f(x)$$

其最优解$x^{\star}$一定满足：

$$\nabla f(x^{\star})=0$$

也就是说，只要求解这个具有$n$个变量$x=\{x_{1},x_{2},…,x_{n}\}$的等式方程组就可以得到最优解，然而，这个方程组一般没有解析解，需要进行数值迭代寻优求解，不论何种寻优方法，其最后迭代（第$k$次迭代）均满足：

$$|f(x^{k})-f(x^{\star})|<\epsilon$$

其中，$\epsilon $为足够小的数。

总体而言，所有的寻优方法均遵从下述寻优框架：

给定初始点$x^{0}\in D$

重复进行

     1.确定下降方向 $\Delta x^{k}$，但是必须满足$\nabla f(x^{k})\Delta x^{k}<0$

      2.直线搜索。选择步长$t>0$

      3.修改。$x^{k+1}=x^{k}+\Delta x^{k}$

直至满足$|f(x^{k+1})-f(x^{k})|<\epsilon $

不同寻优方法核心在于确定$\Delta x$和$t$，具体如下：

• 梯度下降方法（线性收敛）

  $\Delta x=-\nabla f(x)$

• 最速下降方法（线性收敛）

  $\Delta x=argmin\{(\nabla f(x))^{T}v|\left|v\right|=1\}$

• Newton方法（二次收敛）

  $\Delta x=-\nabla^{2} f(x)^{-1}\nabla f(x)$

等式约束优化问题

等式约束问题主流方法是通过KKT条件确定Newton方法的梯度，这样就能得到满足等式约束的梯度，进一步利用Newton方法进行迭代寻优即可。

等式约束优化问题标准形式为：

$$\begin{matrix} minimize & f(x) \hfill \\ subject\ to & Ax=b\\ \end{matrix}$$

因为这是凸优化问题，必须满足$rank\ A=p<n$ 。代入KKT条件，此优化问题的最优解$x^{\star}$满足：

$$\begin{matrix} Ax^{\star}=b \\ \nabla f(x^{\star})+A^{T}v^{\star}=0 \end{matrix}$$

其中，$v^{\star}$为对偶解。这个方程组同样难以通过解析解求解，我们需要寻求迭代求解的方法来获得最优解。常用的方法就是Newton方法。为了求得Newton方法的梯度方向$\Delta x$ ，我们对等式约束问题在$x$附近进行二次泰勒展开，即：

$$\begin{matrix} minimize & f(x+\Delta x)= f(x)+\nabla f(x)\Delta x+\frac{1}{2}\Delta x^{T}\nabla^{2} f(x)\Delta x \hfill \\ subject\ to & A(x+\Delta x)=b \hfill\\ \end{matrix}$$

根据等式约束并将目标函数代入KKT条件对$\Delta x$求导（因为要求$\Delta x$）得到：

$$\begin{matrix}\nabla f(x)+\nabla^{2} f(x)\Delta x+A^{T}v=0 \\ A\Delta x=0\end{matrix}$$

转化成矩阵形式：

$$\begin{bmatrix} \nabla^{2} f(x)&A^{T} \\ A& 0 \end{bmatrix} \begin{bmatrix} \Delta x \\ v \end{bmatrix} =\begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

求解方程组即可得到Newton方法的梯度方向$\Delta x$ ，代入Newton迭代寻优方法即可求得最优解，算法如下：

给定满足$Ax^{0}=0$的初始点$x^{0}\in D$

重复进行

     1.根据前述方法计算下降方向 $\Delta x^{k}$

      2.直线搜索。选择步长$t>0$

      3.修改。$x^{k+1}=x^{k}+\Delta x^{k}$

直至满足$|f(x^{k+1})-f(x^{k})|<\epsilon $

不等式约束优化问题

对于不等式约束优化问题，我们很自然会想将其转化为等式约束优化问题，关键在于如何转化。

不等式约束优化问题标准形式为：

$$\begin{matrix} minimize & f(x) \hfill \\ subject\ to & Ax=b,i=1,2,...m\\ & g_{j}(x)\leq 0,j=1,2,...p\\ \end{matrix}$$

要求其最优解$x^{\star}$可以根据KKT条件得到：

$$\left\{\begin{matrix} & Ax^{\star}=b,i=1,2,...m \hfill& \\ & g_{j}(x^{\star})\leq 0,j=1,2,...p \hfill& \\ & \lambda^{\star} _{j} \geq 0,j=1,2,...p \hfill& \\ & \nabla f(x^{\star})+\sum_{j=1}^{p}\lambda^{\star} _{j}\nabla g_{j}(x^{\star})+ A^{T}v^{\star}=0\hfill & \\ & \sum_{j=1}^{p}\lambda^{\star} _{j}g_{j}(x^{\star})=0 \hfill& \end{matrix}\right.$$

同样地，这个方程组也无法通过解析解求解，而关键方法就是讲不等式优化问题转化为等式优化问题，核心在于对目标函数进行变化，使得其可以将解满足不等式约束。主流方法就是利用障碍法，也称之为内点法。转换得到的模型为：

$$\begin{matrix} minimize & f(x)+\sum_{j=1}^{p}-(1/t)log(-g_{i}(x))\hfill \\ subject\ to & Ax=b,i=1,2,...m \hfill\\ \end{matrix}$$

$-(1/t)log(-g_{i}(x))$可以很好地逼近不等式约束$g_{j}(x)\leq 0$ ，一旦$g_{j}(x)> 0$ 或者$g_{j}(x)\rightarrow 0$ ，上式目标函数会趋于无穷大，这也是障碍法或者内点法的由来，它保证解在可行域内。上式模型可以利用第二节等式约束优化模型的求解思路来进行。当然具体算法不一样，在这就不赘言。

结语

至此，凸优化的主要问题已经介绍完了，在应用的时候，我们往往需要根据实际情况将模型松弛或者简化至经典的凸优化模型，这些内容有缘再见！