目标

min ⁡ { f ( x ) : x ∈ R n } \min\{f(\boldsymbol{x}):\boldsymbol{x}\in \mathbb{R}^n \} min{f(x):x∈Rn}

下降方向

设$f:{\mathbb{R}}^n\to \mathbb{R}$是一个在${\mathbb{R}}^n$上连续可微的函数。
$0\ne \mathbf{d}\in {\mathbb{R}}^n$,如果
$$f^{\prime }(\mathbf{x};\mathbf{d})=\nabla f(\mathbf{x}{)}^T\mathbf{d}<0$$
那么称$\mathbf{d}$为一个下降方向

性质

设$f:{\mathbb{R}}^n\to \mathbb{R}$是一个在${\mathbb{R}}^n$上连续可微的函数。$\mathbf{x}\in {\mathbb{R}}^n$
如果$\mathbf{d}$是一个下降方向，那么$\exists ϵ>0$,使得$\forall t\in (0,ϵ]$,有
$$f(\mathbf{x}+t\mathbf{d})<f(\mathbf{x})$$
证明：
$$\underset{t\to 0^{+}}{\lim }\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}=f^{\prime }(\mathbf{x};\mathbf{d})<0$$
由保号性，$\exists ϵ>0$,使得$\forall t\in (0,ϵ]$,有
$$\frac{f(\mathbf{x}+t\mathbf{d})-f(\mathbf{x})}{t}<0$$
再根据$t>0$
有
$$f(\mathbf{x}+t\mathbf{d})<f(\mathbf{x})$$

Lipschitz连续

主要用到梯度是Lipschitz连续

假设$f$连续可微，如果
$$\Vert \nabla f(\mathbf{x})-\nabla f(\mathbf{y})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert ,\forall \mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$$
那么称他的梯度$\nabla f(\mathbf{x})$是Lipchitz连续的
$L$称为Lipschitz常数
显然$\tilde{L}\ge L$也满足条件，所以我们只关心满足条件的$L$中最小的

把梯度Lipschitz连续的函数的一类函数记为$C_L^{1,1}({\mathbb{R}}^n)$
如果不关心$L$具体是多少，有时候也记为$C_L^{1,1}$
比如$f(\mathbf{x})={\mathbf{a}}^T\mathbf{x}\in C_0^{1,1}$
$f(\mathbf{x})={\mathbf{x}}^{T}A\mathbf{x}+2{\mathbf{b}}^T\mathbf{x}+c\in C_{2\Vert A\Vert }^{1,1}$

定理

假设$f$二阶连续可微，那么下面两个命题等价
a)$f\in C_L^{1,1}$
b)$\forall \mathbf{x}\in {\mathbb{R}}^n,\Vert {\nabla }^{2}f(\mathbf{x})\Vert \le L$
证明：
$b)\Rightarrow a)$
$$\begin{array}{rl}\nabla f(\mathbf{y})& =\nabla f(\mathbf{x})+{\int }_0^1{\nabla }^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))(\mathbf{y}-\mathbf{x})\mathrm{d}\mathbf{x}\\ & =\nabla f(\mathbf{x})+({\int }_0^1{\nabla }^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))\mathrm{d}\mathbf{x})(\mathbf{y}-\mathbf{x})\end{array}$$
所以
$$\begin{array}{rl}\Vert \nabla f(\mathbf{y})-\nabla f(\mathbf{x})\Vert & =\Vert ({\int }_0^1{\nabla }^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))\mathrm{d}\mathbf{x})(\mathbf{y}-\mathbf{x})\Vert \\ & \le \Vert {\int }_0^1{\nabla }^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))\mathrm{d}\mathbf{x}\Vert \Vert \mathbf{y}-\mathbf{x}\Vert \\ & \le \left({\int }_0^1\Vert {\nabla }^{2}f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))\Vert \mathrm{d}\mathbf{x}\right)\Vert \mathbf{y}-\mathbf{x}\Vert \\ & \le L\Vert \mathbf{y}-\mathbf{x}\Vert \end{array}$$
$a)\Rightarrow b)$
$$\nabla f(\mathbf{x}+\alpha \mathbf{d})-\nabla f(\mathbf{x})={\int }_0^{\alpha }{\nabla }^{2}f(\mathbf{x}+t\mathbf{d})\mathbf{d}\mathrm{d}t$$
所以
$$\Vert \left({\int }_0^{\alpha }{\nabla }^{2}f(\mathbf{x}+t\mathbf{d})\mathrm{d}t\right)\mathbf{d}\Vert =\Vert \nabla f(\mathbf{x}+\alpha \mathbf{d})-\nabla f(\mathbf{x})\Vert \le \alpha L\Vert \mathbf{d}\Vert$$
两边同除$\alpha$,并令$\alpha \to 0^{+}$
$$\Vert {\nabla }^{2}f(\mathbf{x})\mathbf{d}\Vert \le L\Vert \mathbf{d}\Vert \Rightarrow \Vert {\nabla }^{2}f(\mathbf{x})\Vert \le L$$

下降法

有了上面的知识，其实我们的迭代就很明显了
$${\mathbf{x}}_{k+1}={\mathbf{x}}_k+t_k{\mathbf{d}}_k,k=0,1,\cdots$$
下降法的整体框架就是
1.选择初始点${\mathbf{x}}_0\in {\mathbb{R}}^n$
2. 循环$k=0,1,\cdots$
a)选择下降方向${\mathbf{d}}_k$
b)挑选步长$t_k$,使得$f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)<f({\mathbf{x}}_k)$
c)迭代${\mathbf{x}}_{k+1}={\mathbf{x}}_k+t_k{\mathbf{d}}_k$
d)如果满足停止条件就停止，并返回${\mathbf{x}}_{k+1}$

那么问题来了，

• 怎么选起始点
• 怎么选下降方向
• 怎么选步长
• 停止条件是什么

因为最小值点，起码得是一个驻点，所以停止条件经常就是$\Vert f(x)\Vert \le ϵ$
所以终点看步长和下降方向

步长

固定步长

就是$\forall k,t_k=\tilde{t}$

精确线搜索算法

$$t_k=\arg \underset{t\ge 0}{\min }f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)$$

非精确线搜索算法

对于非精确线搜索，就是步长需要满足一些条件。

Armijo准则

$$f({\mathbf{x}}_k)-f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)\ge -\alpha t_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$$
其中$\alpha \in (0,1)$

如果$t$足够小，这个准则总是能满足的
大概下面这个图这种感觉

存在性证明

设$f:{\mathbb{R}}^n\to \mathbb{R}$是一个在${\mathbb{R}}^n$上连续可微的函数。$\mathbf{x}\in {\mathbb{R}}^n$
设$0\ne \mathbf{d}\in {\mathbb{R}}^n$是一个下降方向,$\alpha \in (0,1)$
那么$\exists ϵ>0,\forall t\in [0,ϵ]$，有
$$f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})\ge -\alpha t\nabla f(\mathbf{x}{)}^T\mathbf{d}$$

证明：
$$\begin{array}{rl}f(\mathbf{x}+t\mathbf{d})& =f(\mathbf{x})+t\nabla f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert )\\ f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})& =-\alpha t\nabla f(\mathbf{x}{)}^T\mathbf{d}-(1-\alpha )\nabla f(\mathbf{x}{)}^T\mathbf{d}-o(t\Vert \mathbf{d}\Vert )\end{array}$$
$$\underset{t\to 0^{+}}{\lim }\frac{(1-\alpha )t\nabla f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert )}{t}=(1-\alpha )\nabla f(\mathbf{x}{)}^T\mathbf{d}<0$$
因此$\exists ϵ>0,\forall t\in (0,ϵ]$
$$(1-\alpha )\nabla f(\mathbf{x}{)}^T\mathbf{d}+o(t\Vert \mathbf{d}\Vert )<0$$
进而
$$f(\mathbf{x})-f(\mathbf{x}+t\mathbf{d})\ge -\alpha t\nabla f(\mathbf{x}{)}^T\mathbf{d}$$

Goldstein准则

也叫做Armijo-Goldstein准则
为了克服Armijo准则的步长可能过小，这个准则
$$\begin{array}{rl}f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)& \le f({\mathbf{x}}_k)+\alpha t_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)& \ge f({\mathbf{x}}_k)+(1-\alpha )t_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\end{array}$$
其中$\alpha \in (0,\frac{1}{2})$

然而缺点就是，可能会漏掉最优的点

Wolfe准则

也叫Wolfe-Powell准则
$$\begin{array}{rl}f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)& \le f({\mathbf{x}}_k)+{\alpha }_1{t}_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ \nabla f({\mathbf{x}}_k+t_k{\mathbf{d}}_k{)}^T{\mathbf{d}}_k& \ge {\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\end{array}$$
其中${\alpha }_1,{\alpha }_2\in (0,1),{\alpha }_1<{\alpha }_2$

也有强Wolfe准则
$$\begin{array}{rl}f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)& \le f({\mathbf{x}}_k)+{\alpha }_1{t}_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ \left|\nabla f({\mathbf{x}}_k+t_k{\mathbf{d}}_k{)}^T{\mathbf{d}}_k\right|& \le \left|{\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\right|\end{array}$$
其中${\alpha }_1,{\alpha }_2\in (0,1),{\alpha }_1<{\alpha }_2$

设$\varphi (t_k)=f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)$
$${\varphi }^{\prime }(t_k)=\nabla f({\mathbf{x}}_k+t_k{\mathbf{d}}_k{)}^T{\mathbf{d}}_k$$
而极小值点$t_k^{\ast }$,满足
$${\varphi }^{\prime }(t_k^{\ast })=0$$
所以第二个条件总是满足的
第一个条件其实就是Armijo准则

存在性

设$f:{\mathbb{R}}^n\to \mathbb{R}$连续可微，${\mathbf{d}}_k$时一个下降方向，$f$有下界 { x k + α d k ∣ α > 0 } \left\{\mathbf{x}_k+\alpha\mathbf{d}_k|\alpha>0\right\} {xk​+αdk​∣α>0}.如果$0<{\alpha }_1<{\alpha }_2<1$,则存在步长满足Wolfe准则和强Wolfe准则

证明：
设$\varphi (t_k)=f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)$
$l\left(t\right)=f({\mathbf{x}}_k)+{\alpha }_{1}t\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$和$\varphi$必然有交集
设$t^{\prime }>0$为他们相交的最小的$t^{\prime }$,则
$$f\left({\mathbf{x}}_k+t^{\prime }{\mathbf{d}}_k\right)=f({\mathbf{x}}_k)+{\alpha }_1{t}^{\prime }\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$$
$t^{\prime }$满足Armijo条件,并且对于小于$t^{\prime }$的步长也满足

根据拉格朗日中值定理,存在$t^{\prime \prime }\in \left(0,t^{\prime }\right)$,使得
$$f\left({\mathbf{x}}_k+t^{\prime }{\mathbf{d}}_k\right)-f({\mathbf{x}}_k)=t^{\prime }\nabla f({\mathbf{x}}_k+t^{\prime \prime }{\mathbf{d}}_k{)}^T{\mathbf{d}}_k$$

结合一下
$$\nabla f({\mathbf{x}}_k+t^{\prime \prime }{\mathbf{d}}_k{)}^T{\mathbf{d}}_k={\alpha }_1\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k>{\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$$
所以$t^{\prime \prime }$是满足Wolfe准则的步长
注意到${\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k<0$以及${\alpha }_1\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k<0$
所以$t^{\prime \prime }$是满足强Wolfe准则的步长

步骤

https://blog.csdn.net/weixin_43761124/article/details/107436454

收敛性

考虑一般的迭代格式，其中${\mathbf{d}}_k$是搜索方向，$t_k$是步长，且在迭代过程中满足Wolfe准则，假设目标函数$f$连续可微，有下界，且
$$\Vert \nabla f(\mathbf{x})-\nabla f(\mathbf{y})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert ,\forall \mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$$
那么
$$\sum _{k=0}^{\infty }{\cos }^2{\theta }_k\Vert {\nabla }^{2}f({\mathbf{x}}_k){\Vert }^2<+\infty$$
其中$\cos {\theta }_k$为负梯度和下降方向$d_k$的夹角的余弦，即
$$\cos {\theta }_k=\frac{-\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k}{\Vert \nabla f({\mathbf{x}}_k)\Vert \Vert {\mathbf{d}}_k\Vert }$$
这个不等式也叫做Zoutendijk不等式

证明：

$$\begin{array}{rl}\nabla f({\mathbf{x}}_k+t_k{\mathbf{d}}_k{)}^T{\mathbf{d}}_k& \ge {\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ \nabla f({\mathbf{x}}_{k+1}{)}^T{\mathbf{d}}_k& \ge {\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ \nabla f({\mathbf{x}}_{k+1}{)}^T{\mathbf{d}}_k-\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k& \ge {\alpha }_2\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k-\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ (\nabla f({\mathbf{x}}_{k+1})-f({\mathbf{x}}_k){)}^T{\mathbf{d}}_k& \ge ({\alpha }_2-1)\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\end{array}$$
$$(\nabla f({\mathbf{x}}_{k+1})-f({\mathbf{x}}_k){)}^T{\mathbf{d}}_k\le \Vert \nabla f({\mathbf{x}}_{k+1})-f({\mathbf{x}}_k)\Vert \Vert {\mathbf{d}}_k\Vert \le t_{k}L\Vert {\mathbf{d}}_k{\Vert }^2$$
于是
$$t_k\ge \frac{({\alpha }_2-1)}{L}\frac{\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k}{\Vert {\mathbf{d}}_k{\Vert }^2}$$

注意到$\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k<0$
$$\begin{array}{rl}f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)& \le f({\mathbf{x}}_k)+{\alpha }_1{t}_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ f({\mathbf{x}}_{k+1})& \le f({\mathbf{x}}_k)+{\alpha }_1\frac{({\alpha }_2-1)}{L}\frac{\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k}{\Vert {\mathbf{d}}_k{\Vert }^2}\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k\\ f({\mathbf{x}}_{k+1})& \le f({\mathbf{x}}_k)+{\alpha }_1\frac{({\alpha }_2-1)}{L}{\cos }^2{\theta }_k\Vert {\nabla }^{2}f({\mathbf{x}}_k){\Vert }^2\end{array}$$
关于$k$求和，得到
$$\begin{array}{rl}f({\mathbf{x}}_{k+1})& \le f(0)+{\alpha }_1\frac{({\alpha }_2-1)}{L}\sum _{j=0}^k{\cos }^2{\theta }_j\Vert {\nabla }^{2}f({\mathbf{x}}_j){\Vert }^2\\ \sum _{j=0}^k{\cos }^2{\theta }_j\Vert {\nabla }^{2}f({\mathbf{x}}_j){\Vert }^2& \le \frac{f(0)-f({\mathbf{x}}_{k+1})}{{\alpha }_1\frac{(1-{\alpha }_2)}{L}}\end{array}$$
其中利用了$0<{\alpha }_1<{\alpha }_2<1$
因为$f$有下界，所以$k\to \infty$时
$$\sum _{k=0}^{\infty }{\cos }^2{\theta }_k\Vert {\nabla }^{2}f({\mathbf{x}}_k){\Vert }^2<+\infty$$

推论

对于迭代法，设
$$\cos {\theta }_k=\frac{-\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k}{\Vert \nabla f({\mathbf{x}}_k)\Vert \Vert {\mathbf{d}}_k\Vert }$$
并假设$\forall k,\exists \gamma >0$使得
$${\theta }_k<\frac{\pi }{2}-\gamma$$
在Zoutendijk不等式成立的条件下，有
$$\underset{k\to \infty }{\lim }\nabla f({\mathbf{x}}_k)=0$$
证明：
假设结论不成立，即存在子列 { k l } \{k_l\} {kl​}和正常数$\delta >0$,使得
$$\Vert f({\mathbf{x}}_{k_l})\Vert \ge \delta ,l=1,2,\cdots$$
$$\begin{array}{rl}{\theta }_k& <\frac{\pi }{2}-\gamma \\ \cos {\theta }_k& >\cos (\frac{\pi }{2}-\gamma )=\sin \gamma >0\end{array}$$
$$\begin{array}{rl}\sum _{k=0}^{\infty }{\cos }^2{\theta }_k\Vert {\nabla }^{2}f({\mathbf{x}}_k){\Vert }^2& \ge \sum _{l=1}^{\infty }{\cos }^2{\theta }_{k_l}\Vert {\nabla }^{2}f({\mathbf{x}}_{k_l}){\Vert }^2\\ & \ge \sum _{l=1}^{\infty }{\sin }^2\gamma {\delta }^2\to +\infty \end{array}$$
矛盾
所以
$$\underset{k\to \infty }{\lim }\nabla f({\mathbf{x}}_k)=0$$

回溯法

设$s>0,\alpha \in (0,1),\beta \in (0,1)$,我们要让步长满足Armijo准则
即，先猜测$t_k=s$
当
$$f({\mathbf{x}}_k)-f({\mathbf{x}}_k+t_k{\mathbf{d}}_k)<-\alpha t_k\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$$
时，让$t_k=\beta t_k$
换句话说,$t_k=s{\beta }^{i_k}$,其中$i_k$满足
$$f({\mathbf{x}}_k)-f({\mathbf{x}}_k+s{\beta }^{i_k}{\mathbf{d}}_k)\ge -\alpha s{\beta }^{i_k}\nabla f({\mathbf{x}}_k{)}^T{\mathbf{d}}_k$$

梯度方法

引理

设$f:{\mathbb{R}}^n\to \mathbb{R}$是一个在${\mathbb{R}}^n$上连续可微的函数。
设$\mathbf{x}\in {\mathbb{R}}^n$不是一个驻点，即$\nabla f(\mathbf{x})\ne 0$
那么
min ⁡ d ∈ R n { f ′ ( x ; d ) : ∥ d ∥ = 1 } \min\limits_{\boldsymbol{d}\in\mathbb{R}^n}\{f'(\boldsymbol{x};\boldsymbol{d}):\Vert \boldsymbol{d}\Vert=1\} d∈Rnmin​{f′(x;d):∥d∥=1}
的最优解是
$$\mathbf{d}=-\frac{\nabla f(\mathbf{x})}{\Vert f(\mathbf{x})\Vert }$$
证明：
$$f^{\prime }(\mathbf{x};\mathbf{d})=\nabla f(\mathbf{x}{)}^T\mathbf{d}\ge -\Vert \nabla f(\mathbf{x})\Vert \Vert \mathbf{d}\Vert$$
当且仅当$\nabla f(\mathbf{x})=\lambda \mathbf{d}$时取等
即$\mathbf{d}=-\Vert \nabla f(\mathbf{x}){\Vert }^2$

也就是说，负梯度方向是下降最快的方向

梯度方法框架

1.选择初始点${\mathbf{x}}_0\in {\mathbb{R}}^n$
2. 循环$k=0,1,\cdots$
a)挑选步长$t_k$,使得$f({\mathbf{x}}_k-t_k\nabla f({\mathbf{x}}_k))<f({\mathbf{x}}_k)$
c)迭代${\mathbf{x}}_{k+1}={\mathbf{x}}_k-t_k\nabla f({\mathbf{x}}_k)$
d)如果满足停止条件就停止，并返回${\mathbf{x}}_{k+1}$

这里步长你依然可以用之前的固定步长，精确线搜索，或者回溯法，或者其他非精确线搜索

下面给出梯度方法中用回溯法的代码

function [x,fun_val]=gradient_method_backtracking(f,g,x0,s,alpha,...
beta,epsilon)
% Gradient method with backtracking stepsize rule
%
% INPUT
%=======================================
% f ......... objective function
% g ......... gradient of the objective function
% x0......... initial point
% s ......... initial choice of stepsize
% alpha ..... tolerance parameter for the stepsize selection
% beta ...... the constant in which the stepsize is multiplied
% at each backtracking step (0<beta<1)
% epsilon ... tolerance parameter for stopping rule
% OUTPUT
%=======================================
% x ......... optimal solution (up to a tolerance)
% of min f(x)
% fun_val ... optimal function value
x=x0;
grad=g(x);
fun_val=f(x);
iter=0;
while (norm(grad)>epsilon)
    iter=iter+1;
    t=s;
    while (fun_val-f(x-t*grad)<alpha*t*norm(grad)^2)
        t=beta*t;
    end
    x=x-t*grad;
    fun_val=f(x);
    grad=g(x);
    fprintf('iter_number = %3d norm_grad = %2.6f fun_val = %2.6f \n',...
    iter,norm(grad),fun_val);
end

收敛性

下降引理

设$f\in C_L^{1,1}$,那么$\forall \mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$
$$f(\mathbf{y})\le f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{L}{2}\Vert \mathbf{x}-\mathbf{y}{\Vert }^2$$
证明：
$$\begin{array}{rl}f(\mathbf{y})-f(\mathbf{x})& ={\int }_0^1⟨\nabla f(\mathbf{x}+t(\mathbf{y}-\mathbf{x})),\mathbf{y}-\mathbf{x}⟩\mathrm{d}t\\ f(\mathbf{y})-f(\mathbf{x})& =⟨\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩+{\int }_0^1⟨\nabla f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩\mathrm{d}t\\ |f(\mathbf{y})-f(\mathbf{x})-⟨\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩|& =\left|{\int }_0^1⟨\nabla f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩\mathrm{d}t\right|\\ & \le {\int }_0^1|⟨\nabla f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}⟩|\mathrm{d}t\\ & \le {\int }_0^1\Vert \nabla f(\mathbf{x}+t(\mathbf{y}-\mathbf{x}))-\nabla f(\mathbf{x})\Vert \cdot \Vert \mathbf{y}-\mathbf{x}\Vert \mathrm{d}t\\ & \le {\int }_0^{1}tL\Vert \mathbf{y}-\mathbf{x}{\Vert }^2\mathrm{d}t\\ & =\frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }^2\end{array}$$

充分下降引理

sufficient decrease lemma

假设$f\in C_L^{1,1}$,那么$\forall x\in {\mathbb{R}}^n,t>0$,有
$$f(\mathbf{x})-f(\mathbf{x}-t\nabla f(\mathbf{x}))\ge t\left(1-\frac{Lt}{2}\right)\Vert \nabla f(\mathbf{x}){\Vert }^2$$
证明：
由下降引理
$$\begin{array}{rl}f(\mathbf{x}-t\nabla f(\mathbf{x}))& \le f(\mathbf{x})-t\Vert \nabla f(\mathbf{x}){\Vert }^2+\frac{L{t}^2}{2}\Vert \nabla f(\mathbf{x}){\Vert }^2\\ & =f(\mathbf{x})-t\left(1-\frac{Lt}{2}\right)\Vert \nabla f(\mathbf{x}){\Vert }^2\end{array}$$

固定步长

由充分下降引理
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge \bar{t}\left(1-\frac{L\bar{t}}{2}\right){\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
要想下降
$$\{\begin{array}{l}\bar{t}>0\\ \left(1-\frac{L\bar{t}}{2}\right)>0\end{array}\Rightarrow 0<\bar{t}<\frac{2}{L}$$
显然当$\bar{t}=\frac{1}{L}$时取得最大值
所以固定步长，可以取$\bar{t}=\frac{1}{L}$
从而
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)=f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-\frac{1}{L}\nabla f\left({\mathbf{x}}_k\right)\right)\ge \frac{1}{2L}{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$

精确线搜索

因为$t_k=\arg \underset{t\ge 0}{\min }f({\mathbf{x}}_k-t_k\nabla f\left({\mathbf{x}}_k\right))$
有
$$f\left({\mathbf{x}}_k-t_k\nabla f\left({\mathbf{x}}_k\right)\right)\le f\left({\mathbf{x}}_k-\frac{1}{L}\nabla f\left({\mathbf{x}}_k\right)\right)$$
因此
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-\frac{1}{L}\nabla f\left({\mathbf{x}}_k\right)\right)\ge \frac{1}{2L}{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$

回溯法

第一种情况，直接满足Armijo准则，即
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-s\nabla f\left({\mathbf{x}}_k\right)\right)\ge \alpha s{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
第二种情况，$t_k$时满足Armijo准则，也就是说$\frac{t_k}{\beta }$还不满足Armijo准则
有
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-\frac{t_k}{\beta }\nabla f\left({\mathbf{x}}_k\right)\right)<\alpha \frac{t_k}{\beta }{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2,$$
让$x=x_k,t=\frac{t_k}{\beta }$,代入充分下降引理，有
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-\frac{t_k}{\beta }\nabla f\left({\mathbf{x}}_k\right)\right)\ge \frac{t_k}{\beta }\left(1-\frac{L{t}_k}{2\beta }\right){\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
联合上面两个式子，得到
$$\begin{array}{rl}\frac{t_k}{\beta }\left(1-\frac{L{t}_k}{2\beta }\right)& <\alpha \frac{t_k}{\beta }\\ t_k& >\frac{2(1-\alpha )\beta }{L}\end{array}$$
综上所述
$$t_k\ge \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}$$
使得
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_k-t_k\nabla f\left({\mathbf{x}}_k\right)\right)\ge \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$

梯度方法的充分下降

sufficient decrease of the gradient method
设$f\in C_L^{1,1}({\mathbb{R}}^n)$
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​为梯度方法产生在解决
$$\underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }f(\mathbf{x})$$
产生的序列，使用的步长

• 固定步长$\bar{t}\in (0,\frac{2}{L})$
• 精确线搜索
• 回溯法($s\in {\mathbb{R}}_{++},\alpha \in (0,1),\beta \in (0,1)$)

那么
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge M{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
其中
$$M=\{\begin{array}{ll}\bar{t}\left(1-\frac{\bar{t}L}{2}\right)& \text{ 固定步长 }\\ \frac{1}{2L}& \text{ 精确线搜索 }\\ \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}& \text{回溯法 }\end{array}$$

梯度方法收敛性

设$f\in C_L^{1,1}({\mathbb{R}}^n)$
设 { x k } k ≥ 0 \{\mathbf{x}_k\}_{k\ge 0} {xk​}k≥0​为梯度方法产生在解决
$$\underset{\mathbf{x}\in {\mathbb{R}}^n}{\min }f(\mathbf{x})$$
产生的序列，使用的步长

• 固定步长$\bar{t}\in (0,\frac{2}{L})$
• 精确线搜索
• 回溯法($s\in {\mathbb{R}}_{++},\alpha \in (0,1),\beta \in (0,1)$)

假设$f$有下界，即$\exists m\in \mathbb{R},\forall \mathbf{x}\in {\mathbb{R}}^n,f(\mathbf{x})>m$
那么有
a)序列 { f ( x k ) } k ≥ 0 \{f(\mathbf{x}_k)\}_{k\ge 0} {f(xk​)}k≥0​单调不增，并且$\forall k\ge 0,f({\mathbf{x}}_{k+1})<f({\mathbf{x}}_k)$,除非$\nabla f({\mathbf{x}}_k)=0$
b)当$k\to \infty ,\nabla f({\mathbf{x}}_k)\to 0$
证明：
a)
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge M{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2\ge 0$$
$M>0$,如果$f\left({\mathbf{x}}_k\right)=f\left({\mathbf{x}}_{k+1}\right)$,那么$\nabla f\left({\mathbf{x}}_k\right)=0$

b)
{ f ( x k ) } k ≥ 0 \{f(\mathbf{x}_k)\}_{k\ge 0} {f(xk​)}k≥0​单调递减有下界，所以收敛
$k\to \infty ,f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)$那么$k\to \infty ,\nabla f({\mathbf{x}}_k)\to 0$

梯度的范数收敛速率

设 { f ( x k ) } k ≥ 0 \{f(\mathbf{x}_k)\}_{k\ge 0} {f(xk​)}k≥0​收敛到$f^{\ast }$，则
$$\underset{k=0,1,\dots ,n}{\min }\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert \le \sqrt{\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{M(n+1)}}$$
其中$$M=\{\begin{array}{ll}\bar{t}\left(1-\frac{\bar{t}L}{2}\right)& \text{ 固定步长 }\\ \frac{1}{2L}& \text{ 精确线搜索 }\\ \alpha \min \left\{s,\frac{2(1-\alpha )\beta }{L}\right\}& \text{回溯法 }\end{array}$$

证明：
根据
$$f\left({\mathbf{x}}_k\right)-f\left({\mathbf{x}}_{k+1}\right)\ge M{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
有
$$f\left({\mathbf{x}}_0\right)-f^{\ast }\ge M\sum _{k=0}^n{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
显然${\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2\ge \underset{k=0,1,\cdots ,n}{\min }{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$
所以
$$f\left({\mathbf{x}}_0\right)-f^{\ast }\ge M(n+1)\underset{k=0,1,\cdots ,n}{\min }{\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert }^2$$
于是
$$\underset{k=0,1,\dots ,n}{\min }\Vert \nabla f\left({\mathbf{x}}_k\right)\Vert \le \sqrt{\frac{f\left({\mathbf{x}}_0\right)-f^{\ast }}{M(n+1)}}$$