soarli

凸优化问题求解方法
阅读本文不推荐开启博客夜间模式!摘要:在推导出KKT条件后,如何利用它对不同的凸优化模型求解是本篇文章的主要介绍内...
扫描右侧二维码阅读全文
18
2021/05

凸优化问题求解方法

阅读本文不推荐开启博客夜间模式!

摘要:

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

无约束优化问题

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

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

其最优解一定满足:

也就是说,只要求解这个具有个变量的等方程组就可以得到最优解,然而,这个方程组一般没有解析解,需要进行数值迭代寻优求解,不论何种寻优方法,其最后迭代(第次迭代)均满足:

其中,为足够小的数。

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

给定初始点
重复进行
1.确定下降方向 ,但是必须满足
2.直线搜索。选择步长
3.修改。
直至满足

不同寻优方法核心在于确定,具体如下:

  • 梯度下降方法(线性收敛)

  • 最速下降方法(线性收敛)

  • Newton方法(二次收敛)

等约束优化问题

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

等约束优化问题标准形为:

因为这是凸优化问题,必须满足 。代入KKT条件,此优化问题的最优解满足:

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

根据等约束并将目标函数代入KKT条件对求导(因为要求)得到:

转化成矩阵形:

求解方程组即可得到Newton方法的梯度方向 ,代入Newton迭代寻优方法即可求得最优解,算法如下:

给定满足的初始点
重复进行
1.根据前述方法计算下降方向
2.直线搜索。选择步长
3.修改。
直至满足

不等约束优化问题

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

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

要求其最优解可以根据KKT条件得到:

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

可以很好地逼近不等约束 ,一旦 ,上目标函数会趋于无穷大,这也是障碍法或者内点法的由来,它保证解在可行域内。上模型可以利用第二节等约束优化模型的求解思路来进行。当然具体算法不一样,在这就不赘言。

原文地址:
https://zhuanlan.zhihu.com/p/105313548

最后修改:2021 年 05 月 18 日 12 : 33 AM

发表评论