一、梯度下降法
梯度下降法
考虑无约束优化问题：
其中， 为可微凸函数，且
。
记：
梯度下降法迭代格式为：
其中， 为搜索步长，
为初始迭代点。
梯度下降法解释
梯度下降法每步迭代中，考虑二次近似函数:
上式中前两项可视为目标函数的线性近似，最后一项则是临近二次项。极小化以上函数可得 ：
二、次梯度法
- 可微凸函数最优性条件：
- 可推广至次梯度情形。
我的理解是：上面的大于等于号应该只有在在
的边界时候取到[意思是在该点，不管向着那个方向走，函数值都是增加的]。倘若
定理：凸函数极小值点与次梯度的关系
为凸函数
在凸集
的极小点的充要条件为：存在一个次梯度
满足：
Theorem (投影算子非扩张性质)
设 为非空闭凸集，
为投影算子，以下结论成立：
Theorem (次梯度相邻迭代点距离不等式)
设 为次梯度方法产生的点列，有以下结论成立：
‘1. 对所有的 以及
，有：
- 若
，且
，有：
证明：(1) 由投影算子非扩张性质，对所有 与
，
三、临近点算法
Proximal算法基本原理
考虑极小化闭凸函数 ，Proximal算法迭代格式为:
其中： 为第
步迭代点；
为正则化参数(>0)。(去约束、去不可微性、强凸化)。
注意：
- 正则化程度主要由参数
控制；
- 下一迭代点
尽可能要靠近前一个迭代点
；
- 二次项
使得目标函数在一个紧水平集上极小化强凸函数。
容易验证：从非最优点 出发，目标函数值是递减的，即：
四、增广拉格朗日算法
考虑约束优化问题：
其中： 是凸函数，
是凸集，
。
MC/MC对偶框架下，原问题与：
对偶问题函数为：
五、ADMM算法
ADMM算法迭代格式:
-
关于
:
-
关于
极小化
-
拉格朗日乘子更新:
六、近似点梯度算法
邻近算子
邻近算子是处理非光滑问题的一个非常有效的工具，也与许多算法设计密切联系。首先介绍邻近算子的定义。
定义：（邻近算子）对于一个凸函数 ，定义它的邻近算子为：
可以看到，邻近算子的目的是求解一个距离 不太远的点，使得
函数值也相对较小。
几个临近算子的例子
- 下面例子中
均为正实数。
-
范数:
-
范数:
- 二次函数:
-
近似点梯度算法的思想和迭代形式
近似点梯度法的思想非常简单：针对 中的两部分
（光滑部分）与
（非光滑部分）分别做梯度下降与邻近算子，则近似点梯度算法的迭代公式为：
其中： 为第
步迭代的步长，可以是常数或者用某种线性搜索方法计算得出。
-
当
时，近似点梯度算法变为梯度下降算法：
当
时，迭代公式变为投影梯度法。
七、Nesterov加速算法
通常梯度下降算法在极小化凸目标函数的收敛率为 . Nesterov在1983提出了针对光滑目标函数的改进的一阶算法，收敛速度能够达到
. 相较于牛顿算法，Nesterov加速算法更加适合数据量大的优化问题类型。
以梯度下降法为例，对 进行一步梯度迭代得到辅助点
，即：
将相邻两步迭代的辅助点 与
加权得到下一个迭代点
。
迭代格式为：
这里：。
