无约束优化特殊问题

正定二次目标函数

非线性最小二乘

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

  • 为$r(x)$的Jacobi矩阵

Gauss-Newton法

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

算法

同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方法中的方程组会出现困难,可以改为求解

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

定理1

  • 若$d(v)$是以上方程组的解,则$|d(v)|^2$是$v$的连续下降 函数,且$v \rightarrow +\infty, |d(v)| \rightarrow 0$
  • $J(x^{(k)})^T J(x^{(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矩阵定义二次函数

  • 其增量为

  • 目标函数增量

  • 定义$\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)}$,否则求解线性方程组

    得到$d^{(k)}$

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

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

Lagrange 对偶

Langrangian Duality

拉格朗日对偶

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

  • 考虑方程组

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

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

      • 显然,取$g_1 + g_2 = 0, g_1(x) > 0$是反例,不能 推出原方程有解
    • 由以上方程组有解逆否命题:方程组无解充分条件如下

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

说明

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

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

    • 线性规划
    • 半正定规划
    • 凸优化
    • 即需要给约束条件加以限制,使得 是上述方程组有解的冲要条件
  • 弱对偶定理:$v^{} \leq z^{}$,永远成立(以上即可证)

    • 通过弱对偶定理,可以得到原问题的一个下界
    • 对求解原问题有帮助,比如:分支界限法中快速求下界
  • 对偶问题相关算法往往原问题算法在实际应用中往往更加有效

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

原始问题

约束最优化问题

Generalized Lagrange Function

  • 引入Generalized Lagrange Function

    • $x=(x_1, x_2, \cdots, x_n) \in R^n$
    • $\alpha_i \geq 0, \beta_j$:拉格朗日乘子
  • 考虑关于x的函数

    • $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_D(\alpha, \beta)$,得到广义拉格朗日 函数的极大极小问题,即

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

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

原始、对偶问题关系

定理1

  • 若原始问题、对偶问题都有最优值,则
  • $\forall x, \alpha, \beta$有

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

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

Gradient Descent Method

思想:最速下降&牛顿

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

  • 最速下降法:只保留一阶项,即使用线性函数近似原目标函数
  • Newton法:保留一阶、二阶项,即使用二次函数近似
  • 利用近似函数求解元素问题极小值

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

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

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

最速下降算法

思想

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

    • $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$,则停止计算,得到最优解, 否则置

    以负梯度作为前进方向

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

    得$\alpha_k$前进步长,置

  4. 置k=k+1,转2

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

叠加惯性

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

momentum

Momentum

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

  • $v^{(t)}$:第$t$步时第k个参数更新步
  • $L(\theta)$:往往是batch损失函数
  • 更新参数时,一定程度保持上次更新方向
  • 可以在一定程度上保持稳定性,学习速度更快
  • 能够越过部分局部最优解

Nesterov Momentum

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

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

动态学习率

  • 学习率太小收敛速率缓慢、过大则会造成较大波动
  • 在训练过程中动态调整学习率大小较好
  • 模拟退火思想:达到一定迭代次数、损失函数小于阈值时,减小 学习速率

param_estimation_comparion_1 param_estimation_comparion_2

Vanilla Gradient Descent

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

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

Adagrad

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

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

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

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

RMSprop

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

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

Adam

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

  • $\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)}$动态调整每个 参数学习率

  • 类似于mommentumRMSprop结合

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

Adadelta

指数平滑更新学习率(分子)、学习率分母

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

样本量

Singular Loss/Stocastic Gradient Descent

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

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

    • 代表模型在单点上的优劣,无法代表模型在总体上性质
    • 具有很强随机性
  • 单点损失不常用,SGD范围也不局限于单点损失

  • 损失函数具体参见ml_xxxxx

全局估计

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

  • $\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上的损失极小化目标函数、 计算梯度、更新参数

  • $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's Method

Newton法

思想

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

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

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

    解得

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

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

    • $d^{(k)}$:Newton方向,即以下方程解

算法

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

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

    • 若满足,则停止计算,得到最优解 $x^{(k)}$
    • 否则求解如下方程,得到 $d^{(k)}$

  • 如下设置,并转2

特点

  • 优点

    • 产生点列 ${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)}$
  • 一维搜索,求解一维问题

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

其他改进

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

结合最速下降方向

  • Newton 方向和最速下降方向结合
  • 设 $\theta_k$ 是 $$ 之间夹角,显然希望 $\theta < \frac \pi 2$

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

Negative Curvature

  • Hesse 矩阵非正定时,选择负曲率下降方向 $d^{(k)}$(一定存在)
  • Hesse 矩阵非正定时,一定存在负特征值、相应特征向量 $u$

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

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

修正 Hesse 矩阵

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

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

Quasi-Newton Method/Variable Metric Method

综述

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

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

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

思想

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

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

    • $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)}$对称

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

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

Hesse矩阵修正

对称秩1修正

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

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

    • 这里有的书会设$\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$共线,则有

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

算法

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

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

  3. 一维搜索,求解

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

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

  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,设

  • 带入拟Newton方程有

  • 类似的取

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

BFGS算法

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

Hesse逆修正

对称秩2修正

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

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

  • 相应拟Newton方程为

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

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

DFP算法

类似BFGS算法,只是

  • 使用$H^{(k)}$计算更新方向
  • 使用$H^{(k)}$的对称秩2修正公式修正
  • 对正定二次函数,BFGS算法和DFP算法效果相同
  • 对一般可微(非正定二次函数),一般认为BFGS算法在收敛性质 、数值计算方面均由于DFP算法

Hesse逆的BFGS算法

  • 考虑

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

todo

  • 还可以进一步展开

变度量法的基本性质

算法的下降性

定理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)}$是最优解

Conjugate Gradient Method

共轭方向

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

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

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

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

定理1

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

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

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

扩展子空间定理

  • 设目标函数为 $d^{(1)}, \cdots, d^{(k)}$是$k, k \leq n$个非零正交方向 ,从任意初始点$x^{(1)}$出发,依次沿着以上正交方向做 精确一维搜索,得到$x^{(1)}, \cdots, x^{(k+1)}$, 则$x^{(k+1)}$是$f(x)$在线性流形 上的唯一极小点,特别的k=n时,$x^{(n+1)}$是$f(x)$在整个 空间上的唯一极小点
  • 引进变换$w = \sqrt G x$即可证
  • 在以上假设下,有

Conjugate Gradient Method

共轭梯度法

对正定二次函数函数

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

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

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

    • 这里$d^{(2)}$方向的构造方式是为类似构造后面$d^{(k)}$ ,得到能方便表示的系数
    • 类似于将向量组$\triangledown f(x^{(i)})$正交化
  • 如此重复搜索,若$\triangledown f^(x^{i)}) \neq 0$,构造 $x^{(k)}$处搜索方向$d^{(k)}$如下

    可得

    此时$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)}$的构造公式,有

  • 则有

    • $d^{(k)} = \frac 1 {\alpha_i} x^{(i+1)} - x^{(i)}$
  • 所以上述$d^{(k)}$构造公式可以简化为

  • 类似以上推导有

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

    或FR公式

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

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

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

  • Growder-Wolfe公式

  • Dixon公式

FR/PRP算法

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

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

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

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

    得$\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步终止,否则

    • 目标函数不是正定二次函数
    • 或目标函数没有进入正定二次函数区域,
  • 此时共轭没有意义,搜索方向应该重新开始,即令

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

Line Search

综述

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

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

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

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

一维搜索基本结构

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

搜索区间

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

确定搜索区间的进退法

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

  2. 若$\phi < \phi_3$,置

  3. 若k =1,置

    转2,否则置

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

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

试探法

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

0.618法

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

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

  2. 若$\phi_l<\phi_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$,置

    • 若n>2,计算

    • 否则计算

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

    • 若n>2,计算

    • 否则计算

  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)$ 的二次插值函数逼近目标函数

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

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

算法

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

  2. 计算

    • 若A=0,置$\mu = \mu_2, \phi = \phi_2$,停止计算, 输出$\mu, \phi$
  3. 计算

    • 若$\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$,置
    • 否则置

    否则

    • 若$\phi < \phi_2$,置

    • 否则置

  6. 转2

两点二次插值法

思想

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

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

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

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

算法

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

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

  3. 计算

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

  5. 计算

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

  • 其中通常取$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)$极小点

算法

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

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

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

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

    转3

  5. 计算

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

    转2

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

非精确一维搜索

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

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

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

GoldStein方法

原理

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

  • 以以下不等式限定步长

line_search_goldstein

算法

  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$不满足

  • M通常取2至10

line_search_armijo

Wolfe-Powell方法

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

  • 选取$\mu$满足

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