凸优化算法原理及讲解

问题描述

精选答案

凸优化算法是最优化问题中非常重要的一类，也是被研究的很透彻的一类。

对于机器学习来说，如果要优化的问题被证明是凸优化问题，则说明此问题可以被比较好的解决。

求解一个一般性的最优化问题的全局极小值是非常困难的，至少要面临的问题是：函数可能有多个局部极值点，另外还有鞍点问题。

对于第一个问题，我们找到了一个梯度为0的点，它是极值点，但不是全局极值，如果一个问题有多个局部极值，则我们要把所有局部极值找出来，然后比较，得到全局极值，这非常困难，而且计算成本相当高。

第二个问题更严重，我们找到了梯度为0的点，但它连局部极值都不是，典型的是这个函数，在0点处，它的导数等于0，但这根本不是极值点：

梯度下降法和牛顿法等基于导数作为判据的优化算法，找到的都导数/梯度为0的点，而梯度等于0只是取得极值的必要条件而不是充分条件。

如果我们将这个必要条件变成充分条件，即：问题将会得到简化。

如果对问题加以限定，是可以保证上面这个条件成立的。

其中的一种限制方案是：

对于目标函数，我们限定是凸函数；对于优化变量的可行域（注意，还要包括目标函数定义域的约束），我们限定它是凸集。

同时满足这两个限制条件的最优化问题称为凸优化问题，这类问题有一个非常好性质，那就是局部最优解一定是全局最优解。

其他回答

工程军事

凸优化方法是数学优化方法中具有代表性的一种，凸优化被广泛运用在图像处理，自动控制系统，估计和信号处理，通信网络，数据挖掘，电路设计等很多方面，特别是在现在的人工智能时代，机器学习和深度学习具有很高的热度和应用价值，从某种意义上讲，凸优化也可看做是机器学习中的一部分。