正定二次目标函数

$$min f(x) = \frac 1 2 x^T G x + r^T x + \sigma$$

非线性最小二乘

$$\begin{align*} f(x) & = \frac 1 2 \sum_{i=1}^m r^2_i(x) \\ & = \frac 1 2 r(x) r^T(x) \end{align*}$$

• $r_i(x)$：通常为非线性函数
• $r(x) = (r_1(x), \cdots, r_n(x))^T$
• $x \in R^n, m \geq n$

则

$$\begin{align*} \nabla f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) \\ & = J(x)^T r(x) \\ \nabla^2 f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) + \sum_{i=1}^m r_i \nabla^2 r_i(x) \\ & = J(x)^T J(x) + \sum_{i=1}^m r_i(x) \nabla^2 r_i(x) \end{align*}$$

• $$J(x) = \begin{bmatrix} \frac {\partial r_1} {\partial x_1} & \frac {\partial r_1} {\partial x_2} & \cdots & \frac {\partial r_1} {\partial x_n} \\ \frac {\partial r_2} {\partial x_1} & \frac {\partial r_2} {\partial x_2} & \cdots & \frac {\partial r_2} {\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac {\partial r_m} {\partial x_1} & \frac {\partial r_m} {\partial x_2} & \cdots & \frac {\partial r_m} {\partial x_n} \end{bmatrix} = \begin{bmatrix} \nabla r_1(x)^T \\ \nabla r_2(x)^T \\ \vdots \\ \nabla r_m(x)^T \\ \end{bmatrix}$$ 为$r(x)$的Jacobi矩阵

Gauss-Newton法

Newton法中为简化计算，略去其Hesse矩阵中 $\sum_{i=1}^m r_i(x) \nabla^2 r_i(x)$项，即直接求解 方程组

$$J(x^{(k)})^T J(x^{(k)}) d = -J(x^{(k)})^T r(x^{(k)})$$

算法

同Newton法，仅求解Newton方程改为求解以上方程组

特点

• 实际问题中

  • 局部解$x^{ }$对应的目标函数值$f(x^{ })$接近0 时，$|r(x^{(k)})|$较小
  • 曲线$r_i(x)$接近直线， $\nabla^2 r_i(x) \approx 0$

  采用Gauss-Newton法效果较好，否则效果一般

• 矩阵$J(x^{(k)})^T J(x^{(k)})$是半正定矩阵，当Jacobi矩阵 列满秩时为正定矩阵，此时虽然$d^{(k)}$是下降方向，但仍需 类似修正牛顿法增加一维搜索策略保证目标函数值不上升

Levenberg-Marquardt方法

但$J(x^{(k)})$中各列线性相关、接近线性相关，则求解 Newton-Gauss方法中的方程组会出现困难，可以改为求解

$$(J(x^{(k)})^T J(x^{(k)}) + vI) d = -J(x^{(k)})^T r(x^{(k)})$$

• $v$：迭代过程中需要调整的参数，LM方法的关键即如何调整

定理1

• 若$d(v)$是以上方程组的解，则$|d(v)|^2$是$v$的连续下降 函数，且$v \rightarrow +\infty, |d(v)| \rightarrow 0$

• $J(x^{(k)})^T J(x^{(k)})$是对称半正定矩阵，则存在正交阵

  $$(P^{(k)})^T J(x^{(k)})^T J(x^{(k)}) P^{(k)} = \Lambda^{(k)}$$

• 则可以解出$|d(v)|^2$

• 增大$v$可以限制$|d^{(k)}|$，所以LM方法也被称为阻尼最小 二乘法

定理2

• 若$d(v)$是以上方程的解，则$d(v)$是$f(x)$在$x^{(k)}$处的 下降方向，且$v \rightarrow + \infty$时，$d(v)$的方向与 $-J(x^{(k)})^T r(x^{(k)})$方向一致

• 下降方向：$\nabla f(x^{(k)}) d(v) < 0$即可
• 方向一致：夹角余弦

• $v$充分大时，LM方法产生的搜索方向$d^{(k)}$和负梯度方向 一致

参数调整方法

使用梯度、近似Hesse矩阵定义二次函数

$$q(d) = f(x^{(k)}) + (J(x^{(k)})^T r(x^{(k)}))^T d + \frac 1 2 d^T (J(x^{(k)})^T J(x^{(k)})) d$$

• 其增量为

  $$\begin{align*} \Delta q^{(k)} & = q(d^{(k)}) - q(0) \\ & = (J(x^{(k)})^T r(x^{(k)}))^T d^{(k)} + \frac 1 2 (d^{(k)})^T (J(x^{(k)})^T J(x^{(k)})) d^{(k)} \end{align*}$$

• 目标函数增量

  $$\begin{align*} \Delta f^{(k)} & = f(x^{(k)} + d^{(k)}) - f(x^{(k)}) \\ & = f(x^{(k+1)}) - f(x^{(k)}) \end{align*}$$

• 定义$\gamma_k = \frac {\Delta f^{(k)}} {\Delta q^{(k)}}$

• $\gamma_k$接近1说明$\Delta f^{(k)}$接近$\Delta q^{(k)}$

  • 即$f(x^{(k)} + d^{(k+1)})$接近$q(d^{(k)})$
  • 即$f(x)$在$x^{(k)}$附近接近二次函数
  • 即使用Gauss-Newton方法求解最小二乘问题效果较好
  • 即LM方法求解时$v$参数应该较小

• $\gamma_k$接近0说明$\Delta f^{(k)}$与$\Delta q^{(k)}$ 近似程度不好

  • $d^{(k)}$不应取得过大，应减少$d^{(k)}$得模长
  • 应该增加参数$v$进行限制
  • 迭代方向趋近于负梯度方向

• $\gamma_k$适中时，认为参数$v$选取合适，不做调整

  • 临界值通常为0.25、0.75

算法

1. 初始点$x^{(1)}$、初始参数$v$（小值）、精度要求$\epsilon$ ，置k=k+1

2. 若$|J(x^{(k)})^T r(x^{(k)})| < \epsilon$，则停止计算， 得到问题解$x^{(k)}$，否则求解线性方程组

   $$(J(x^{(k)})^T J(x^{(k)}) + v_kI) d = -J(x^{(k)})^T r(x^{(k)})$$

   得到$d^{(k)}$

3. 置$x^{(k+1)} = x^{(k)} + d^{(k)}$，计算$\gamma_k$

4. 若

   • $\gamma < 0.25$，置$v_{k+1} = 4 v_k$
   • $\gamma > 0.75$，置$v_{k+1} = v_k / 2$
   • 否则置$v_{k+1} = v_k$

5. 置k=k+1，转2

Langrangian Duality

拉格朗日对偶

• 考虑优化问题：找到$f(x)$满足约束的最好下界

  $$z^{*} = \min_{x} f(x) \\ \begin{align*} s.t. \quad & g_i(x) \leq 0, i=1,2,\cdots,m \\ & x \in X \end{align*}$$

• 考虑方程组

  $$\left \{ \begin{array}{l} f(x) < v \\ g_i(x) \leq 0, i=1,2,\cdots,m \end{array} \right.$$

  • 方程组无解：$v$是优化问题的一个下界

  • 方程组有解：则可以推出

    $$\forall \lambda \geq 0, \exists x, f(x) + \sum_{i=1}^m \lambda_ig_i(x) < v$$

    • 显然，取$g_1 + g_2 = 0, g_1(x) > 0$是反例，不能 推出原方程有解

  • 由以上方程组有解逆否命题：方程组无解充分条件如下

    $$\exists \lambda \geq 0, \min_{x} f(x) + \sum _{i=1}^m \lambda_ig_i(x) \geq v$$

• 由此方法推出的最好下界，即拉格朗日对偶问题

  $$v^{*} = \max_{\lambda \geq 0} \min_{x} f(x) + \sum_{i=1}^m \lambda_ig_i(x)$$

说明

• 拉格朗日对偶对实数域上的优化问题都存在，对目标函数、 约束函数都没有要求

• 强对偶定理：$v^{} = z^{}$，需要$f,g$满足特定条件才成立

  • 线性规划
  • 半正定规划
  • 凸优化

  • 即需要给约束条件加以限制，使得 $$\forall \lambda \geq 0, \exists x, f(x) + \sum_{i=1}^m \lambda_ig_i(x) < v$$ 是上述方程组有解的冲要条件

• 弱对偶定理：$v^{} \leq z^{}$，永远成立（以上即可证）

  • 通过弱对偶定理，可以得到原问题的一个下界
  • 对求解原问题有帮助，比如：分支界限法中快速求下界

• 对偶问题相关算法往往原问题算法在实际应用中往往更加有效

  • dual-simplex
  • primal-dual interior point method
  • augmented Lagrangian Method

原始问题

约束最优化问题

$$\begin{array}{l} \min_{x \in R^n} & f(x) \\ s.t. & c_i(x) \leq 0, i = 1,2,\cdots,k \\ & h_j(x) = 0, j = 1,2,\cdots,l \end{array}$$

Generalized Lagrange Function

• 引入Generalized Lagrange Function

  $$L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)$$

  • $x=(x_1, x_2, \cdots, x_n) \in R^n$
  • $\alpha_i \geq 0, \beta_j$：拉格朗日乘子

• 考虑关于x的函数

  $$\theta_P(x) = \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)$$

  • $P$：primal，原始问题

  • 若x满足原始问题的两组约束条件，则$\theta_P(x)=f(x)$

  • 若x违反等式约束j，取$\beta_j \rightarrow \infty$， 则有$\theta_P(x) \rightarrow \infty$

  • 若x违反不等式约束i，取$\alpha_i \rightarrow \infty$ ，则有$\theta_P(x) \rightarrow \infty$

  则有

  $$\theta_P(x) = \left \{ \begin{array}{l} f(x), & x 满足原始问题约束条件 \\ +\infty, & 其他 \end{array} \right.$$

• 则极小化问题，称为广义拉格朗日函数的极小极大问题

  $$\min_x \theta_P(x) = \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)$$

  与原始最优化问题等价，两问题最优值相同，记为

  $$p^{*} = \min_x \theta_P(x)$$

对偶问题

• 定义

  $$\theta_D (\alpha, \beta) = \min_x L(x, \alpha, \beta)$$

• 再考虑极大化$\theta_D(\alpha, \beta)$，得到广义拉格朗日 函数的极大极小问题，即

  $$\max_{\alpha, \beta: \alpha \geq 0} \theta_D(\alpha, \beta) = \max_{\alpha, \beta: \alpha \geq 0} \min_x L(x, \alpha, \beta)$$

  表示为约束最优化问题如下

  $$\begin{align*} \max_{\alpha, \beta} & \theta_D(\alpha, \beta) = \max_{\alpha, \beta} \min_x L(x, \alpha, \beta) \\ s.t. & \alpha_i \geq 0, i=1,2,\cdots,k \end{align*}$$

  称为原始问题的对偶问题，其最优值定义记为

  $$d^{*} = \max_{\alpha, \beta: \alpha \geq 0} \theta_D(\alpha, \beta)$$

原始、对偶问题关系

定理1

• 若原始问题、对偶问题都有最优值，则 $$d^{*} = \max_{\alpha, \beta: \alpha \geq 0} \min_x L(x, \alpha, \beta) \leq \min_x \max_{\alpha, \beta: \alpha \geq 0} L(x, \alpha, \beta) = p^{*}$$

• $\forall x, \alpha, \beta$有

  $$\theta_D(\alpha, \beta) = \min_x L(x, \alpha, \beta) \leq L(x, \alpha, \beta) \leq \max_{\alpha, \beta: \alpha \geq 0} = \theta_P(x)$$

  即

  $$\theta_D(\alpha, \beta) \leq \theta_P(x)$$

• 而原始、对偶问题均有最优值，所以得证

• 设$x^{}$、$\alpha^{}, \beta^{}$分别是原始问题、对偶 问题的可行解，且$d^{} = p^{*}$，则其分别是原始问题、 对偶问题的最优解

思想：最速下降&牛顿

对目标函数$f(x)$在$x^{(1)}$进行展开

$$f(x) = f(x^{(1)}) + \nabla f(x^{(1)})(x - x^{(1)})+ \frac 1 2 \nabla^2 f(x^{(1)})(x - x^{(1)})^2 + o((x - x^{(1)})^2)$$

• 最速下降法：只保留一阶项，即使用线性函数近似原目标函数
• Newton法：保留一阶、二阶项，即使用二次函数近似

• 利用近似函数求解元素问题极小值

  • 最速下降法：线性函数无极值，需要确定步长、迭代
  • Newton法：二次函数有极值，直接求导算出极值、迭代

• 最速下降法

  • 只考虑一阶导：甚至说根本没有考虑拟合原目标函数

• Newton法

  • 考虑二阶导：每步迭代还考虑了二阶导，即当前更新完毕 后，下一步能够更好的更新（二阶导的意义）
  • 甚至从后面部分可以看出，Newton法甚至考虑是全局特征， 不只是局部性质（前提目标函数性质足够好）
  • 二次函数拟合更接近函数极值处的特征

最速下降算法

思想

• 设$x=x(t)$为最优点$x$从初始点、沿负梯度方向经过的曲线， 则有

  $$\left \{ \begin{array}{l} & \frac {dx(t)} {dt} = -\nabla f(x(t)) \\ & x(t_1) = x^{(1)} \end{array} \right.$$

  • $t_1, x^{(1)}$：初始时刻、初始位置

• 可以证明，$x(t)$解存在，且$t \rightarrow \infty$时，有 $x(t) \rightarrow x^{ * }$，即得到无约束问题最优解

• 但微分方程组求解可能很麻烦，可能根本无法求解

  • 考虑将以上曲线离散化，每次前进到“不应该”前进为止
  • 然后更换方向，逐步迭代得到最优解

算法

• 搜索方向最速下降方向：负梯度方向
• 终止准则：$\nabla f(x^{(k)})=0$

1. 取初始点$x^{(1)}$，置k=1

2. 若$\nabla f(x^{(k)})=0$，则停止计算，得到最优解， 否则置

   $$d^{(k)} = -\nabla f(x^{(k)})$$

   以负梯度作为前进方向

3. 一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

   得$\alpha_k$前进步长，置

   $$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$$

4. 置k=k+1，转2

• 最速下降算法不具有二次终止性

叠加惯性

模拟物体运动时惯性：指数平滑更新步长

Momentum

冲量方法：在原始更新步上叠加上次更新步，类似指数平滑

$$v^{(t)} = \gamma v^{(t-1)} + (1 - \gamma) \eta \bigtriangledown_\theta L(\theta^{(t-1)}) \\ \theta^{(t)} = \theta^{(t-1)} - v^{(t)}$$

• $v^{(t)}$：第$t$步时第k个参数更新步
• $L(\theta)$：往往是batch损失函数

• 更新参数时，一定程度保持上次更新方向
• 可以在一定程度上保持稳定性，学习速度更快
• 能够越过部分局部最优解

Nesterov Momentum

NGA：在使用冲量修正最终方向基础上，使用冲量对当前 参数位置进行修正，即使用“未来”位置计算梯度

• 先使用冲量更新一步
• 再在更新后位置计算新梯度进行第二步更新

$$v^{(t)} = \gamma v^{(t-1)} + \eta \bigtriangledown_\theta L(\theta^{(t-1)} - \gamma v^{(t-1)}) \\ \theta^{(t)} = \theta^{(t-1)} - v^{(t)}$$

动态学习率

• 学习率太小收敛速率缓慢、过大则会造成较大波动
• 在训练过程中动态调整学习率大小较好

• 模拟退火思想：达到一定迭代次数、损失函数小于阈值时，减小 学习速率

Vanilla Gradient Descent

每次迭代减小学习率$\eta$

$$\eta^{(t)} = \frac \eta {\sqrt {t+1}} \\ \theta^{(t)} = \theta^{(t-1)} - \eta^{(t)} \bigtriangledown_\theta L(\theta^{(t-1)})$$

• 学习率逐渐减小，避免学习后期参数在最优解附近反复震荡

Adagrad

adaptive gradient：训练中不同参数学习率随着迭代次数、 梯度动态变化，使得参数收敛更加平稳

$$v^{(t)}_k = \bigtriangledown_{\theta_k} L(\theta^{(t-1)}) \\ \theta^{(t)}_k = \theta^{(t-1)}_k - \frac \eta {\sqrt {\sum_{i=0}^{t-1} (v^{(i)}_k)^2 + \epsilon}} v^{(t)}_k$$

• $\epsilon$：fuss factor，避免分母为0
• $\theta^{(t)}_k$：第t轮迭代完成后待估参数第k个分量 （之前未涉及参数间不同，统一为向量）

• 特点

  • 较大梯度参数真正学习率会被拉小；较小梯度真正学习率 参数被拉小幅度较小
  • 可以和异步更新参数结合使用，给不常更新参数更大学习率

• 缺点

  • 在训练后期，分母中梯度平方累加很大，学习步长趋于0， 收敛速度慢（可能触发阈值，提前结束训练）

RMSprop

root mean square prop：指数平滑更新学习率分母

$$v^{(t)}_k = \bigtriangledown_{\theta_k} L(\theta^{(t-1)}) \\ \theta^{(t)}_k = \theta^{(t-1)}_k - \frac \eta {\sqrt { \gamma \sum_{i=1}^{t-1}(v^{(i)}_k)^2 + (1 - \gamma)((v^{(t)})^2 + \epsilon} } v^{(t)}$$

• 赋予当前梯度更大权重，减小学习率分母，避免学习速率下降 太快

Adam

adptive moment estimation：指数平滑更新步、学习率分母

$$\begin{align*} v^{(t)}_k & = \gamma_1 v^{(t-1)}_k + (1 - \gamma_1) \bigtriangledown_{\theta_k} L(\theta^{(t-1)}) \\ s^{(t)}_k & = \gamma_2 s^{(t-1)}_k + (1 - \gamma_2) \bigtriangledown_{\theta_k} L(\theta^{(t-1)})^2 \\ \hat{v^{(t)}_k} & = \frac {v^{(t)}_k} {1 - \gamma_1^t} \\ \hat{s^{(t)}_k} & = \frac {s^{(t)}_k} {1 - \gamma_2^t} \\ \theta^{(t)}_k & = \theta^{(t-1)}_k - \frac \eta {\sqrt{\hat{s^{(t)}_k} + \epsilon}} \hat{v^{(t)}_k} \end{align*}$$

• $\gamma_1$：通常为0.9
• $\gamma_2$：通常为0.99
• $\hat{v^{(t)}_k} = \frac {v^{(t)}_k} {1 - \gamma_1^t}$ ：权值修正，使得过去个时间步，小批量随机梯度权值之和为1

• 利用梯度的一阶矩$v^{(t)}$、二阶矩$s^{(t)}$动态调整每个 参数学习率

• 类似于mommentum、RMSprop结合

• 经过偏执矫正后，每次迭代学习率都有确定范围，参数比较平稳

Adadelta

指数平滑更新学习率（分子）、学习率分母

$$\begin{align*} s^{(t)}_k & = \gamma_1 s^{(t-1)}_k + (1 - \gamma_1) \bigtriangledown_{\theta_k} L(\theta^{(t-1)})^2 \\ \hat{v^{(t)}_k} & = \sqrt {\frac {\Delta \theta^{(t-1)}_k + \epsilon} {s^{(t)}_k + \epsilon}} \bigtriangledown_{\theta_k} L(\theta^{(t-1)})^2 \\ \Delta \theta^{(t)}_k & = \gamma_1 \Delta \theta^{(t-1)}_k + (1 - \gamma_1) \hat{v^{(t)}_k}^2 \\ \theta^{(t)}_k & = \theta^{(t)}_k - \hat{v^{(t)}_k} \end{align*}$$

• $s, \Delta \theta$共用超参$\gamma_1$

• 在RMSprop基础上，使用$\sqrt {\Delta \theta}$作为学习率
• $\hat v$：中超参$\gamma_1$在分子、分母“抵消”，模型对 超参不敏感

样本量

Singular Loss/Stocastic Gradient Descent

SGD：用模型在某个样本点上的损失极小化目标函数、计算梯度、 更新参数

• 单点损失度量模型“一次”预测的好坏

  • 代表模型在单点上的优劣，无法代表模型在总体上性质
  • 具有很强随机性

• 单点损失不常用，SGD范围也不局限于单点损失

• 损失函数具体参见ml_xxxxx

全局估计

全局损失：用模型在全体样本点上损失极小化目标函数、计算梯度、 更新参数

$$\theta^{(t)} = \theta^{(t-1)} - \eta \bigtriangledown_\theta L_{total}(\theta_{(t-1)})$$

• $\theta^{(t)}$：第t步迭代完成后待估参数
• $\eta$：学习率
• $L{total}(\theta) = \sum{i=1}^N L(\theta, x_i, y_i)$： 训练样本整体损失
• $N$：训练样本数量

• 若损失函数有解析解、样本量不大，可一步更新（计算） 完成（传统参数估计场合）

  • 矩估计
  • 最小二乘估计
  • 极大似然估计

• 否则需要迭代更新参数

  • 样本量较大场合
  • 并行计算

Mini-Batch Loss

mini-batch loss：用模型在某个batch上的损失极小化目标函数、 计算梯度、更新参数

$$\theta^{(t)} = \theta^{(t-1)} - \eta \bigtriangledown_\theta L_{batch}(\theta^{(t-1)})$$

• $L{batch}(\theta)=\sum{i \in B} L(\theta, x_i, y_i)$： 当前batch整体损失
• $B$：当前更新步中，样本组成的集合batch

• batch-loss是模型在batch上的特征，对整体的代表性取决于 batch大小

  • batch越大对整体代表性越好，越稳定；越小对整体代表 越差、不稳定、波动较大、难收敛
  • batch大小为1时，就是SGD
  • batch大小为整个训练集时，就是经验（结构）风险

• batch-loss是学习算法中最常用的loss，SGD优化常指此

  • 实际中往往是使用batch-loss替代整体损失，表示经验风险 极小化
  • batch-loss同样可以带正则化项，表示结构风险极小化
  • 损失极值：SVM（几何间隔最小）

优点

• 适合样本量较大、无法使用样本整体估计使用
• 一定程度能避免局部最优（随机batch可能越过局部极值）
• 开始阶段收敛速度快

缺点

• 限于每次只使用单batch中样本更新参数，batch-size较小时， 结果可能不稳定，往往很难得到最优解

• 无法保证良好的收敛性，学习率小收敛速度慢，学习率过大 则损失函数可能在极小点反复震荡

• 对所有参数更新应用相同学习率，没有对低频特征有优化 （更的学习率）

• 依然容易陷入局部最优点

Newton法

思想

• 若$x^{ * }$是无约束问题局部解，则有

  $$\nabla f(x^{ * }) = 0$$

  可求解此问题，得到无约束问题最优解

• 原始问题是非线性，考虑求解其线性逼近，在初始点$x^{(1)}$ 处泰勒展开

  $$\nabla f(x) \approx \nabla f(x^{(1)}) + \nabla^2 f(x^{(1)})(x - x^{(1)})$$

  解得

  $$x^{(2)} = x^{(1)} - (\nabla^2 f(x^{(1)}))^{-1} \nabla f(x^{(1)})$$

  作为$x^{ * }$的第二次近似

• 不断迭代，得到如下序列

  $$x^{(k+1)} = x^{(k)} + d^{(k)}$$

  • $d^{(k)}$：Newton方向，即以下方程解 $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

算法

• 初始点 $x^{(1)}$、精度要求 $\epsilon$，置 $k=1$

• 考虑 $|\nabla f(x^{(k)})| \leq \epsilon$

  • 若满足，则停止计算，得到最优解 $x^{(k)}$

  • 否则求解如下方程，得到 $d^{(k)}$

    $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

• 如下设置，并转2

  $$x^{(k+1)} = x^{(k)} + d^{(k)}, k = k+1$$

特点

• 优点

  • 产生点列 ${x^{k}}$ 若收敛，则具有二阶收敛速率
  • 具有二次终止性，事实上对正定二次函数，一步即可收敛

• 缺点

  • 可能会在某步迭代时目标函数值上升
  • 当初始点 $x^{(1)}$ 距离最优解 $x^{ * }$ 时，产生的点列 可能不收敛，或者收敛到鞍点
  • 需要计算 Hesse 矩阵
    • 计算量大
    • Hesse 矩阵可能不可逆，算法终止
    • Hesse 矩阵不正定，Newton 方向可能不是下降方向

阻尼/修正 Newton 法

• 克服 Newton 法目标函数值上升的缺点
• 一定程度上克服点列可能不收敛缺点

算法

• 初始点 $x^{(1)}$、精度要求 $\epsilon$，置 $k=1$

• 考虑 $|\nabla f(x^{(k)})| \leq \epsilon$

  • 若满足，停止计算，得到最优解 $x^{(k)}$
  • 否则求解如下方程得到 $d^{(k)}$ $$\nabla^2 f(x^{(k)}) d = -\nabla f(x^{(k)})$$

• 一维搜索，求解一维问题

  $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

  得到 $\alpha_k$，如下设置并转2

  $$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}, k = k+1$$

其他改进

• Newton 法、修正 Newton 法的改进方向
  • 结合最速下降方向修正迭代方向
  • Hesse 矩阵不正定情形下的替代

结合最速下降方向

• 将 Newton 方向和最速下降方向结合

• 设 $\theta_k$ 是 $$ 之间夹角，显然希望 $\theta < \frac \pi 2$

• 则置限制条件 $\eta$，取迭代方向

  $$d^{(k)} = \left \{ \begin{array}{l} d^{(k)}, & cos\theta_k \geq \eta \\ -\nabla f(x^{(k)}), & 其他 \end{array} \right.$$

Negative Curvature

• 当 Hesse 矩阵非正定时，选择负曲率下降方向 $d^{(k)}$（一定存在）

• Hesse 矩阵非正定时，一定存在负特征值、相应特征向量 $u$

  • 取负曲率下降方向作为迭代方向

    $$d^{(k)} = -sign(u^T \nabla f(x^{(k)})) u$$

  • $x^{(k)}$ 处负曲率方向 $d^{(k)}$ 满足

    $${d^{(k)}}^T \nabla^2 f(x^{(k)}) d^{(k)} < 0$$

修正 Hesse 矩阵

• 取迭代方向 $d^{(k)}$ 为以下方程的解

  $$(\nabla^2 f(x^{(k)}) + v_k I) d = -\nabla f(x^{k})$$

• $v_k$：大于 $\nabla^2 f(x^{(k)})$ 最大负特征值绝对值

综述

拟Newton法/变度量法：不需要求解Hesse矩阵，使用一阶导构造 二阶信息的近似矩阵

• 使用迭代过程中信息，创建近似矩阵$B^{(k)}$代替Hesse矩阵

• 用以下方程组替代Newton方程，其解$d^{(k)}$作为搜索方向

  $$B^{(k)} d = - \triangledown f(x^{(k)})$$

思想

• 考虑$\triangledown f(x)$在$x^{(k+1)}$处泰勒展开

  $$\triangledown f(x) \approx \triangledown f(x^{(k+1)}) + \triangledown^2 f(x^{(k+1)})(x - x^{(k+1)})$$

• 取$x = x^{(k)}$，有

  $$\begin{align*} \triangledown f(x^{(k+1)}) - \triangledown f(x^{(k)}) & \approx \triangledown^2 f(x^{(x+1)}) (x^{(k+1) } - x^{(k)}) \\ \triangledown^2 f(x^{k+1}) s^{(k)} & \approx y^{(k)} \end{align*}$$

  • $s^{(k)} = x^{(k+1)} - x^{(k)}$
  • $y^{(k)} = \triangledown f(x^{(k+1)}) - \triangledown f(x^{(k)})$

• 要求$B^{(k)}$近似$\triangledown^2 f(x^{(k)})$，带入并将 $\approx$改为$=$，得到拟Newton方程

  $$B^{(k+1)} s^{(k)} = y^{(k)}$$

  并假设$B^{(k)}$对称

• 拟Newton方程不能唯一确定$B^{(k+1)}$，需要附加条件，自然 的想法就是$B^{(k+1)}$可由$B^{(k)}$修正得到，即

  $$B^{(k+1)} = B^{(k)} + \Delta B^{(k)}$$

  且修正项$\Delta B^{(k)}$具有“简单形式”

Hesse矩阵修正

对称秩1修正

认为简单指矩阵秩小：即认为$\Delta B^{(k)}$秩为最小值1

• 设$\Delta B^{(k)} = u v^T$，带入有

  $$\begin{align*} y^{(k)} & = B^{(k+1)} s^{(k)} \\ & = B^{(k)} s^{(k)} + (v^T s^{(k)}) u \\ y^{(k)} - B^{(k)} s^{(k)} & = (v^T s^{(k)}) u \end{align*}$$
  • 这里有的书会设$\Delta B^{(k)} = \alpha u v^T$， 其实对向量没有必要
  • $v^T s^{(k)}$是数，所以$u$必然与共线，同理也没有必要 考虑系数，直接取相等即可
  • 而且系数不会影响最终结果

• 可取$u = y^{(k)} - B^{(k)} s{(k)}$，取$v$满足 $v^T s^{(k)} = 1$

• 由$B^{(k)}$的对称性、并希望$B^{(k+1)}$保持对称，需要 $u, v$共线，则有

  $$\begin{align*} v & = \lambda u = \lambda (y^{(k)} - B^{(k)} s^{(k)}) \\ 1 & = \lambda (y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)} \end{align*}$$

• 得到$B^{(k)}$的对称秩1修正公式

  $$B^{(k+1)} = B^{(k)} + \frac {(y^{(k) - B^{(k)} s^{(k)}}) (y^{(k)} - B^{(k)} s^{(k)})^T} {(y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)}}$$

算法

1. 初始点$x^{(1)}$、初始矩阵$B^{(1)} = I$、精度要求 $\epsilon$、置$k=1$

2. 若$|\triangledown f(x^{(k)})| \leq \epsilon$，停止计算 ，得到解$x^{(k)}$，否则求解以下方程得到$d^{(k)}$

   $$B^{(k)} d = -\triangle f(x^{(k)})$$

3. 一维搜索，求解

   $$\arg\min_{\alpha} \phi(\alpha)=f(x^{(k)} + \alpha d^{(k)})$$

   得到$\alpha_k$，置$x^{(k+1)}=x^{(k)} + \alpha_k d^{(k)}$

4. 修正$B^{(k)}$

   $$\begin{align*} s^{(k)} & = x^{(k+1)} - x^{(k)} \\ y^{(k)} & = \triangledown f(x^{(k+1)}) - \triangledown f(x^{(k)}) \\ B^{(k+1)} & = B^{(k)} + \frac {(y^{(k) - B^{(k)} s^{(k)}}) (y^{(k)} - B^{(k)} s^{(k)})^T} {(y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)}} \end{align*}$$

5. 置$k = k+1$，转2

特点

• 缺点

  • 要求$(y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)} \neq 0$， 否则无法继续计算

  • 不能保证正定性传递，只有 $(y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)} > 0$才能保证 $B^{(k+1)}$也正定

  • 即使$(y^{(k)} - B^{(k)} s^{(k)})^T s^{(k)} > 0$， 也可能很小，容易产生较大的舍入误差

对称秩2修正

• 为克服秩1修正公式缺点，考虑$\Delta B^{(k)}$秩为2，设

  $$\Delta B^{(k)} = u^{(1)} (v^{(1)})^T + u^{(2)} (v^{(2)})^T$$

• 带入拟Newton方程有

  $$B^{(k)} s^{(k)} + ((v^{(1)})^T s^{(k)}) u^{(1)} + ((v^{(2)})^T s^{(k)}) u^{(2)} = y^{(k)}$$

• 类似的取

  $$\left \{ \begin{array}{l} u^{(1)} = y^{(k)} \\ (v^{(1)})^T s^{(k)} = 1 \end{array} \right.$$ $$\left \{ \begin{array}{l} u^{(2)} = -B^{(k)} s^{(k)} \\ (v^{(2)})^T s^{(k)} = 1 \end{array} \right.$$

• 同秩1公式保持对称性推导，得到对称秩2修正公式/BFGS公式

  $$B^{(k+1)} = B^{(k)} - \frac {B^{(k)} s^{(k)} (s^{(k)})^T B^{(k)}} {(s^{(k)})^T B^{(k)} s^{(k)}} + \frac {y^{(k)} (y^{(k)})^T} {(y^{(k)})^T s^{(k)}}$$

BFGS算法

类似同秩1修正算法，仅第4步使用对称秩2修正公式

Hesse逆修正

对称秩2修正

• 考虑直接构造近似于$(\triangledown^2 f(x^{(k)}))^{-1}$的 矩阵$H^{(k)}$

• 这样无需求解线性方程组，直接计算

  $$d^{(k)} = -H^{(k)} \triangledown f(x^{(k)})$$

• 相应拟Newton方程为

  $$H^{(k+1)} y^{(k)} = s^{(k)}$$

• 可得$H^{(k)}$的对称秩1修正公式

  $$H^{(k+1)} = H^{(k)} + \frac {(s^{(k)} - H^{(k)} y^{(k)}) (s^{(k)} - H^{(k)} y^{(k)})T} {(s^{(k)} - H^{(k)} y^{(k)})^T y^{(k)}}$$

• 可得$H^{(k)}$的对称秩2修正公式/DFP公式

  $$H^{(k+1)} = H^{(k)} - \frac {H^{(k)} y^{(k)} (y^{(k)})^T H^{(k)}} {(y^{(k)})^T H^{(k)} y^{(k)}} + \frac {s^{(k)} (s^{(k)})^T} {(s^{(k)})^T y^{(k)}}$$

DFP算法

类似BFGS算法，只是

• 使用$H^{(k)}$计算更新方向
• 使用$H^{(k)}$的对称秩2修正公式修正

• 对正定二次函数，BFGS算法和DFP算法效果相同
• 对一般可微（非正定二次函数），一般认为BFGS算法在收敛性质 、数值计算方面均由于DFP算法

Hesse逆的BFGS算法

• 考虑

  $$\begin{align*} B^{(k+1)} & = B^{(k)} + u^{(1)} (v^{(1)})^T + u^{(2)} (v^{(2)})^T \\ H^{(k+1)} & = (B^{(k+1)})^{-1} \\ & = (B^{(k)} + u^{(1)} (v^{(1)})^T + u^{(2)} (v^{(2)})^T)^{-1} \\ \end{align*}$$

• 两次利用Sherman-Morrison公式，可得

  $$H^{(k+1)} = (I - \frac {s^{(k)} (y^{(k)})^T} {(y^{(k)})^T s^{(k)}}) H^{(k)} (I - \frac {s^{(k)} (y^{(k)})^T} {(y^{(k)})^T s^{(k)}})^T + \frac {s^{(k)} (s^{(k)})^T} {(y^{(k)})^T s^{(k)}}$$

todo

• 还可以进一步展开

  $$H^{(k+1)} = H^{(k)} + (\frac 1 {(s^{(k)})^T y^{(k)}} + \frac {(y^{(k)})^T H^{(k)} y^{(k)}} {((s^{(k)})^T y^{(k)})^2}) s^{(k)} (s^{(k)})^T - \frac 1 {(s^{(k)})^T y^{(k)}} (H^{(k)} y^{(k)} (s^{(k)})^T + s^{(k)} (y^{(k)})^T H^{(k)})$$

变度量法的基本性质

算法的下降性

定理1

• 设$B^{(k)}$（$H^{(k)}$）是正定对称矩阵，且有 $(s^{(k)})^T y^{(k)} > 0$，则由BFGS（DFS）公式构造的 $B^{(k+1)}$（$H^{(k+1)}$）是正定对称的

• 考虑$B^{(k)}$对称正定，有 $B^{(k)} = (B^{(k)})^{1/2} (B^{(k)})^{1/2}$

• 带入利用柯西不等式即可证

• 中间插入正定矩阵的向量内积不等式也称为广义柯西不等式

定理2

• 若$d^{(k)}$v是下降方向，且一维搜索是精确的，设 $B^{(k)}$（$H^{(k)}$）是正定对称矩阵，则有BFGS（DFP） 公式构造的$B^{(k+1)}$（$H^{(k+1)}$）是正定对称的

• 精确一维搜索$(d^{(k)})^T \triangledown f(x^{(k+1)}) = 0$
• 则有$(s^{(k)})^T y^{(k)} > 0$

定理3

• 若用BFGS算法（DFP算法）求解无约束问题，设初始矩阵 $B^{(1)}$（$H^{(1)}$）是正定对称矩阵，且一维搜索是精确的 ，若$\triangledown f(x^{(k)}) \neq 0$，则产生搜索方向 $d^{(k)}$是下降方向

• 结合上2个结论，数学归纳法即可

总结

• 若每步迭代一维搜索精确，或满足$(s^{(k)})^T y^{(k)} > 0$

  • 停止在某一稳定点
  • 或产生严格递减的序列${f(x^{(k)})}$

• 若目标函数满足一定条件我，可以证明变度量法产生的点列 ${x^{(k)}}$收敛到极小点，且收敛速率超线性

搜索方向共轭性

• 用变度量法BFGS（DFP）算法求解正定二次函数

$$
min f(x) = \frac 1 2 x^T G x + r^T x + \sigma
$$

若一维搜索是精确的，假设已经进行了m次迭代，则

• 搜索方向$d^{(1)}, \cdots, d^{(m)}$是m个非零的G共轭方向

• 对于$j = 1, 2, \cdots, m$，有

$$
B^{(m+1)} s^{(j)} = y^{(j)}
(H^{(m+1)} y^{(j)} = s^{(j)})
$$

且$m = n$时有吧

$$
B^{(n+1)} = G(H^{(n+1)} = G^{-1})
$$

变度量法二次终止

• 若一维搜索是精确的，则变度量法（BFGS、DFP）具有二次终止

• 若$\triangle f(x^{(k)}) = 0, k \leq n$，则得到最优解 $x^{(k)}$

• 否则得到的搜索方向是共轭的，由扩展空间子定理， $x^{(n+1)}$是最优解

共轭方向

• 设G为$n * n$阶正定对称矩阵，若$d^{(1)}, d^{(2)}$满足

  $$(d^{(1)})^T G d^{(2)} = 0$$

  则称$d^{(1)}, d^{(2)}$关于G共轭

• 类似正交方向，若$d^{(1)},\cdots,d^{(k)}(k \leq n)$关于 G两两共轭，则称其为G的k个共轭方向

• 特别的，$G=I$时，共轭方向就是正交方向

定理1

• 设目标函数为 $$f(w) = \frac 1 2 w^T w + r^T w + \sigma$$ $q^{(1)}, \cdots, q^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$w^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$w^{(1)}, \cdots, w^{(k+1)}$， 则$w^{(k+1)}$是$f(w)$在线性流形 $$\bar W_k = \{w = w^{(1)} + \sum_{i=1}^k \alpha_i q^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$w^{(n+1)}$是$f(w)$在整个 空间上的唯一极小点

• $\bar W_k$上的存在唯一极小点$\hat w^{(k)}$，在所有方向 都是极小点，所以有

  $$<\triangledown f(\hat w^{(k)}), q^{(i)}> = 0, i=1,2,..$$

• 将$\hat w^{(k)}$由正交方向表示带入梯度，求出系数表达式

• 解精确搜索步长，得到$w^{(k+1)}$系数表达式

扩展子空间定理

• 设目标函数为 $$f(w) = \frac 1 2 x^T G x + r^T x + \sigma$$ $d^{(1)}, \cdots, d^{(k)}$是$k, k \leq n$个非零正交方向 ，从任意初始点$x^{(1)}$出发，依次沿着以上正交方向做 精确一维搜索，得到$x^{(1)}, \cdots, x^{(k+1)}$， 则$x^{(k+1)}$是$f(x)$在线性流形 $$\bar x_k = \{x = x^{(1)} + \sum_{i=1}^k \alpha_i d^{(i)} | -\infty < \alpha_i < +\infty \}$$ 上的唯一极小点，特别的k=n时，$x^{(n+1)}$是$f(x)$在整个 空间上的唯一极小点

• 引进变换$w = \sqrt G x$即可证

• 在以上假设下，有 $$<\triangledown f(x^{(k+1)}), d^{(i)}> = 0, i=1,2...$$

Conjugate Gradient Method

共轭梯度法

对正定二次函数函数

$$f(x) = \frac 1 2 x^T G x + r^T x + \sigma$$

• 任取初始点$x^{(1)}$，若$\triangledown f(x^{(1)}) = 0$， 停止计算，得到极小点$x^{(1)}$，否则取

  $$d^{(1)} = -\triangledown f(x^{(1)})$$

• 沿着$d^{(1)}$方向进行精确一维搜索得到$x^{(2)}$，若 $\triangledown f(x^{(2)}) \neq 0$，令

  $$d^{(2)} = -\triangledown f(x^{(2)}) + \beta_1^{(2)} d^{(1)}$$

  且满足$(d^{(1)})^T G d^{(2)} = 0$，即二者共轭，可得

  $$\beta_1^{(2)} = \frac {(d^{(1)})^T G \triangledown f(x^{(2)})} {((d^{(1)})^T G d^{(1)})}$$
  • 这里$d^{(2)}$方向的构造方式是为类似构造后面$d^{(k)}$ ，得到能方便表示的系数
  • 类似于将向量组$\triangledown f(x^{(i)})$正交化

• 如此重复搜索，若$\triangledown f^(x^{i)}) \neq 0$，构造 $x^{(k)}$处搜索方向$d^{(k)}$如下

  $$\begin{align*} 0 & = (d^{(i)})^T G d^{(k)} \\ & = -(d^{(i)})T G \triangledown f(x^{(k)}) + \sum_{j=1}^{k-1} \beta_j^{(k)} (d^{(i)})^T G d^{(j)} \\ & = -(d^{(i)})^T G \triangledown f(x^{(k)}) + \beta_i^{(k)} (d^{(i)})^T G d^{(i)} \end{align*}$$

  可得

  $$\beta_i^{(k)} = \frac {(d^{(i)})^T G \triangledown f(x^{(k)})} {(d^{(i)})^T G d^{(i)}}$$

  此时$d^{(k)}$与前k-1个方向均关于G共轭，此k个方向是G的k个 共轭方向，由扩展空间子定理，$x^{(k+1)}$是整个空间上极小

计算公式简化

期望简化$d^{(k)}$的计算公式

• 由扩展子空间定理推论有 $\triangledown f(x^{(k)})^T d^{(i)} = 0, i=1,2…,k-1$ 结合以上$d^{(k)}$的构造公式，有

  $$\begin{align*} & \triangledown f(x^{(k)})^T \triangledown f(x^{(i)}) \\ = & \triangledown f(x^{(k)})^T ( -d^{(i)} + \beta_1^{(i)} d^{(1)} + \cdots + \beta_{i-1}^{(i)} d^{(i-1)} ) \\ = & 0, i=1,2,...,k-1 \end{align*}$$

• 则有

  $$\begin{align*} (d^{(i)})^T G \triangledown f(x^{(k)}) & = \triangledown f(x^{(k)})^T G d^{(i)} \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T G (x^{(i+1)} - x^{(i)}) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(i+1)}) - \triangledown f(x^{(i)})) \\ & = 0, i=1,2,\cdots,k-2 \end{align*}$$

  • $d^{(k)} = \frac 1 {\alpha_i} x^{(i+1)} - x^{(i)}$

• 所以上述$d^{(k)}$构造公式可以简化为

  $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1} d^{(k-1)}$$

• 类似以上推导有

  $$\begin{align*} (d^{(k-1)})^T G \triangledown f(x^{(k)}) & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = \frac 1 {\alpha_i} \triangledown f(x^{(k)})^T \triangledown f(x^{(k)}) \\ \end{align*}$$ $$\begin{align*} (d^{(k-1)})^T G d^{(k-1)} & = \frac 1 {\alpha_i} (d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)})) \\ & = -\frac 1 {\alpha_i} (d^{(k-1)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} (\triangledown f(x^{(k-1)}) - \beta_{k-2}d^{(k-2)})^T \triangledown f(x^{(x-1)}) \\ & = -\frac 1 {\alpha_i} \triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)}) \end{align*}$$

  最终的得到简化后系数$\beta_{k-1}, k>1$的PRP公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {\triangledown f(x^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

  或FR公式

  $$\beta_{k-1} = \frac {\|\triangledown f(x^{(k)})\|^2} {\|\triangledown f(x^{(k-1)}) \|^2}$$

• 以上推导虽然是根据正定二次函数得出的推导，但是仍适用于 一般可微函数

• $\beta _ {k-1}$给出两种计算方式，应该是考虑到目标函数 可能不是标准正定二次函数、一维搜索数值计算不精确性

• 将$\beta _ {k-1}$分子、分母推导到不同程度可以得到其他 公式

• Growder-Wolfe公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))} {(d^{(k-1)})^T (\triangledown f(x^{(k)}) - \triangledown f(x^{(k-1)}))}$$

• Dixon公式

  $$\beta_{k-1} = \frac {\triangledown f(x^{(k)})^T \triangledown f(x^{(k)})} {(d^{(k-1)})^T \triangledown f(x^{(k-1)})}$$

FR/PRP算法

1. 初始点$x^{(1)}$、精度要求$\epsilon$，置k=1

2. 若$|\triangledown f(x^{(k)}) | \leq \epsilon$，停止 计算，得到解$x^{(k)}$，否则置

   $$d^{(k)} = -\triangledown f(x^{(k)}) + \beta_{k-1}d^{(k-1)}$$

   其中$\beta_{k-1}=0, k=1$，或由上述公式计算

3. 一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} - \alpha d^{(k)})$$

   得$\alpha_k$，置$x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$

4. 置k=k+1，转2

• 实际计算中，n步重新开始的FR算法优于原始FR算法
• PRP算法中 $\triangledown f(x^{(k)}) \approx \triangledown f(x^{(k-1)})$ 时，有$\beta_{k-1} \approx 0$，即 $d^{(k)} \approx -\triangledown f(x^{(k)})$，自动重新开始
• 试验表明，对大型问题，PRP算法优于FR算法

共轭方向下降性

• 设$f(x)$具有连续一阶偏导，假设一维搜索是精确的，使用共轭 梯度法求解无约束问题，若$\triangledown f(x^{(k)}) \neq 0$ 则搜索方向$d^{(k)}$是$x^{(k)}$处的下降方向

• 将$d^{(k)}$导入即可

算法二次终止性

• 若一维搜索是精确的，则共轭梯度法具有二次终止性

• 对正定二次函数，共轭梯度法至多n步终止，否则

  • 目标函数不是正定二次函数
  • 或目标函数没有进入正定二次函数区域，

• 此时共轭没有意义，搜索方向应该重新开始，即令

  $$d^{(k)} = -\triangledown f(x^{(k)})$$

  即算法每n次重新开始一次，称为n步重新开始策略

综述

一维搜索/线搜索：单变量函数最优化，即求一维问题

$$\arg\min _ {\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

最优解的$\alpha_k$的数值方法

• exact line search：精确一维搜索，求得最优步长 $\alpha_k$使得目标函数沿着$d^{(k)}$方向达到极小，即

• inexact line search：非精确一维搜索，求得$\alpha_k$ 使得

  $$\begin{align*} f(x^{(k)} + \alpha_k d^{(k)}) & < f(x^{(k)}) \\ \phi(\alpha_k) & < \phi(0) \end{align*}$$

一维搜索基本结构

• 确定搜索区间
• 用某种方法缩小搜索区间
• 得到所需解

搜索区间

• 搜索区间：设$\alpha^{ }$是$\phi(\alpha)$极小点，若存在 闭区间$[a, b]$使得$\alpha^{ } \in [a, b]$，则称 $[a, b]$是$phi(\alpha)$的搜索区间

确定搜索区间的进退法

1. 取初始步长$\alpha$，置初始值

   $$\mu_3 = 0, \phi_3 = \phi(\mu_3), k = 0$$

2. 置

   $$\mu = \mu_3 + \alpha, \phi = \phi(\mu), k = k+1$$

3. 若$\phi < \phi_3$，置

   $$\mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi \\ \alpha = 2\alpha, k = k+1$$

4. 若k =1，置

   $$\mu_2 = mu, \phi_2 = \phi, \alpha = -\alpha$$

   转2，否则置

   $$\mu_1 = \mu_2, \phi_1 = \phi_2 \\ \mu_2 = \mu_3, \phi_2 = \phi_3 \\ \mu_3 = \mu, \phi_3 = \phi$$

   并令$a=min{\mu_1,\mu_3}, b=max{\mu_1,\mu_3}$，停止搜索

• 通常认为目标函数此算法得到搜索区间就是单峰函数

试探法

• 在搜索区间内选择两个点，计算目标函数值
  • 需要获得两个点取值才能判断极值点的所属区间
• 去掉函数值较大者至离其较近端点段

0.618法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，计算左右 试探点

   $$\begin{align*} a_l & = a + (1 - \tau)(b - a) \\ a_r & = a + \tau(b - a) \end{align*}$$

   其中$\tau = \frac {\sqrt 5 - 1} 2$，及相应函数值

   $$\begin{align*} \phi_l & = \phi(a_l) \\ \phi_r & = \phi(a_r) \end{align*}$$

2. 若$\phi_l<\phi_r$，置

   $$b= a_r, a_r = a_l, \phi_l = \phi_l$$

   并计算

   $$a_l = a + (1 - \tau)(b - a), \phi_l = \phi(a_l)$$

   否则置

   $$a = a_l, a_l = a_r, \phi_l = \phi_r$$

   并计算

   $$a_r = a + \tau(b - a), \phi_r = \phi(a_r)$$

3. 若$|b - a| \geq \epsilon$

   • 若$\phi_l < \phi_r$，置$\mu = a_l$
   • 否则置$\mu = \alpha_r$ 得到问题解$\mu$，否则转2

• 0.618法除第一次外，每次只需要计算一个新试探点、一个新 函数值，大大提高了算法效率
• 收敛速率线性，收敛比为$\tau = \frac {\sqrt 5 - 1} 2$常数

Fibonacci方法

1. 置初始搜索区间$[a, b]$，置精度要求$\epsilon$，选取分离 间隔$\sigma < \epsilon$，求最小正整数n，使得 $F_n > \frac {b - a} \epsilon$，计算左右试探点

   $\begin{align} al & = a + \frac {F{n-2}} {Fn} (b - a)\ a_r & = a + \frac {F{n-1}} {F_n} (b - a) \end{align}

2. 置n=n-1

3. 若$\phi_l < \phi_r$，置

   $$b = a_r, a_r = a_l , \phi_r = \phi_l$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-2}} {F_n} (b - a) \\ \phi_r & = \phi(a_l) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_l & = a_r - \sigma \\ \phi_l & = \phi(a_l) \end{align*}$$

4. 若$\phi_l \geq \phi_r$，置

   $$a = a_l, a_l = a_r , \phi_l = \phi_r$$

   • 若n>2，计算

     $$\begin{align*} a_l & = a + \frac {F_{n-1}} {F_n} (b - a) \\ \phi_r & = \phi(a_r) \end{align*}$$

   • 否则计算

     $$\begin{align*} a_r & = a_l + \sigma \\ \phi_r & = \phi(a_r) \end{align*}$$

5. 若n=1

   • 若$\phi_l < \phi_r$，置$\mu = a_r$
   • 否则置$\mu = a_r$

   得到极小点$\mu$，停止计算，否则转2

• Finonacci方法是选取实验点的最佳策略，即在实验点个数相同 情况下，最终的极小区间最小的策略

• Finonacci法最优性质可通过设最终区间长度为1，递推使得原始 估计区间最大的取实验点方式，得出

插值法

• 利用搜索区间上某点的信息构造插值多项式（通常不超过3次） $\hat \phi(\alpha)$
• 逐步用$\hat \phi(\alpha)$的极小点逼近$\phi(\alpha)$ 极小点$\alpha^{*}$

• $\phi^{ * }$解析性质比较好时，插值法较试探法效果好

三点二次插值法

思想

以过三个点$(\mu_1,\phi_1), (\mu_2,\phi_2), (\mu_3,\phi_3)$ 的二次插值函数逼近目标函数

$$\begin{align*} \hat \phi(\alpha) & = \phi_1 \frac {(\alpha - \mu_2) (\alpha - \mu_3)} {(\mu_1 - \mu_2)(\mu_1 - \mu_3)} \\ & + \phi_2 \frac {(\alpha - \mu_1) (\alpha - \mu_3)} {(\mu_2 - \mu_1)(\mu_2 - \mu_3)} \\ & + \phi_3 \frac {(\alpha - \mu_1) (\alpha - \mu_2)} {(\mu_3 - \mu_1)(\mu_3 - \mu_2)} \end{align*}$$

• 求导，得到$\hat \phi(\alpha)$的极小点

  $$\mu = \frac {2[\phi_1(\mu_2-\mu_3) + \phi_2(\mu_3-\mu_1) + \phi_3(\mu_1 - \mu_2)]} {[\phi_1 (\mu_2^2-\mu_3^2) + \phi_2(\mu_3^2-\mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)]}$$

• 若插值结果不理想，继续构造插值函数求极小点近似值

算法

1. 取初始点$\mu_1<\mu_2<\mu_3$，计算$\phi_i=\phi(\mu_i)$， 且满足$\phi_1 > \phi_2, \phi_3 > \phi_2$，置精度要求 $\epsilon$

2. 计算

   $$A = 2[\phi_1(\mu_2 - \mu_3) + \phi_2(\mu_3 - \mu_1) + \phi_3(\mu_1 - \mu_2)]$$
   • 若A=0，置$\mu = \mu_2, \phi = \phi_2$，停止计算， 输出$\mu, \phi$

3. 计算

   $$\mu = [\phi_1 (\mu_2^2 - \mu_3^2) + \phi_2(\mu_3^2 - \mu_1^2) + \phi_3(\mu_1^2 - \mu_2^2)] / A$$
   • 若$\mu<\mu_1 或 \mu>\mu_3,\mu \notin (\mu_1,\mu_3)$ ，停止计算，输出$\mu, \phi$

4. 计算$\phi = \phi(\mu)$，若$|\mu - \mu_2| < \epsilon$， 停止计算，得到极小点$\mu$

5. 若$\mu \in (\mu_2, \mu_3)$

   • 若$\phi < \phi_2$，置 $$\mu_1=\mu_2, \phi_1=\phi_2, \mu_2=\mu, \phi_2=\phi$$
   • 否则置 $$\mu_3 = \mu, \phi_3 = \phi$$

   否则

   • 若$\phi < \phi_2$，置

     $$\mu_3=\mu_2, \phi_3=\phi_2, \mu_2=\mu, \phi_2=\phi$$

   • 否则置

     $$\mu_1 = \mu, \phi_1 = \phi$$

6. 转2

两点二次插值法

思想

以$\phi(\alpha)$在两点处$\mu_1, \mu_2$函数值 $\phi_1=\phi(\mu_1)$、一点处导数值 $\phi_1^{‘}=\phi^{‘}(\mu_1) < 0$构造二次函数逼近原函数

$$\begin{align*} \hat \phi(\alpha) & = A(\alpha - \mu_1)^2 + B(\alpha - \mu_1) + C \\ A & = \frac {\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)} {(\mu_2 - \mu_1)^2} \\ B & = \phi_1^{'} \\ C & = \phi_1 \end{align*}$$

• 为保证$[\mu_1, \mu_2]$中极小点，须有 $\phi_2 > \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$

• 求解，得到$\hat \phi (\mu)$极小值为

  $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]}$$

• 若插值不理想，继续构造插值函数求极小点的近似值

算法

1. 初始点$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_2 = \phi_(\mu_2)$$

2. 若$\phi_1^{‘} < 0$，置$d = |d|$，否则置$d = -|d|$

3. 计算

   $$\mu_2 = \mu_1 + d, \phi_2 = \phi(\mu_2)$$

4. 若$\phi_2 \leq \phi_1 + \phi_1^{‘}(\mu_2 - \mu_1)$，置 $d = 2d$，转3

5. 计算

   $$\mu = \mu_1 - \frac {\phi_1^{'}(\mu_2 - \mu_1)^2} {2[\phi_2 - \phi_1 - \phi_1^{'}(\mu_2 - \mu_1)]} \\ \phi = \phi(\mu), \phi^{'} = \phi^{'}(\mu)$$

6. 若$|phi^{‘}| \leq \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$\mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}, \alpha = \rho \alpha$$

• 其中通常取$d = 1, \rho = 0.1$

两点三次插值法

原理

以两点$\mu_1, \mu_2$处函数值$\phi_i = \phi(\mu_i)$和其导数值 $\phi_i^{‘} = \phi^{‘}(\mu_i)$，由Himiter插值公式可以构造 三次插值多项式$\hat \phi(\alpha)$

• 求导置0，得到$\hat \phi(\alpha)$极小点

  $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \end{align*}$$

算法

1. 初始值$\mu_1$、初始步长$d$、步长缩减因子$\rho$、精度要求 $\epsilon$，计算

   $$\phi_1 = \phi(\mu_1), \phi_1^{'} = \phi^{'}(\mu_1)$$

2. 若$\phi_1^{‘} > 0$，置$d = -|d|$，否则置$d = |d|$

3. 置$\mu_2 = \mu_1 + \alpha$，计算

   $$\phi_2 = \phi(\mu_2), \phi_2^{'} = \phi^{'}(\mu_2)$$

4. 若$\phi_1^{‘} \phi_2{‘} > 0$，置

   $$d = 2d, \mu_1 = \mu_2, \phi_1 = \phi_2, \phi_1^{'} = \phi_2^{'}$$

   转3

5. 计算

   $$\begin{align*} \mu & = \mu_1 + (\mu_2 - \mu_1)(1 - \frac {\phi_2^{'} + w + z} {\phi_2^{'} - \phi_1^{'} + 2w}) \\ z & = \frac {3(\phi_2 - \phi_1)} {\mu_2 - \mu_1} - \phi_1^{'} - \phi_2^{'} \\ w & = sign(\mu_2 - \mu_1) \sqrt {z^2 - \phi_1^{'} \phi_2^{'}} \\ \phi & = \phi(\mu) \\ \phi^{'} = \phi^{'}(\mu) \end{align*}$$

6. 若$|\phi^{‘}| < \epsilon$，停止计算，得到极小点$\mu$， 否则置

   $$d = \rho d, \mu_1 = \mu, \phi_1 = \phi, \phi_1^{'} = \phi^{'}$$

   转2

• 通常取$d = 1, \rho = 0.1$

非精确一维搜索

• 对无约束问题整体而言，又是不要求得到极小点，只需要一定 下降量，缩短一维搜索时间，使整体效果最好

• 求满足$\phi(\mu) < \phi(0)$、大小合适的$\mu$

  • $\mu$过大容易不稳定
  • $\mu$过小速度慢

GoldStein方法

原理

• 预先指定精度要求$0< \beta_1 < \beta_2 < 1$

• 以以下不等式限定步长

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu\beta_1 \phi^{'}(0) \\ \phi(\mu) & \geq \phi(0) + \mu\beta_2 \phi^{'}(0) \end{align*}$$

算法

1. 初始试探点$\mu$，置$\mu{min} = 0, \mu{max} = \infty$， 置精度要求$0 < \beta_1 < \beta_2 < 1$

2. 对$\phi(mu)$

   • 若$\phi(\mu) > \phi(0) + \beta1 \phi^{‘}(0) \mu$， 置$\mu{max} = \mu$

   • 否则若$\phi(\mu) > \phi(0) + \beta_2 \phi^{‘}(0)\mu$ ，则停止计算，得到非精确最优解$\mu$

   • 否则置$\mu_{min} = \mu$

3. 若$\mu{max} < \infty$，置 $\mu = \frac 1 2 (\mu{min} + \mu{max})$，否则置 $\mu = 2 \mu{min}$

4. 转2

Armijo方法

Armijo方法是Goldstein方法的变形

• 预先取$M > 1, 0 < \beta_1 < 1$

• 选取$\mu$使得其满足以下，而$M\mu$不满足

  $$\phi(\mu) \leq \phi(0) + \mu \beta_1 \phi^{'}(0)$$

• M通常取2至10

Wolfe-Powell方法

• 预先指定参数$0 < \beta_1 < \beta_2 <1$

• 选取$\mu$满足

  $$\begin{align*} \phi(\mu) & \leq \phi(0) + \mu \beta_1 \phi^{'}(0) \\ \phi^{'}(\mu) & \geq \beta_2 \phi^{'}(0) \end{align*}$$

• 能保证可接受解中包含最优解，而Goldstein方法不能保证