优化算法

优化算法概论

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

• 数值解 {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

则有 $$ 所以下降方向就是负梯度方向

关于步长的三个约束条件

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)

• 充分条件

$$

Glodstein Condition

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

$$

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

$$

第二个式子中∇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）可得 $$ 代入（3）（注意到α_k∇f_k^Tp_k < 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收敛速度

次线性收敛

$$

线性收敛

$$

超线性收敛

$$

二次收敛

$$

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

• k充分大

例子
$$ 是Q次线性
2^−k是Q线性
2^2−k是二次线性

梯度下降法

关于凸函数性质的理解

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

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

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

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

$$

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

$$ 左边等于  = ∫₀¹g^′(θ)dθ − ∫₀¹∇f(x)^T(y − x)dθ

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

$$

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

$$

证毕

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

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

回到算法本身

x的更新公式为 x_k + 1 = x_k − α_k∇f(x_k) 根据二次上界不等式可得 $$

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

由于$$,则

$$

$$

进一步有 $$ $$

由于f_k单调下降，因此 $$ 算法使得以$$收敛到f^*

重要的引理:白老爹定理

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

• f有下界，m-强凸，可微
• ∇f李普希兹连续
• $$

则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^*)寻找一个合适的下界

带入原始的式子

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