阅读本文不推荐开启博客夜间模式！
摘要：
在推导出KKT条件后，如何利用它对不同的凸优化模型求解是本篇文章的主要介绍内容，本文从无约束优化、等约束优化、不等约束优化三个凸优化模型来进行介绍。
无约束优化问题
无约束优化问题求解思路非常简单，一般是对目标函数进行梯度计算的方法进行寻优，各类寻优的方法不同之处在于确定梯度方向和大小。
现在考虑无约束优化问题：
其最优解一定满足：
也就是说，只要求解这个具有个变量
的等方程组就可以得到最优解，然而，这个方程组一般没有解析解，需要进行数值迭代寻优求解，不论何种寻优方法，其最后迭代（第
次迭代）均满足：
其中，为足够小的数。
总体而言，所有的寻优方法均遵从下述寻优框架：
给定初始点
重复进行
1.确定下降方向，但是必须满足
2.直线搜索。选择步长
3.修改。
直至满足
不同寻优方法核心在于确定和
，具体如下：
- 梯度下降方法（线性收敛）
- 最速下降方法（线性收敛）
- Newton方法（二次收敛）
等约束优化问题
等约束问题主流方法是通过KKT条件确定Newton方法的梯度，这样就能得到满足等约束的梯度，进一步利用Newton方法进行迭代寻优即可。
等约束优化问题标准形为：
因为这是凸优化问题，必须满足 。代入KKT条件，此优化问题的最优解
满足：
其中，为对偶解。这个方程组同样难以通过解析解求解，我们需要寻求迭代求解的方法来获得最优解。常用的方法就是Newton方法。为了求得Newton方法的梯度方向
，我们对等约束问题在
附近进行二次泰勒展开，即：
根据等约束并将目标函数代入KKT条件对求导（因为要求
）得到：
转化成矩阵形：
求解方程组即可得到Newton方法的梯度方向 ，代入Newton迭代寻优方法即可求得最优解，算法如下：
给定满足
的初始点
重复进行
1.根据前述方法计算下降方向
2.直线搜索。选择步长
3.修改。
直至满足
不等约束优化问题
对于不等约束优化问题，我们很自然会想将其转化为等约束优化问题，关键在于如何转化。
不等约束优化问题标准形为：
要求其最优解可以根据KKT条件得到：
同样地，这个方程组也无法通过解析解求解，而关键方法就是讲不等优化问题转化为等优化问题，核心在于对目标函数进行变化，使得其可以将解满足不等约束。主流方法就是利用障碍法，也称之为内点法。转换得到的模型为：
可以很好地逼近不等约束
，一旦
，上目标函数会趋于无穷大，这也是障碍法或者内点法的由来，它保证解在可行域内。上模型可以利用第二节等约束优化模型的求解思路来进行。当然具体算法不一样，在这就不赘言。
原文地址：
https://zhuanlan.zhihu.com/p/105313548
版权属于：soarli
本文链接：https://blog.soarli.top/archives/509.html
转载时须注明出处及本声明。
