经典优化算法

优化算法概论

理想的优化算法有以下几个特点

• 数值解 {x_k}_k = 0^∞的迭代，实际中操作使用有限次，满足一定条件停止迭代即可
• 单调性，满足f(x_k + 1) < f(x_k − m)就很好，但是往往碰到螺旋下降的情况
• 策略 ：x_k如何到x_k + 1?

线搜索方法

x_k + 1 = x_k + α_kp_k

这里α_k是一个很小的正量表示步长，p_k表示方向，线搜索方法就是先定方向，再定步长

信赖域方法

x_k + 1 = x_k + p_k

方向和步长合二为一

线搜索方法理论

确定方向

假定 - {f(x_k)}_k = 0^∞是单调下降的
- α_k足够小
- ||p_k|| = 1

则有 $$ \begin{align*} f(x_{k+1}) &= f(x_k + \alpha_k p_k) \\ &= f(x_k) + \nabla f(x_k)^T \cdot \alpha_k p_k + o(\|\alpha_k p_k\|) \\ f(x_{k+1}) - f(x_k) &\approx \nabla f(x_k)^T \cdot \alpha_k p_k < 0 \\ \text{由于 } \alpha_k &> 0 \quad \text{因此} \\ \nabla f(x_k)^T \cdot p_k &< 0 \end{align*} $$ 所以下降方向就是负梯度方向

关于步长的三个约束条件

Armijo Condition

假定p_k是下降方向，我们令 ϕ(α) = f(x_k + 1) = f(x_k + αp_k)

于是

ϕ^′(α) = ∇f(x_k + αp_k)^Tp_k

ϕ(0) = f(x_k)

ϕ^′(0) = ∇f_k^Tp_k

我们想让a取到一个良好的位置，应当满足 - 必要条件(f序列单调减) ϕ(α) < ϕ(0)

• 充分条件

$$\phi(\alpha) \le f(x_k)+c_1\nabla f_k^Tp_k \alpha \\ c_1 \in (0,1) $$

Glodstein Condition

Glodstein发现Armijo条件总会导致筛选出特别小的a，但是这在数值计算中没有意义，为此他提出了新的筛选方法

$$f(x_k)+(1-c)\nabla f_k^Tp_k\alpha \le \phi(\alpha) \le f(x_k)+c\nabla f_k^Tp_k \alpha \\ c \in (0,\frac12) $$

wolfe condition

wolfe综合了上述思想，又考虑到Glodstein的约束条件过于狭窄，在c趋于0.5的时候几乎不留区间，于是最终演化出我们现在通用的筛选标准

ϕ(α) ≤ f(x_k) + C₁∇f_k^Tp_kα

∇f_k + 1^T ⋅ p_k ≥ C₂∇f_k^TP_k

$$C_{1}\in(0,1)\\C_{2}\in(C_{1},1)$$

第二个式子中∇f_k + 1^T就是函数图像中ϕ(a)在a处的斜率，这样就不冒进的排除掉了α靠近0的一小段区间

收敛性证明

记 x_k + 1 = x_k + α_kp_k ,我们有以下几点要求，

• ∇f(x)满足Lipschitz连续，即∥∇f(x) − ∇f(x̂)∥ ≤ L∥x − x̂∥,  ∀x, x̂ (1)

• p_k是下降方向，即∇f_k^Tp_k < 0 (2)

• α_k满足wolfe条件，即： f_k + 1 < f_k + c₁α_k∇f_k^Tp_k  (3)
  ∇f_k + 1^Tp_k ≥ c₂∇f_k^Tp_k  (4)

这几点要求对大多数优化问题来说都是比较容易满足的。在这样的已知条件下，我们可以推导出一个重要的结论:Zoutendijk条件

Proof

由(4) (∇f_k + 1 − ∇f_k)^Tp_k ≥ (c₂ − 1)(∇f_k^Tp_k)  (5) 又由李普希兹连续条件可得 ∥∇f_k + 1 − ∇f_k∥ ≤ α_kL∥p_k∥ ∥∇f_k + 1 − ∇f_k∥∥p_k∥ ≤ α_kL∥p_k∥² (∇f_k + 1 − ∇f_k)^Tp_k ≤ α_kL∥p_k∥²  (6)

联立（5）,（6）可得 $$\alpha_k\geq\frac{c_2-1}{L}\frac{\nabla f_k^Tp_k}{\left\|p_k\right\|^2}$$ 代入（3）（注意到α_k∇f_k^Tp_k < 0） $$f_{k+1}\leq f_k+c_1\frac{c_2-1}{L}\frac{\left(\nabla f_k^Tp_k\right)^2}{\left\|p_k\right\|^2}$$ $$f_k-f_{k+1}\geq c\cos^2\theta_k\|\nabla f_k\|^2 \quad c=c_1\frac{1-c_2}{L}>0$$ 两边累加可得 f₀ − f_k + 1 ≥ cΣ_j = 0^kcos²θ_j∥∇f_j∥² 因为f有下界，因此左边收敛，那么由数列和的收敛判断，必然有 lim_{k → ∞}cos²θ_k∥∇f_k∥² = 0

上面我们已经证明了在一定条件下，可以推导出Zoutendijk条件： lim_{k → ∞}cos²θ_k∥∇f_k∥² = 0 更进一步，如果能够证明 cos θ_k ≥ δ > 0, ∀k

那么显然要想仍然满足Zoutendijk条件，则只能要求lim_{k → ∞}∥∇f_k∥ = 0 ,从而证明了收敛性。对于最速下降方向p_k = −∇f_k,天然的cos θ_k = 1,则自然满足收敛性。

收敛速度

记x^*为局部的最优解 ### Q收敛速度

次线性收敛

$$\lim_{k\to\infty}\frac{\left\|x_{k+1}-x^{*}\right\|}{\left\|x_{k}-x^{*}\right\|}=1$$

线性收敛

$$\frac{\parallel x_{k+1}-x^{*}\parallel}{\parallel x_{k}-x^{*}\parallel}\leq a\in(0,1)$$

超线性收敛

$$\lim_{k\to\infty}\frac{\parallel x_{k+1}-x^{*}\parallel}{\parallel x_{k}-x^{*}\parallel}=0$$

二次收敛

$$\frac{\|x_{k+1}-x^{*}\|}{\|x_{k}-x^{*}\|^{2}}\leq a\in(0,+\infty)$$

R收敛速度（类似于比较收敛）

• k充分大

例子
$\{ \frac 1 k\}$ 是Q次线性
2^−k是Q线性
2^2−k是二次线性

梯度下降法

关于凸函数性质的理解

在数学上，我们应当有这样的直觉:

• 李普希兹连续保证了我们的研究函数有二次上界
• 强凸这一性质保证了研究函数大于了一个二次下界

proof:李普希兹连续->二次上界

命题:若f可微，∇fLipschitz连续，则f有二次上界：

$$ f(y) \le f(x)+\nabla f(x)^T(y-x)+\frac L2||y-x||^2 $$

证明: 记 g(θ) = f(x + θ(y − x))
原命题变为证明

$$g(1)-g(0)-\nabla f(x)^T(y-x) \le \frac L2||y-x||^2 $$ 左边等于  = ∫₀¹g^′(θ)dθ − ∫₀¹∇f(x)^T(y − x)dθ

 = ∫₀¹(∇f(x + θ(y − x))^T ⋅ (y − x) − ∇f(x)^T(y − x))dθ

$$=\int_{0}^{1}\left(\nabla f\left(x+\theta\left(y-x\right)\right)-\nabla f\left(x\right)\right)^{T}\cdot\left(y-x\right)d\theta .\\\leq\int_{0}^{1}\|\nabla f\left(x+\theta\left(y-x\right)\right)-\nabla f\left(x\right)\|\cdot\|y-x\|d\theta .$$

 ≤ ∫₀¹L||θ(y − x)||⋅||y − x||dθ

$$= \frac L2||y-x||^2 $$

证毕

凸函数:梯度下降法收敛性分析

先引入一种求解α最小上界的思路

回到算法本身

x的更新公式为 x_k + 1 = x_k − α_k∇f(x_k) 根据二次上界不等式可得 $$\begin{aligned} f_{k+1}& =f\left(x_k-\alpha\nabla f(x_k)\right) \\ &\leq f(x_k)-\alpha\|\nabla f(x_k)\|^2+\frac{L\alpha^2}2\|\nabla f(x_k)\|^2 \\ &=f(x_k)-\alpha\left(1-\frac{\alpha L}2\right)\|\nabla f(x_k)\|^2 \end{aligned}$$

由凸函数的性质可知:f^* > f(x_k) − ∇f(x_k)^⊤(x_k − x^*)

由于$\alpha\in\left(0,\frac1L\right)$,则

$$

$$

进一步有 $$f_{k+1}-f^*=\frac1{2\alpha}\left(\|x_k-x^*\|^2-\|x_{k+1}-x^*\|^2\right)$$ $$\begin{gathered} \sum_{k=0}^n(f_{k+1}-f^*) \leq\frac1{2\alpha}\big(\|x_0-x^*\|^2-\|x_{k+1}-x^*\|^2\big) \\ =\frac1{2\alpha}\|x_0-x^*\|^2 \end{gathered}$$

由于f_k单调下降，因此 $$f_{n+1}-f^*\leq\frac1{n+1}\sum_{k=0}^n(f_{k+1}-f^*)\leq\frac1{2(n+1)\alpha}\|x_0-x^*\|^2$$ 算法使得以$O(\frac 1k)$收敛到f^*

重要的引理:白老爹定理

强凸函数应用梯度下降法的收敛性分析

• f有下界，m-强凸，可微
• ∇f李普希兹连续
• $\alpha \in (0,\frac{2}{L+m})$

则x_kQ线性收敛到x^*

||x_k + 1 − x^*||² = ||x_k − α∇f(x_k) − x^*||²  = ∥x_k − x^*∥² − 2α∇f(x_k)^T(x_k − x^*) + α²∥∇f(x_k)∥²  = ||x_k − x^*||² − 2α(∇f(x_k) − ∇f(x^*))^T(x_k − x^*) + α²||∇f(x_k)||² 现在的任务就是为(∇f(x_k) − ∇f(x^*))^T(x_k − x^*)寻找一个合适的下界

带入原始的式子

梯度下降法的缺点:在病态条件下收敛过慢