本文最后更新于:2024年5月7日 下午
本文介绍优化二次型的常用迭代方法——最速下降法。
问题描述
重述我们需要优化的问题:
$$
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$求偏导:
- 得到:
$$
{\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)——无聊的最速下降法推导
-
该方法也存在一定问题,由于建模过于简单,导致其计算出的最优值结果与真实最小值不断遗漏下偏差,带来的结果就是需要往复迭代才能接近最优值
共轭梯度法的由来
- 最速下降法拟合的方案过于简单,导致了该方法注定无法轻易得到全局最优解
- 如果可以有正确拟合真实二次型的迭代优化方法,那么如果找到了这个模型下的最优值,岂不就迭代得到了全局最优解
- 带着这个初衷,大神们提出了共轭梯度法
“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付