二次型优化问题 - 5 - 最速下降法

本文最后更新于：2024年1月14日晚上

本文介绍优化二次型的常用迭代方法——最速下降法。

问题描述

重述我们需要优化的问题：

$$
f({\bf{x} }) = \frac{1}{2}{\bf{x^TAx} } - { {\bf{b} }^{\bf{T} } }{\bf{x} } + {\bf{c} } \tag{1} \label{1}
$$

矩阵$\bf{A}$正定对称
目标为优化$\bf{x}$，使得$f(\bf{x})$取得最小值

最速下降法

当有一天大神们厌倦了代数法解决优化问题时，提出了迭代计算，逐步接近最优解的优化方法，方法的思想也是朴素直观的。

核心思想

我们的目标是找到函数的最小值，而且我已经知道了这个函数就那么一个极小值点，相当于找到一个曲面的最低点，最速下降法的流程图：

graph LR

	A[寻找函数最小值]-->B[计算当前梯度方向]
	B --> C[计算前进距离]
	C --> D{精度是否满足要求}
	D -- 否 --> B
	D -- 是 --> E[输出当前位置]

计算流程

初始位置： $\bf{x}_0$

计算梯度$\bf{g}$

沿用之前的计算结论：

$$
\bf{g} = f’(\bf{x}) = A\bf{x}-\bf{b} \tag{2}
$$

那么关于 $\bf{x}_0$为了寻找最小值，需要向梯度的反方向前进，但为了保证推导过程顺遂，前进距离系数不管符号，设第$i$步需要前进的距离为${\alpha}_i$,那么对于第$i$个$\bf{x}_i$，有：

$$
{\bf{x}_{i + 1} } = {\bf{x}_i} + \alpha_i {\bf{g}_i} \tag{3} \label{3}
$$

系数${\alpha}_i$求解

方法1：

行动前后两个位置的梯度方向需要正交，不然当前行动的位置还可以取到更低的值：

即：

$$ {\bf{g}}_i^T {{\bf{g}}_{i + 1}}=0 \tag{4} $$ 其中： $$ { {\bf{g} }_i}{\bf{ = A} }{ {\bf{x} }_i}{\bf{ - b} } \tag{5} $$ $$ { {\bf{x} }_{i + 1} } = { {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i} = {\bf{x}_i} + {\alpha _i}({\bf{A} }{ {\bf{x} }_i} - {\bf{b} }) \tag{6} $$ $$ \begin{array}{l} { {\bf{g} }_{i + 1} } &= {\bf{A} }{ {\bf{x} }_{i + 1} } - {\bf{b} }\\ &= {\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{b} } \tag{7} \end{array} $$ 那么有： $$ {\bf{g} }_i^T{ {\bf{g} }_{i + 1} } = {\bf{g} }_i^T{\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{g} }_i^T{\bf{b} } = 0 $$ $$ {\bf{g} }_i^T{\bf{A} }{ {\bf{x} }_i} + {\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} - {\bf{g} }_i^T{\bf{b} } = 0 $$ $$ {\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} + {\bf{g} }_i^T{ {\bf{g} }_i} = 0 $$ $$ {\alpha _i} = - \frac{ { {\bf{g} }_i^T{ {\bf{g} }_i} } }{ { {\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} } } \tag{8} $$

方法2

确定梯度方向$\bf{g}$后求解$\alpha$，由于最速下降法确定的是每一步方向上的局部最优解，也就是沿着这个方向运动得到最小值的位置，那么可以对$\alpha$求导，使得导数为0：

由$\eqref{1}$和$\eqref{3}$，有：

$$
f({\bf{x} }) = \frac{1}{2}{({\bf{x} } + \alpha {\bf{g} })^T}{\bf{A} }({\bf{x} } + \alpha {\bf{g} }) - { {\bf{b} }^{\bf{T} } }({\bf{x} } + \alpha {\bf{g} }) + {\bf{c} } \tag{9}
$$

对于已经确定的当前位置$\bf{x}_i$，当前可以看成是关于$\bf{x}_i$，$\alpha_i$的函数：

$$
f(\bf{x}_{i+1}) =f(\bf{x}_i,{\alpha _i}) = \frac{1}{2}{({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i})^T}{\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - { {\bf{b} }^{\bf{T} } }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) + {\bf{c} } \tag{10}
$$

对$\alpha_i$求偏导：

$$ \begin{array}{l} \frac{ {\partial f({ {\bf{x} }_{i + 1} })} }{ {\partial {\alpha _i} } } &= \frac{ {\partial f({ {\bf{x} }_{i + 1} })} }{ {\partial { {\bf{x} }_{i + 1} } } }\frac{ {\partial { {\bf{x} }_{i + 1} } } }{ {\partial {\alpha _i} } }\\ &= {({\bf{A} }{ {\bf{x} }_{i + 1} } - {\bf{b} })^T}{ {\bf{g} }_i}\\ &= {({\bf{A} }({ {\bf{x} }_i} + {\alpha _i}{ {\bf{g} }_i}) - {\bf{b} })^T}{ {\bf{g} }_i}\\ &= {({\bf{A} }{ {\bf{x} }_i} - {\bf{b} } + {\alpha _i}{\bf{A} }{ {\bf{g} }_i})^T}{ {\bf{g} }_i}\\ &= ({\bf{g} }_i^T + {\alpha _i}{\bf{g} }_i^T{\bf{A} }){ {\bf{g} }_i}\\ &= {\bf{g} }_i^T{ {\bf{g} }_i} + {\alpha _i}{\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} =0 \end{array} \tag{11} $$

得到：

$$
{\alpha _i} = - \frac{ { {\bf{g} }_i^T{ {\bf{g} }_i} } }{ { {\bf{g} }_i^T{\bf{A} }{ {\bf{g} }_i} } } \tag{12}
$$

下一个位置

按照公式$\eqref{3}$，获取下一个获取的位置$\bf{x}_{i+1}$
检测当前梯度大小，如果梯度小于一定阈值$\varepsilon$即认为已经达到了极小值：

$$
\varepsilon \ge \left| { { {\bf{g} }_{i+1} } } \right| \tag{13}
$$

否则再向前走下一步

分析

最速下降法是一种简单拟合当前问题的贪心优化方法，通过一步步计算局部最优解来逼近全局最优解，其本质为：
- 将当前的二次型拟合成高维球形
- 运动到拟合球形的中心
- 计算误差，测量精度
- 若精度不够则，根据误差拟合下一个高维球
首先，要声明的是，该方法是收敛的，也就是在我们定义的问题下，是可以逐步收敛到最优解的，证明比较复杂，参考番外篇(2)——无聊的最速下降法推导
该方法也存在一定问题，由于建模过于简单，导致其计算出的最优值结果与真实最小值不断遗漏下偏差，带来的结果就是需要往复迭代才能接近最优值