凸优化

凸优化是指一种比较特殊的优化,是指求取最小值的目标函数为凸函数的一类优化问题。其中,目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数,等式约束函数为仿射函数,并且定义域为凸集的优化问题为约束优化问题。

凸优化之所以如此重要,是因为:

  • 其应用非常广泛,机器学习中很多优化问题都要通过凸优化来求解;
  • 在非凸优化中,凸优化同样起到重要的作用,很多非凸优化问题,可以转化为凸优化问题来解决;
  • 如上引用所述,凸优化问题可以看作是具有成熟求解方法的问题,而其他优化问题则未必。

标准优化问题

凸优化知识体系包括了1

  • 凸集,定义目标函数和约束函数的定义域。
  • 凸函数,定义优化相关函数的凸性限制。
  • 凸优化,中心内容的标准描述。
  • 凸优化问题求解,核心内容。相关算法,梯度下降法、牛顿法、内点法等。
  • 对偶问题,将一般优化问题转化为凸优化问题的有效手段,求解凸优化问题的有效方法。

最速下降法

【最优化】一文搞懂最速下降法

最速梯度下降法解决的问题是无约束优化问题,而所谓的无约束优化问题就是对目标函数的求解,没有任何的约束限制的优化问题。

牛顿法

【最优化】无约束优化方法-牛顿法

牛顿法思想: 用目标函数的二阶泰勒展开近似该目标函数,通过求解这个二次函数的极小值来求解凸优化的搜索方向。

牛顿法推导:凸优化(七)——牛顿法

我们可以看出,牛顿法和最速梯度的不同就是在于最速梯度下降法的迭代方向是梯度的负方向,迭代步长根据一维搜索得到。而牛顿法的迭代方向为上述推导的牛顿步径,迭代步长可以看为定值1。

牛顿法的优缺点:

  • 优点是:对于二次正定函数,迭代一次即可以得到最优解,对于非二次函数,若函数二次性较强或迭代点已经进入最优点的较小邻域,则收敛速度也很快。
  • 缺点:
    • 保证不了迭代方向是下降方向,这就是致命的!换句话说就是不一定迭代能够收敛,后面的阻尼牛顿法会解决这个问题,牛顿法就到此为止了。
    • 计算量相当复杂,除需计算梯度除外,还需要计算二阶偏导数矩阵和它的逆矩阵,计算量,存储量都很大,并且都以维数N的平方比增加,当N很大的时候,计算量的问题就更加突出。
0%
Title - Artist
0:00