Truncated Gradient

L1正则化法

L1正则化

$$w^{(t+1)} = w^{(t)} - \eta^{(t)}g^{(t)} - \eta^{(t)} \lambda sgn(w^{(t)})$$

• $\lambda$：正则化项参数
• $sgn$：符号函数
• $g^{(t)}=\nabla_w L(w^{(t)}, Z^{(t)})$：损失函数对参数梯度

• L1正则化项在0处不可导，每次迭代使用次梯度计算正则项梯度
• OGD中每次根据观测到的一个样本进行权重更新 （所以后面正则项次梯度只考虑非0处？？？）

简单截断法

简单截断法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_0 (w^{(t)} - \eta^{(t)} G^{(t)}, \theta) \\ T_0(v_i, \theta) & = \left \{ \begin{array}{l} 0, & |v_i| \leq \theta \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $w^{(t)}$：模型参数
• $g^{(t)}$：损失函数对模型参数梯度
• $T_0$：截断函数
• $\theta$：控制参数稀疏性

截断梯度法

截断梯度法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_1(w^{(t)} - \eta^{(t)} g^{(t)}, \lambda^{(t)} \eta^{(t)}, \theta) \\ T_1(v_i, \alpha, \theta) & = \left \{ \begin{array}{l} max(0, v_i - \alpha), & v_i \in [0, \theta] \\ min(0, v_1 + \alpha), & v_i \in [-\theta, 0] \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $\lambda, \theta$：控制参数$w$稀疏性

• 对简单截断的改进，避免在实际（OgD）中参数因训练不足过小 而被错误截断，造成特征丢失

  

Forward-Backward Spliting

FOBOS：前向后向切分，权重更新方式为proximal method如下

$$\begin{align*} w^{(t.5)} & = w^{(t)} - \eta^{(t)} g^{(t)} \\ w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t.5)}\| + \eta^{(t+0.5)} \Phi(w) \} \\ & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t+0.5)} \Phi(w) \} \end{align*}$$

L1-FOBOS

L1-FOBOS：即令$Phi(w)=\lambda |w|_1$，则根据可加性如下

$$\begin{align*} w^{(t+1)} & = \arg\min_w \sum_{i=1}^N (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) w_i^{(t+1)} = \arg\min_{w_i} (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) \end{align*}$$

• $V=[v_1, v_2, \cdots, v_N]:=w^{(t.5)}$：为方便
• $\tilde \lambda := \eta^{t.5} \lambda$：为方便
• $\eta^{t.5}$：学习率，常取 $\eta^{(t)} \in \theta(\frac 1 {\sqrt t})$

• 则对$w_i$求次梯度、分类讨论，解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} v_i - \tilde \lambda, & v_i > \tilde \lambda \\ 0, & |v_i| < \tilde \lambda \\ v_i + \tilde \lambda, & v_i < -\tilde \lambda \end{array} \right.$$

  • 可以理解为：到当前样本为止，维度权重小于阈值 $\eta^{(t.5)} \lambda$）时，认为该维度不够重要， 权重置为0

  • 可视为$k=1, \theta=\infty$的Tg算法

• 另外，显然有$w_i^{(t+1)} v_i \geq 0$

  $$\begin{align*} \frac 1 2 (w_i^{(t+1)} - v_i)^2 + \tilde \lambda |w_i^{(t+1)}| & = \frac 1 2((w_i^{(t+1)})^2 - 2 w_i^{(t+1)} v_i + v_i^2) + \tilde \lambda |w_i^{(t+1)}| \\ & \leq \frac 1 2 v_i^2 \end{align*}$$

  • 考虑$w_i^{(t+1)}$使得目标函数最小，带入$w=0$则得

Regularized Dual Averaging

RDA算法：正则对偶平均算法，权重更新方式为 包含[增广]正则项的最速下降

$$w^{(t+1)} = \arg\min_w {\frac 1 t \sum_{r=1}^t g^{(r)} w + \Phi(w) + \frac {\beta^{(t)}} t h(w)}$$

• 目标函数包括三个部分

  • $\frac 1 t \sum_{r=1}^t g^{(r)} w$：包含之前所有梯度 均值
  • $\Phi(w)$：正则项
  • $\frac {\beta^{(t)}} t h(w)$：额外正则项，严格凸，且 不影响稀疏性

• 相较于TG、FOBOS是从另一方面求解在线最优化，更有效地提升 特征权重稀疏性

L1 RDA

L1 RDA：令$\Phi(w) := \lambda |w|_1$， 再设$h(w) := |w|_2^2$，根据可加性则有

$$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 t \sum_{r=1}^t <g^{(t)}, w> + \lambda \|w\|_1 + \frac {\gamma} {2\sqrt t} \|w\|_2^2 \} \\ w_i^{(t+1)} & = \arg\min_{w_i} \{bar g_i^{(t)} w_i + \lambda |w_i| \frac {\gamma} {2 \sqrt t} w_i^2 \} \end{align*}$$

• $\lambda > 0, \gamma > 0$
• $\bar gi^{(t)} = \frac 1 t \sum{r=1}^t g_i^{(r)}$

• 对$w_i$求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} -\frac {\sqrt t} {\gamma} (\bar g^{(t)} - \lambda), & \bar g_i^{(t)} > \lambda \\ 0, & |\bar g_i^{(t)}| \leq \lambda \\ -\frac {\sqrt t} {\gamma} (\bar g^{(t)} + \lambda), & \bar g_i^{(t)} < -\lambda \\ \end{array} \right.$$
  • 可以理解为：某维度梯度累计均值绝对值$|bar g_i^{(t)}$ 小于阈值$\lambda$时，对应权重被置零、产生稀疏性

• 相较于L1-FOBOS的截断

  • 截断阈值为常数，更加激进、容易产生稀疏性
  • 截断判断对象为梯度累加均值，避免由于训练不足而产生 截断
  • 只需条件$\lambda$参数，容易权衡精度、稀疏性

Follow the Regularized Leader

FTRL：综合考虑L1-RDA、L1-FOBOS

L1-FOBOS、L1-RDA变换

• 将L1-FOBOS类似近端算法收敛证明中展开、去除无关项、放缩， 得到类似L1-RDA目标函数

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t)} \lambda \|w\|_1 \} \\ & = \arg\min_w \{ g^{(t)} w + \lambda \|w\|_1 + \frac 1 {2 \eta^{(t)}} \|w - w^{(t)}\|_2^2 \} \end{align*}$$

• 将L1-RDA目标函数整体整体放缩，得到

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} w + t \lambda \|w\|_1 + \frac 1 {2\eta^{(t)}} \|w - 0\|_2^2 \}$$

  • $g^{(1:t)} := \sum_{r=1}^t g^{(r)}$

• FTRL综合考虑L1-FOBOS、L1-RDA，得到目标函数

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} W + \lambda_1 \|w\|_1 + \frac {\lambda_2} 2 \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w - w^{(r)}\|_2^2 \}$$
  • 使用累加梯度更新，避免因训练不充分错误截断
  • 包含L1-FOBOS、L1-RDA全部正则化项

求解

• 将FTRL中最后一项拆分、去除无关项

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{(g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)})w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w^{(r)}\|_2^2 \} \\ & = \arg\min_w \{ z^{(t)} w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 \} \\ z^{(t)} &= g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)} \end{align*}$$

• 则同样根据可加性，对各分量求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} - \lambda_1 z_i), & z_i > \lambda_1 \\ 0, & |z_i^{(t)}| \leq \lambda_1 \\ \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} + \lambda_1 z_i), & z_i < -\lambda_1 \\ \end{array} \right.$$

• 其中学习率$\eta$为类似Adagrad优化器的学习率，但包括可学习 参数$\alpha, \beta$

  $$\eta_i^{(t)} = \frac {\alpha} {\beta + \sqrt{\sum_{r=1}^t (g_i^{(r)})^2}}$$

坐标下降

坐标下降法：在当前点处延一个坐标方向进行一维搜索以求得函数 的局部极小值

• 非梯度优化算法，但能提供超过一阶的信息
  • SMO算法就是两块贪心坐标下降

说明

• 优化方向从算法一开始就固定，如：选择线性空间中一组基作为 搜索方向

• 循环极小化各坐标方向上目标函数值，即：若$x^k$给定，则

  $$x_i^{(k+1)} = \arg\min_{x \in R} f(x_1^{k+1}, \cdots, x_{i-1}^{k+1}, x, x_{i+1}^{k}, \cdots, x_n^k)$$

  • $k$：第k轮迭代
  • $i$：某轮迭代中更新第i个方向

• 对初始值为$X_0$得到迭代序列$X_1, \cdots, X_n$，对精确 一维搜索类似最速下降有

  $$F(X_0) \geq F(X_1) \geq \cdots \geq F(x_n)$$

• 若某轮迭代中目标函数无法被有优化，说明已经达到驻点

Adaptive Coordinate Descent

自适应坐标下降：变换坐标系使得在考虑目标函数的情况下，新坐标 间尽可能不相关

• 对非可拆分函数（可加？），算法可能无法在较小迭代步数中 求得最优解

  • 可采用适当坐标系加速收敛，如：主成分分析进行自适应 编码
  • 性能远超过传统坐标下降算法，甚至可以达到梯度下降的 性能

  

• 自适应坐标下降具有以下特性，和最先进的进化算法相当

  • 缩放不变性
  • 旋转不变性

Block Coordinate Descent

块坐标下降：在当前点处在一个超平面内方向进行搜索以求得函数 的局部极小值

• 即同时更新一组坐标的坐标下降

例

Lasso求解

• 目标函数

  $$L(x) = RSS(x) + \lambda \|x\|_1 = \frac 1 2 (Ax - y)^T(Ax - y) + \lambda \|x\|_1$$

• RSS求导

  $$\begin{align*} \frac {\partial RSS} {\partial x} & = (Ax - y)^T A \\ (\frac {\partial RSS} {\partial x})_i & = (Ax - y)^T A_{:i} \\ & = (Ax_{i0} - y)^T A_{:i} + x_i A_{:i}^T A_{:i} \\ & = z_i + \rho_i x_i \end{align*}$$

  • $(\frac {\partial RSS} {\partial x})_i$：RSS对$x$ 导数第$i$分量，即对$x_i$偏导
  • $A_{:i}$：$A$第$i$列
  • $x_{i0}$：$x$第$i$分量置零
  • $zi = (Ax{i0} - y)^T A_{:i}$
  • $\rhoi = A{:i}^T A_{:i}$

• 则$x_i$整体次梯度为

  $$\frac {\partial L} {\partial x_i} = z_i + \rho_i x_i + \left \{ \begin{array}{l} -\lambda, & x_i < 0 \\ [-\lambda, \lambda], & x_i = 0 \\ \lambda, & x_i > 0 \end{array} \right.$$

• 分类讨论：令整体次梯度为0求解$x_i$、回带确定参数条件

  $$x_i = \left \{ \begin{array}{l} \frac {-z_i + \lambda} {\rho_i}, & z_i > \lambda \\ 0 , & -\lambda < z_i < \lambda \\ \frac {-z_i - \lambda} {\rho_i}, & z_i < -\lambda \end{array} \right.$$

  • 此算子也称soft threshholding

  

无约束局部解

$$minf(x), x \in R^n$$

• 若存在$x^{ } \in R^n, \epsilon > 0, \forall x \in R^n$ 使得$|x - x^{ }| < \epsilon$时，恒有
• $f(x) \geq f(x^{ })$：则称$x^{ }$为f(x)的 local minimum point/solution（局部极小点/局部解）
• $f(x) > f(x^{ })$：则称$x^{ }$为f(x)的 严格局部极小点/局部解

最优性条件

First-Order Necessary Condtion

• 无约束问题局部解的一阶必要条件：设f(x)有连续的一阶偏导， 弱$x^{ * }$是无约束问题的局部解，则 $$\triangledown f(x{* }) = 0$$

Second-Order Necessary Condition

• 无约束问题局部解的二阶必要条件：设f(x)有连续二阶偏导， 若$x^{ * }$是无约束问题的局部解，则

  • $$\triangledown f(x^{ * }) = 0$$
  • $$\triangledown^2 f(x^{ * })半正定$$

Second-Order Sufficient Condition

• 无约束问题局部解的二阶充分条件：设f(x)有连续二阶偏导， 若在$x^{ }$处满足以下，则x^{ }是无约束问题的 严格局部解

  • $$\triangledown f(x^{ * }) = 0$$
  • $$\triangledown^2 f(x^{ * })正定$$

下降算法

迭代算法：将当前迭代点向正确方向移动一定步长，然后 检验目标值是否满足一定要求

• 方向、步长就是不同优化算法主要关心的两个方面
• 还关心算法的rate of convergence（收敛速率）

一般下降算法框架

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

2. 若在点$x^{(k)}$处满足某个终止准则，则停止计算，得无约束 优化问题最优解$x^{(k)}$，否则适当地选择$x^{(k)}$处 搜索方向

3. 进行适当的一维搜索，求解一维问题

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

4. 置k=k+1，转2

要使下降算法可行，需要确定

• 某点出搜索方向
  • 负梯度方向
  • Newton方向：求方向的时候已确定步长，也可用做步长搜索
  • 拟Newton方向
• 求步长地一维搜索方式
  • 试探法
    • 0.618法
    • Fibonacci方法（分数法）
    • 二分法
  • 插值法
    • 三点二次插值法
    • 二点二次插值法
    • 两点三次插值法
  • 非精确一维搜索方法
    • Glodstein方法
    • Armijo方法
    • Wolfe-Powell方法

• 算法终止准则

  • $|\triangledown f(x^{(k)})| < \epsilon$
  • $|x^{(k+1)} - x^{(k)}| < \epsilon$
  • $|f(x^{(k+1)}) - f(x^{(k)})| < \epsilon$

  • 实际计算中最优解可能永远无法迭代达到，应该采用较弱 终止准则

算法收敛性

• 收敛：序列${x^{(k)}}$或其一个子列（仍记${x^{(k)}}$） 满足 $$\lim_{k \rightarrow \infty} x^{(k)} = x^{ * }$$

  • $x^{ * }$：无约束问题局部解

但是这样强的结果难以证明

• 往往只能证明${x^{(k)}}$的任一聚点的稳定点
• 或是更弱的 $$\lim_{k \rightarrow \infty} inf \|\triangledown f(x^{(k)}) \| = 0$$

• 局部收敛算法：只有初始点充分靠近极小点时，才能保证产生 序列收敛
• 全局收敛算法：对任意初始点，产生序列均能收敛

收敛速率

设序列${x^{(k)}}$收敛到$x^{ * }$，若以下极限存在

$$\lim _ {k \rightarrow \infty} \frac {\|x^{(k+1)} - x^{*}\|} {\|x^{(k)} - x^{*}\|} = \beta$$

• $0 < \beta < 1$：线性收敛
• $\beta = 0$：超线性收敛
• $\beta = 1$：次线性收敛（收敛速率太慢，一般不考虑）

算法的二次终止性

• 二次终止性：若某算法对任意正定二次函数，从任意初始点出发 ，都能经过有限步迭代达到其极小点，则称该算法有二次终止性

具有二次终止性的算法被认为时好算法，否则计算效果较差，原因

• 正定二次目标函数有某些好的性质，好的算法应该能在有限步内 达到其极小点

• 对于一个一般的目标函数，若其在极小点处的Hesse矩阵 $\triangledown f(x^{( * )})$，则由泰勒展开式得到

  $$\begin{align*} f(x) & = f(x^{*}) + \triangledown f(x^ {*})^T(x - x^{*}) \\ & + \frac 1 2 (x - x^{*})^T \triangledown^2 f(x^{*}) (x - x^{*}) \\ & + o(\|x - x^{*}\|^2) \end{align*}$$

  即目标函数f(x)在极小点附近与一个正定二次函数近似，所以对 正定二次函数好的算法，对一般目标函数也应该具有较好的性质

正定二次目标函数

$$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

思想：最速下降&牛顿

对目标函数$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方法不能保证