最速下降法[二次型]精确步长迭代公式
$$ \alpha_k^{SD}=\frac{g^T(x_k)g(x_k)}{g^T(x_k)Qg(x_k)},g(x)=\nabla f(x),\\=\frac{s_k^Ts_k}{s_k^TQs_k} $$
目标函数$f(x)$的极值有下格式：
$$ f(x)=\frac 12 \boldsymbol x^TQ\boldsymbol x-\boldsymbol b^T\boldsymbol x,Q\succ0,\boldsymbol b,\boldsymbol x\in\mathbb R^n. $$
$$ f(x^)=-\frac12(x^)^TQx^,x^=Q^{-1}\boldsymbol b. $$
定义评估函数$V(x)$
$$ \begin{aligned}V(\boldsymbol x)&=f(\boldsymbol x)-f(\boldsymbol x^)\\&=f(\boldsymbol x)+\frac 12\boldsymbol x^{T}Q\boldsymbol x^=\frac 12(\boldsymbol x-\boldsymbol x^)^TQ(\boldsymbol x-\boldsymbol x^)=\frac 12\lVert \boldsymbol x-\boldsymbol x^\lVert^{2}Q\\&=\frac 12(Q\boldsymbol x-\boldsymbol b)^TQ^{-1}(Q\boldsymbol x-\boldsymbol b)\\&=\frac 12\lVert \nabla f(\boldsymbol x)\lVert{Q^{-1}}^2.\end{aligned} $$
得到梯度的加权｜椭圆范数（Ellipsoidal norm｜weighted norm ）。
【椭圆范数】
<aside>
厄密正定矩阵，$A^\dagger=A,A\succ 0$可以进行Cholesky分解【Cholesky 分解】 $A^\dagger=A\in\mathbb C^{n\times n},x^\dagger Ax>0,\forall x\ne 0$ ，那么矩阵可做Cholesky分解为一般可逆矩阵的乘积（不唯一）
$$ R^\dagger R=A, $$
$$ \lVert x\lVert_A=\sqrt{x^TAx}=\sqrt{x^TR^\dagger Rx}=\|R\bm x\|_2,U\succ0. $$
由向量范数诱导的范数 直接可知 $\lVert x\lVert_A$是范数（加权范数）
</aside>
利用$\nabla f=Qx-b=Qx-Qx^=Q(x-x^)$，可证明引理：$V(\boldsymbol{x}^{(k+1)})=(1-\gamma_{k})V(\boldsymbol{x}^{(k)})$
$$ V(\boldsymbol{x}^{(k+1)})=(1-\gamma_{k})V(\boldsymbol{x}^{(k)}),\\\gamma_{k}=\begin{cases}\alpha_{k}\frac{\boldsymbol{g}^{(k)\top}\boldsymbol{Q}\boldsymbol{g}^{(k)}}{\boldsymbol{g}^{(k)\top}\boldsymbol{Q}^{-1}\boldsymbol{g}^{(k)}}\left(2\frac{\boldsymbol{g}^{(k)\top}\boldsymbol{g}^{(k)}}{\boldsymbol{g}^{(k)\top}\boldsymbol{Q}\boldsymbol{g}^{(k)}}-\alpha_{k}\right)&, g(x)\ne0\\0&,g(x)=0\end{cases}. $$
什么样的序列$\gamma_k$让$V$单调减小，并趋于零？
首先有$k$次迭代和初始点的关系：
$$ V(\boldsymbol{x}^{(k)})=\left(\prod_{i=0}^{\boldsymbol{k}-1}(1-\gamma_{i})\right)V(\boldsymbol{x}^{(\mathbf{0})}) $$
iff $\left(\prod_{i=0}^{\boldsymbol{k}-1}(1-\gamma_{i})\right)\to 0, (k\to \infty)$满足要求。取对数，得到级数求和：
$$ \sum_{i=0}^{\infty}-\log(1-\gamma_{i})\to\infty $$
级数何时发散？
$$ \sum_{i=0}^\infty\gamma_i $$
【充分条件】级数有下界，级数发散。
那么，总结为定理：