凸优化学习-（二十四）无约束优化算法——梯度下降法

凸优化学习

梯度下降法是最经典、最简单的算法，要求目标函数一阶可微无约束，有$\textbf{m,M}$m,M控制凸性。

学习笔记

一、梯度下降法

形如：
$\begin{aligned} &&d^k&=-\nabla f(x^k)\\ \text{Repeat}&&d^k&=\arg\min f(x^k+\alpha d^k)\\ &&\alpha_{\max}&\ge\alpha\ge0\\ &&x^{k+1}&=x^k+\alpha^kd^k\\ \text{Until Convergence}&&& \end{aligned}$RepeatUntil Convergence​​dkdkαmax​xk+1​=−∇f(xk)=argminf(xk+αdk)≥α≥0=xk+αkdk​

二、收敛性分析

1.精确步长搜索（Exact line search）

有：
$\begin{aligned} &&f(x^{k+1})&\le f(x^k)+\nabla f^T(x^k)\big(-\alpha\nabla f(x^k)\big)+\frac {\textbf M}{2}\|-\alpha \nabla f(x^2)\|_2^2\\ \Leftrightarrow&&\tilde f(\alpha)&\le f(x^k)-\alpha\|\nabla f(x^k)\|_2^2+\frac{\textbf M\alpha^2}{2}\|\nabla f(x^k)\|_2^2\qquad①\\ \Rightarrow&&\min_\alpha\tilde f(\alpha)&\le f(x^k)-\frac 1{\textbf M}\|\nabla f(x^k)\|_2^2+\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2\\ \Rightarrow&&\min_\alpha\tilde f(\alpha)&\le f(x^k)-\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2\qquad ② \end{aligned}$⇔⇒⇒​​f(xk+1)f~​(α)αmin​f~​(α)αmin​f~​(α)​≤f(xk)+∇fT(xk)(−α∇f(xk))+2M​∥−α∇f(x2)∥22​≤f(xk)−α∥∇f(xk)∥22​+2Mα2​∥∇f(xk)∥22​①≤f(xk)−M1​∥∇f(xk)∥22​+2M1​∥∇f(xk)∥22​≤f(xk)−2M1​∥∇f(xk)∥22​②​
其中$\tilde f(\alpha)$f~​(α)指$f$f关于$\alpha$α的函数,$\min\tilde f(\alpha)$minf~​(α)就是指精确步长搜索（即按照求得的能使函数下降最大的步长下降）。②式也可以写成：
$f(x^{k+1})\le f(x^k)-\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2\qquad ②$f(xk+1)≤f(xk)−2M1​∥∇f(xk)∥22​②
②式表明在梯度下降法中，我们每执行一次迭代，我们就能获得一次函数值的下降，这个下降值至少为$\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2$2M1​∥∇f(xk)∥22​。
我们接下来研究每一次迭代后，我们离最优解有多远，由$\textbf{m,M}$m,M定义：
$\begin{aligned} &&p^*&\ge f(x^k)-\frac 1{2\textbf m}\|\nabla f(x^k)\|_2^2\qquad ③\\ ②-p^*:&&\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2+f(x^{k+1})-p^*&\le f(x^k)-p^*\qquad ④\\ ③-p^*:&&-\frac 1{2\textbf m}\|\nabla f(x^k)\|_2^2+f(x^{k})-p^*&\le 0\qquad ⑤\\ ④\cdot\textbf m+⑤\cdot\textbf M:&&\textbf M\big(f(x^{k+1})-p^*\big)+\textbf m\big(f(x^k)-p^*\big)&\le \textbf M \big(f(x^k)-p^*\big)\\ \Rightarrow&& f(x^{k+1})-p^*&\le (1-\frac {\textbf m}{\textbf M})\big(f(x^k)-p^*\big)\qquad ⑥\\ \Rightarrow&&\bigg\|\frac{f(x^{k+1})-p^*}{f(x^k)-p^*}\bigg\|&\le \bigg\|1-\frac {\textbf m}{\textbf M}\bigg\| \qquad ⑦ \end{aligned}$②−p∗:③−p∗:④⋅m+⑤⋅M:⇒⇒​​p∗2M1​∥∇f(xk)∥22​+f(xk+1)−p∗−2m1​∥∇f(xk)∥22​+f(xk)−p∗M(f(xk+1)−p∗)+m(f(xk)−p∗)f(xk+1)−p∗∥∥∥∥​f(xk)−p∗f(xk+1)−p∗​∥∥∥∥​​≥f(xk)−2m1​∥∇f(xk)∥22​③≤f(xk)−p∗④≤0⑤≤M(f(xk)−p∗)≤(1−Mm​)(f(xk)−p∗)⑥≤∥∥∥∥​1−Mm​∥∥∥∥​⑦​
这是什么意思呢，这说明我们每执行一次精准步长搜索的梯度下降，我的目标函数值一定是在下降的，并且我们可以由前一步的下降算出下降了多少。可以看到，梯度下降法在精确步长搜索时是线性收敛的：

2.模糊步长搜索（Inexact line search）(Amijo Rule)

Amijo Rule：
满足$f_0(x^k+\alpha d^k)\le f_0(x^k)+\gamma\alpha\nabla f_0^T(x^k)d^k$f0​(xk+αdk)≤f0​(xk)+γα∇f0T​(xk)dk时接受$\alpha$α，迭代停止。
Amijo Rule满足性质：
$当0\le\alpha\le\frac 1 {\textbf M}时，迭代必然停止。$当0≤α≤M1​时，迭代必然停止。
证明该性质：
当$0\le\alpha\le\frac 1 {\textbf M}$0≤α≤M1​时，必有:
$-\alpha+\frac{\textbf M\alpha^2}{2}\le -\frac \alpha 2\qquad ①$−α+2Mα2​≤−2α​①
根据定义有：
$\begin{aligned} \tilde f(\alpha)=&&f(x^{k+1})&\le f(x^k)-\alpha\|\nabla f(x^k)\|_2^2+\frac{\textbf M \alpha^2}{2}\qquad ②\\ 由①②得：&&&\le f(x^k)-\frac {\alpha} 2\|\nabla f(x^k)\|_2^2\\ 有\gamma\in[0,0.5]得：&&&\le f(x^k)-\gamma\alpha\|\nabla f(x^k)\|_2^2\qquad ③ \end{aligned}$f~​(α)=由①②得：有γ∈[0,0.5]得：​​f(xk+1)​≤f(xk)−α∥∇f(xk)∥22​+2Mα2​②≤f(xk)−2α​∥∇f(xk)∥22​≤f(xk)−γα∥∇f(xk)∥22​③​
③等价于接受$\alpha$α的不等式，所以此时迭代必然停止，证毕。

当不精确搜索在本次迭代后将停止时，我们本次的$\alpha\ge \frac 1 {\textbf M}$α≥M1​，得：
$\alpha_{\text{inexact}}=\alpha_{\max}或\ge \frac{\beta}{\textbf M}\quad \beta\in[0,1]$αinexact​=αmax​或≥Mβ​β∈[0,1]
对于精确步长有：
$f(x^{k+1})=\tilde f(\alpha_{\text{exact}})\le f(x^k)-\frac 1{2\textbf M}\|\nabla f(x^k)\|_2^2$f(xk+1)=f~​(αexact​)≤f(xk)−2M1​∥∇f(xk)∥22​
得模糊步长：
$f(x^{k+1})=\tilde f(\alpha_{\text{inexact}})\le f(x^k)-\gamma\min\bigg\lbrace\alpha_{\max},\frac {\beta}{\textbf M}\bigg\rbrace\|\nabla f(x^k)\|_2^2$f(xk+1)=f~​(αinexact​)≤f(xk)−γmin{αmax​,Mβ​}∥∇f(xk)∥22​
可得：
$\bigg\|\frac{f(x^{k+1})-p^*}{f(x^k)-p^*}\bigg\|\le \bigg\|1-\gamma\min\bigg\lbrace2\textbf m\alpha_{\max},\frac {2\textbf m\beta}{\textbf M}\bigg\rbrace\bigg\|$∥∥∥∥​f(xk)−p∗f(xk+1)−p∗​∥∥∥∥​≤∥∥∥∥​1−γmin{2mαmax​,M2mβ​}∥∥∥∥​
其中$\gamma\in[0,0.5],\beta\in[0,1]$γ∈[0,0.5],β∈[0,1]，这个比例比较接近于1，是线性收敛的。同时，当$\textbf{m,M}$m,M比较接近时，收敛比较快。

个人思考

梯度下降法作为应用最广、最简单的算法，用来入门是最好不过了。这里面的收敛性分析可以帮助我们了解在什么时候使用梯度下降法会收敛得比较快。梯度下降法也有它的一些局限性，在学习后面的算法中可以体会这一点。

纸质笔记