1. 梯度下降算法

2. 二阶近似下的梯度下降算法

3. 引入非光滑约束后的近端梯度下降

4. 三个近端梯度下降计算非光滑约束优化的例子

一、梯度下降

 考虑min_xf(x)，其中f(x)为可微凸函数，且其梯度▽f(x)满足L-Lipschitz条件.最简单的优化方法为梯度下降法(Gradient descent)：

x^(k+1)=x^(k)-η▽f(x^(k))

将f(x)在x=x^(k+1)的值，在x^(k)处做泰勒展开，得到：

f(x^(k+1))=f(x^(k))+▽f(x^(k))(x^(k+1)-x^(k))

=f(x^(k))-η(▽f(x^(k)))²

≤f(x^(k))                     

二、梯度▽f(x^(k))满足L-Lipschitz条件下的梯度下降

首先给出L-Lipschitz定义：

设函数f(x)在有限区间[a,b]上满足如下条件：

• 当x∈[a,b]时，f(x)∈[a,b]，即a≤f(x)≤b;
• 对于任意的x₁, x₂∈[a,b]，|f(x₁)-f(x₂)|≤L|x₁-x₂|恒成立

则称f(x)在[a,b]上满足L-Lipschitz条件，L称为L-Lipschitz常数。

可以发现，L-Lipschitz连续比一致连续更强，要求函数值在有限区间的变化幅度受到限制.

进一步的，如果函数f(x)的梯度▽f(x)满足L-Lipschitz连续，则其在给定点x^(k)可以展开成如下二阶近似形式

展开，并将与x无关的项记为ϕ(x^(k))，则可以进一步化简为

由图可知

因此，在二阶近似的条件下，梯度下降可以理解为：每一次迭代都在最小化目标函数在上一次迭代点处的二次上界.

收敛速度为：O(1/k)

三、引入非光滑约束后的近端梯度下降算法

考虑min_xf^s(x)+fⁿ(x)，其中f^s(x)为可微凸函数，且其梯度▽f^s(x)满足L-Lipschitz条件，fⁿ(x)为非光滑函数，对光滑部分做如上二阶近似，得到

令则可以得到近端梯度下降的更新公式:

而该更新公式可以通过如下近端问题高效求解：

即最小化μfⁿ(x)加上一个独立的二次问题，此时的收敛速率仍为O(1/k)。

四、三个近端梯度下降计算非光滑约束优化的例子

例1.

例2.

例3.

转自：https://blog.csdn.net/qq_38290475/article/details/81052206