收敛速度

由算法A产生的迭代序列${x^{k}$在某种意义下收敛到$x}$即$\lim_{k \to \infty} \left | x^k-x \right | =0$，且存在常数$\alpha>0,q>0$
$$
s.t.\lim_{k \to \infty} \frac{\left | x^{k+1}-x* \right | }{\left | x^k-x* \right | ^{\alpha}} =q
$$
则称算法A产生的点列${x^k}$具有$\alpha$阶的收敛速度或称算法A是$\alpha$阶收敛的

• $\alpha=1,且0<q\le1$,算法A线性收敛
• $1<\alpha<2,且q>0/\alpha=1,q=0$,算法A超线性收敛
• $\alpha=2$,算法A二阶收敛

最速下降法

选择$x^{k$处的负梯度作为搜索方向$d}k=-\grad f(x^k)$,步长$\alpha_k$是$\phi (\alpha)=f(x^k+\alpha d^k)$中的精确最小点，${\phi }' (\alpha)=0$
$$
{\phi }' (\alpha)=\grad f(x^k+\alpha d^k)=-\grad f(x^{k+1})T\grad f(x^k)=0
$$
特点：

• 简单直观
• 收敛
• 搜索方向只要计算$\grad f(x^k)$

缺点：

• 收敛速度慢（线性收敛）
• Zigzag现象
• 不具备二次中止性（在有限步内求得凸二次函数最优解）

牛顿法

基本思想：在当前$x^{k$处选择$d}k=-[\grad^2f(xk)]^{-1}\grad f(x^k)$

理解：对$x^k$处的二次逼近函数进行最小化
$$
\min (f(x^k)+\grad f(x^k)T(x-x^k)+\frac{1}{2} (x-x^k)T\grad f(x^k)(x-xk))\
x^{k+1}=xk-[\grad^2f(xk)]^{-1}\grad f(x^k)\
所以d^k=-[\grad2f(x^k)]\grad f(x^k),步长\alpha_k=1
$$
步骤：

• step0：$x^0,\varepsilon ,k:=0$
• step1:$\left | \grad f(x^k) \right | \le \varepsilon $?
• step2:计算$d^k$
• step3:$x^{k+1}=xk+d^k,k:=k+1$go to step1

优点：

• 初始点$x^{0$取得比较接近收敛点$x}*$，且$\grad^2f(x)$满足比较好的性质时二阶收敛，具有二阶中止性

缺点：

• 计算量大，要计算Hesse矩阵
• 适用范围窄

阻尼/修正牛顿法

对牛顿法的方向和步长进行修正

修正$\alpha_k$：

• $\alpha_k=1$时能否让目标函数充分下降
• 如果否，用线搜索重新确定$\alpha_k$

修正方向$d^k$:$dk=-B_k^{-1}\grad f(x^k)$

• 若$\grad^2f(xk)>0$，则$B_k:=\grad^2f(xk)>0$

• 否则修正方法：

  • 1.$B_k:=\grad^2f(xk)+\lambda E,\lambda 为适当正数保证B_k正交$

  • 2.考虑特征值分解

    $\grad^2f(xk)=Q^T\Lambda Q,其中\Lambda=diag{\lambda_1 \cdots\lambda_n}$

    $B_k=Q^Tdiag(\tau _i) Q,\tau _i=\left{\begin{matrix}
    \lambda_i ,\ \ \ if \lambda_i \ge \delta \
    \delta,\ \ \ \ \ \ \ otherwise
    \end{matrix}\right.(\delta为适当正数)$

拟牛顿法

考虑$f(x)$在当前点$x^k$的二次近似函数
$$
m_k(x):=f(x^k)+\grad f(x^k)T(x-x^{k)+\frac{1}{2}(x-x}k)^TB_k(x-xk)\
B_k>0,并且不仅要体现一些二次信息，还要容易获取\
利用\min m_k(x)得d^k=-B_k \grad f(x^k)
$$
步骤：

• step0: $x^0 ,\varepsilon,k:=0,B_0=\grad^2f(x0)+\lambda E $
• step1: if $\left | \grad f(x^*) \right | \le \varepsilon $?
• step2:算$d^k=-B_k \grad f(x^k)$
• step3:确定步长$\alpha_k$（采用线搜索）
• step4:$x^{k+1}=xk+\alpha_kd^k$确定$B_{k+1},k:=k+1$ go to step1

拟牛顿法是一类方法
$$
B_{k+1}矩阵得确定，拟牛顿法的基本要求\
\grad f(x^{k+1})-\grad f(x^k)=B_{k+1}(x-x^k)\
y_k=\grad f(x^{k+1})-\grad f(x^k);s_k=x-x^k\
y_k =B_{k+1}s_k\
B_{k+1}:n\times n;所以\frac{n(n+1)}{2}个变量，n个方程
$$

$$
H_{k+1}=B_{k+1}^{-1}\
所以Bs_k=y_k \to Hy_k=s_k\
$$

几种方法:

DFP方法(秩2)

$$
H_{k+1}=H_{k}-\frac{H_k y_k y_k^TH_k}{y_kTH_k y_k}+\frac{s_k s_k^T}{y_kTs_k}
$$

BFGS方法（秩2）

$$
B_{k+1}=B_k-\frac{B_k s_k s_k^TB_k}{s_kTB_k s_k}+\frac{y_k y_k^T}{y_kTs_k}
$$

被认为是最有效的拟牛顿法，超线性收敛

SR-1(秩1)

$$
B_{k+1}=B_k+\frac{(y_k-B_ks_k)(y_k-B_ks_k)^{T}{(y_k-B_ks_k)}Ts_k}
$$

迭代公式更简单，但不保证正定性

适当条件下达到n步超线性收敛$\lim_{k \to \infty} \frac{\left | x^{k+1+n}-x* \right | }{\left | x^k-x* \right | ^{\alpha}} =0$