本文主要内容如下：

• 1. 最速下降法
• 2. 抛物型多元二次函数优化问题的步长选取
• 3. 抛物型多元二次函数等值线/面的几何分析
• 4. 基于最速下降法的 “变步长Richardson 迭代法” 的收敛性分析

1. 最速下降法

数值求解极小值问题的基本思想在于从给定的初始点 x ⃗ 0 \vec{x}_0 x 0​ 出发，沿某一搜索方向 d ⃗ 0 \vec{d}_0 d 0​ 进行搜索，同时通过确定**步长 α 0 \alpha_0 α0​ 使函数值沿该搜索方向下降最大。依此方式不断进行，形成函数值下降的迭代算法，即：
x ⃗ k + 1 = x ⃗ k + α k d ⃗ k ( k = 0 , 1 , 2 , … ) f ( x ⃗ k + 1 ) < f ( x ⃗ k ) \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{d}_k\ (k=0,1,2,\dots)\\\ \\ f(\vec{x}_{k+1})<f(\vec{x}_k) x k+1​=x k​+αk​d k​ (k=0,1,2,…) f(x k+1​)<f(x k​)
对于任意的 n n n 元函数 f ( x ⃗ ) ( x ⃗ ∈ R n ) f(\vec{x})\ (\vec{x}\in\mathbb{R}^n) f(x ) (x ∈Rn) 的方向导数（反映函数在当前位置沿任意方向的变化快慢）：
d f ( x ⃗ ) d r ⃗ ∣ x ⃗ = x ⃗ 0 = lim ⁡ Δ r → 0 f ( x 1 + Δ x 1 , x 2 + Δ x 2 , … , x n + Δ x n ) − f ( x 1 , … , x n ) Δ r = g r a d ( f ) ∣ x ⃗ = x ⃗ 0 ⋅ r ⃗ \begin{aligned} &\left.\dfrac{df(\vec{x})}{d\vec{r}}\right|_{\vec{x}=\vec{x}_0}=\lim_{\Delta r\rightarrow0}\dfrac{f(x_1+\Delta x_1,x_2+\Delta x_2,\dots,x_n+\Delta x_n)-f(x_1,\dots,x_n)}{\Delta r}\\\\ &\qquad\qquad\quad=\left.grad(f)\right|_{\vec{x}=\vec{x}_0}\cdot\vec{r} \end{aligned} ​dr df(x )​∣ ∣​x =x 0​​=Δr→0lim​Δrf(x1​+Δx1​,x2​+Δx2​,…,xn​+Δxn​)−f(x1​,…,xn​)​=grad(f)∣x =x 0​​⋅r ​
其中， r ⃗ = 1 Δ r [ Δ x 1 , Δ x 2 , … , Δ x n ] \vec{r}=\dfrac{1}{\Delta r}\begin{bmatrix}\Delta x_1,\Delta x_2,\dots,\Delta x_n\end{bmatrix} r =Δr1​[Δx1​,Δx2​,…,Δxn​​] 为任意单位方向， Δ r = Δ x 1 2 + ⋯ + Δ x n 2 \Delta r=\sqrt{\Delta x_1^2+\dots+\Delta x_n^2} Δr=Δx12​+⋯+Δxn2​ ​，

上式说明：函数的负梯度方向是函数值在该点下降最快的方向。 因此，很容易想到利用负梯度作为搜索方向，这便是为何将其称为最速下降法（Steepest Descent）或梯度法，即
x ⃗ k + 1 = x ⃗ k − α k ▽ f ( x ⃗ k ) ( k = 0 , 1 , 2 , … ) \vec{x}_{k+1}=\vec{x}_k-\alpha_k\bigtriangledown f(\vec{x}_k)\ (k=0,1,2,\dots) x k+1​=x k​−αk​▽f(x k​) (k=0,1,2,…)
搜索方向确定后，步长还有待确定。我们希望函数沿着搜索方向上能够“前进”到该方向上的极小值，如图所示：

另外，梯度沿着等值线、等值面的外法线方向，那么轴线上的各点梯度便指向 ”椭圆“ 中心，说明：若初始点恰巧选择在 ”椭圆“ 的轴线，最速下降法仅一步便可以求得上述优化问题的解。

4. 基于最速下降法的 “变步长Richardson 迭代法” 的收敛性分析

求解线性方程组：
A x ⃗ = b ⃗ ( A ∈ S P D ) \bold A \vec{x}=\vec{b}\quad (\bold A\in SPD) Ax =b (A∈SPD)
等价于求解如下二次函数的极小值点：
g ( x ⃗ ) = 1 2 x ⃗ T A x ⃗ − b ⃗ T x ⃗ + c ( A ∈ S P D ) g(\vec{x})=\frac{1}{2}\vec{x}^T\bold{A}\vec{x}-\vec{b}^T\vec{x}+c\quad (\bold A\in SPD) g(x )=21​x TAx −b Tx +c(A∈SPD)
基于最速下降法可以得出 “变步长Richardson 迭代法”，即参数 α \alpha α 不再取为固定值，求解格式如下：
{ r ⃗ k = b ⃗ − A ⋅ x ⃗ k α k = r ⃗ k T ⋅ r ⃗ k r ⃗ k T ⋅ A ⋅ r ⃗ k x ⃗ k + 1 = x ⃗ k + α k r ⃗ k \begin{cases} \vec{r}_k=\vec{b}-\bold{A}\cdot\vec{x}_k\\\\ \alpha_k=\dfrac{\vec{r}_k^{\ T}\cdot\vec{r}_k}{\vec{r}_k^{\ T}\cdot\bold{A}\cdot\vec{r}_k}\\\\ \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{r}_k \end{cases} ⎩ ⎨ ⎧​r k​=b −A⋅x k​αk​=r k T​⋅A⋅r k​r k T​⋅r k​​x k+1​=x k​+αk​r k​​
现对这种方法的收敛性及收敛速度进行分析：(方程组的精确解为 x ⃗ \vec{x} x )

令
E ( x ⃗ k ) ≜ 1 2 e ⃗ k T A e ⃗ k = 1 2 ( x k ⃗ − x ⃗ ) T A ( x k ⃗ − x ⃗ ) = g ( x ⃗ k ) + 1 2 x ⃗ T A x ⃗ \begin{aligned} E(\vec{x}_k)\triangleq\frac{1}{2}\vec{e}_k^T\bold A\vec{e}_k =\frac{1}{2}(\vec{x_k}-\vec{x})^T\bold A(\vec{x_k}-\vec{x}) =g(\vec{x}_k)+\frac{1}{2}\vec{x}^T\bold A\vec{x} \end{aligned} E(x k​)≜21​e kT​Ae k​=21​(xk​ ​−x )TA(xk​ ​−x )=g(x k​)+21​x TAx ​
又
x ⃗ k + 1 = x ⃗ k + α k r ⃗ k ⟹ e ⃗ k + 1 = e ⃗ k + α k r ⃗ k r ⃗ k = b ⃗ − A x ⃗ k = A x ⃗ − A x ⃗ k = − A e ⃗ k ⟹ e ⃗ k = − A − 1 r ⃗ k \vec{x}_{k+1}=\vec{x}_k+\alpha_k\vec{r}_k \Longrightarrow \vec{e}_{k+1}=\vec{e}_k+\alpha_k\vec{r}_k\\\ \\ \vec{r}_k=\vec{b}-\bold A\vec{x}_k=\bold A\vec{x}-\bold A\vec{x}_k=-\bold A\vec{e}_k \Longrightarrow \vec{e}_k=-\bold A^{-1}\vec{r}_k x k+1​=x k​+αk​r k​⟹e k+1​=e k​+αk​r k​ r k​=b −Ax k​=Ax −Ax k​=−Ae k​⟹e k​=−A−1r k​
那么
E ( x ⃗ k ) − E ( x ⃗ k + 1 ) E ( x ⃗ k ) = e ⃗ k T A e ⃗ k − e ⃗ k + 1 T A e ⃗ k + 1 e ⃗ k T A e ⃗ k = e ⃗ k T A e ⃗ k − ( e ⃗ k + α k r ⃗ k ) T A ( e ⃗ k + α k r ⃗ k ) e ⃗ k T A e ⃗ k = − 2 α k r ⃗ k T A e ⃗ k − α k 2 r ⃗ k T A r ⃗ k e ⃗ k T A e ⃗ k = ( r ⃗ k T r ⃗ k ) 2 ( r ⃗ k T A r ⃗ k ) ( r ⃗ k T A − 1 r ⃗ k ) ≥ 4 λ m i n A λ m a x A ( λ m i n A + λ m a x A ) 2 （ K a n t o r v i c h 不等式） \begin{aligned} &\quad\dfrac{E(\vec{x}_k)-E(\vec{x}_{k+1})}{E(\vec{x}_k)}\\\\ &=\dfrac{\vec{e}_k^T\bold A\vec{e}_k-\vec{e}_{k+1}^T\bold A\vec{e}_{k+1}}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{\vec{e}_k^T\bold A\vec{e}_k-(\vec{e}_k+\alpha_k\vec{r}_k)^T\bold A(\vec{e}_k+\alpha_k\vec{r}_k)}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{-2\alpha_k\vec{r}_k^T\bold A\vec{e}_k-\alpha_k^2\vec{r}_k^T\bold A\vec{r}_k}{\vec{e}_k^T\bold A\vec{e}_k}\\\\ &=\dfrac{(\vec{r}_k^T\vec{r}_k)^2}{(\vec{r}_k^T\bold A\vec{r}_k)(\vec{r}_k^T\bold A^{-1}\vec{r}_k)}\\\\ &\ge\dfrac{4\lambda^A_{min}\lambda^A_{max}}{(\lambda^A_{min}+\lambda^A_{max})^2}（Kantorvich 不等式） \end{aligned} ​E(x k​)E(x k​)−E(x k+1​)​=e kT​Ae k​e kT​Ae k​−e k+1T​Ae k+1​​=e kT​Ae k​e kT​Ae k​−(e k​+αk​r k​)TA(e k​+αk​r k​)​=e kT​Ae k​−2αk​r kT​Ae k​−αk2​r kT​Ar k​​=(r kT​Ar k​)(r kT​A−1r k​)(r kT​r k​)2​≥(λminA​+λmaxA​)24λminA​λmaxA​​（Kantorvich不等式）​
从而有：
E ( x ⃗ k + 1 ) ≤ [ 1 − 4 λ m i n A λ m a x A ( λ m i n A + λ m a x A ) 2 ] E ( x ⃗ k ) = ( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 E ( x ⃗ k ) E(\vec{x}_{k+1})\le\left[1-\dfrac{4\lambda^A_{min}\lambda^A_{max}}{(\lambda^A_{min}+\lambda^A_{max})^2}\right]E(\vec{x}_k) =\left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^2E(\vec{x}_k) E(x k+1​)≤[1−(λminA​+λmaxA​)24λminA​λmaxA​​]E(x k​)=(λminA​+λmaxA​λminA​−λmaxA​​)2E(x k​)
那么
0 ≤ E ( x ⃗ k ) ≤ ( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 k E ( x ⃗ 0 ) 0\le E(\vec{x}_{k})\le\left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^{2k}E(\vec{x}_0) 0≤E(x k​)≤(λminA​+λmaxA​λminA​−λmaxA​​)2kE(x 0​)
即
lim ⁡ k → ∞ E ( x ⃗ k ) = 0 \lim_{k\rightarrow\infty}E(\vec{x}_{k})=0 k→∞lim​E(x k​)=0
因为 A \bold A A 为对称正定矩阵，当且仅当 x ⃗ k = x ⃗ \vec{x}_k=\vec{x} x k​=x 时， E ( x ⃗ k ) = 0 E(\vec{x}_k)=0 E(x k​)=0，故基于最速下降法的 “变步长Richardson 迭代法”必定收敛，且收敛速度至少为：
( λ m i n A − λ m a x A λ m i n A + λ m a x A ) 2 = [ c o n d ( A ) 2 − 1 c o n d ( A ) 2 + 1 ] 2 \left(\dfrac{\lambda^A_{min}-\lambda^A_{max}}{\lambda^A_{min}+\lambda^A_{max}}\right)^2=\left[\dfrac{cond(\bold A)_2-1}{cond(\bold A)_2+1}\right]^2 (λminA​+λmaxA​λminA​−λmaxA​​)2=[cond(A)2​+1cond(A)2​−1​]2
优于Richardson 迭代法的**收敛速度。

那么，当对称正定矩阵 A \bold A A 的最大特征值越接近于最小特征值时，收敛速度越快，换而言之，等值线的椭圆长轴短轴长度越接近时收敛速度越快，**的情况是等值线为同心圆，此时仅需一步便可得到精确解。而若椭圆偏心率越大，越扁平，即最大特征值与最小特征值相差越大，收敛速度便会越小。