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

本文最后更新于:2022年8月10日 上午

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

问题描述

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

$$
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)——无聊的最速下降法推导

  • 该方法也存在一定问题,由于建模过于简单,导致其计算出的最优值结果与真实最小值不断遗漏下偏差,带来的结果就是需要往复迭代才能接近最优值

共轭梯度法的由来

  • 最速下降法拟合的方案过于简单,导致了该方法注定无法轻易得到全局最优解
  • 如果可以有正确拟合真实二次型的迭代优化方法,那么如果找到了这个模型下的最优值,岂不就迭代得到了全局最优解
  • 带着这个初衷,大神们提出了共轭梯度法

二次型优化问题 - 5 - 最速下降法
https://www.zywvvd.com/notes/study/machine-learning/conjugate-gradient-algorithm/steepest-descent-method/steepest-descent-method/
作者
Yiwei Zhang
发布于
2020年12月16日
许可协议