最优化基础：一维搜索方法

精确一维搜索

精确一维搜索通常要求 $f$ 在区间 $[a,b]$ 上为单峰的函数，已知存在极小值，否则会计算失败。

黄金分割法

这个方法只需要计算 $f(x)$ 的值，不需要导数信息。主要的步骤是不断压缩计算区间，假设初始计算区间 $[x_l,x_r]$ ，区间长度 $x_r-x_l$ ，比例系数 $\rho \in (0,\frac12)$ 待定。取内部左右两侧的两个点 $a_l,a_r$ 为

Copy LaTeX

如果 $f(a_l)<f(a_r)$ ，那么极小点位于 $a_r$ 左侧，选取新的计算区间为 $[x_l',x_r']=[x_l,a_r]$ 。
如果 $f(a_l)\ge f(a_r)$ ，那么极小点位于 $a_l$ 右侧，选取新的计算区间为 $[x_l',x_r']=[a_l,x_r]$ 。

新的计算区间长度为 $(1-\rho)(x_r-x_l)$ 。

我们希望可以充分利用计算的点值，以第一种情况为例，希望 $a_l$ 可以在新计算区间 $[x_l',x_r']$ 也被利用，作为右侧点，需要满足

Copy LaTeX

解得 $\rho = \frac{3-\sqrt5}2 \approx 0.382$ 。每次计算区间的压缩比例为 $1-\rho \approx 0.618$ 即黄金分割比。除了第一次压缩区间之外，每一次压缩区间只需要选择一个内部点进行求值。算法流程如下：

起始的计算区间 $[x_l,x_r]=[a,b]$ 。
选取左侧点 $a_l = x_l + \rho(x_r-x_l)$ ，右侧点 $a_r = x_r - \rho(x_r-x_l)$ ，计算 $f(a_l)$ 和 $f(a_r)$ 。
压缩区间：
1. 如果 $f(a_l)<f(a_r)$ ，那么极小点位于 $a_r$ 左侧，选取新的计算区间为 $[x_l',x_r']=[x_l,a_r]$ 。 $a_l$ 可以作为下一步的 $a_r'$ 。
2. 如果 $f(a_l)\ge f(a_r)$ ，那么极小点位于 $a_l$ 右侧，选取新的计算区间为 $[x_l',x_r']=[a_l,x_r]$ 。 $a_r$ 可以作为下一步的 $a_l'$ 。
如果计算区间已经足够小，则求解结束，得到最小值点，否则回到第二步。

Remark

黄金分割法的思路是固定 $\rho$ ，另一种思路是动态调整 $\rho$ ，取一个与斐波那契数列相关的系数 $\rho_k$ ，得到斐波那契数列法。

对分法

对分法主要依赖 $f'(x)$ ，和求根的对分法基本类似，算法流程如下：

起始的计算区间 $[x_l,x_r]=[a,b]$ 。
选取中点 $x_m = \frac12(x_l+x_r)$ ，计算 $f'(x_m)$ 。
如果中点 $|f'(x_m)| \le \varepsilon_g$ ，则达到给定的导数残差容差；或者区间长度 $x_r-x_l\le\varepsilon_x$ 时，输出中点作为位置近似。导数残差小本身不保证与极小点的距离小。
否则压缩区间：若 $f'(x_m) > 0$ ，取左侧为新的计算区间 $[x_l',x_r'] = [x_l,x_m]$ ；若 $f'(x_m) < 0$ ，取右侧为新的计算区间 $[x_l',x_r'] = [x_m,x_r]$ 。

牛顿法

牛顿法需要依赖 $f'(x),f''(x)$ ，并且假设 $f''>0$ 在计算区域内恒成立，否则难以保证收敛性。本质是通过二阶泰勒展开将 $f$ 在 $x^{(k)}$ 局部近似为二次函数 $q(h)$ ，然后更新到二次函数 $q(h)$ 的极小值点，得到 $x^{(k+1)}$ 。

Copy LaTeX

极小值点

Copy LaTeX

因此迭代格式为

Copy LaTeX

关于多维的非线性方程最小值问题：自变量 $X\in R^n$ ，目标函数 $f: R^n \to R$ 足够光滑，假设目标函数存在极小值，那么牛顿迭代法的公式为

Copy LaTeX

其中 $\nabla f$ 是梯度向量， $H = \nabla^2 f$ 是 Hesse 方阵。

Copy LaTeX

要求 Hesse 方阵始终可逆，计算才可以继续，事实上我们还希望 Hesse 方阵始终对称正定，此时二阶近似才存在最小值点，否则可能不收敛。为了确保计算可以继续，从牛顿法发展出了拟牛顿法：用一族对称正定矩阵 $H_k$ 来近似实际的 Hesse 方阵 $H(X^{(k)})$ 参与计算。

非精确一维搜索

非精确一维搜索不要求直接求出最小值点，而是给定一个下降准则，求出一个点使得函数有足够的下降即可。以下 $f(t)$ 表示沿搜索方向得到的一元函数，假设它在 $[0,\infty)$ 上连续可微，且 $f'(0)<0$ ，搜索正步长 $t>0$ 。对于下文需要扩张步长的 Goldstein 和 Wolfe 搜索，还假设 $f$ 在该射线上有下界。常用的下降准则有：

Armijo准则：取定 $\rho \in (0,1)$ ，要求 $t$ 使得
$Copy LaTeX$
Goldstein准则：取定 $\rho \in (0,\frac12)$ ，要求 $t$ 使得
$Copy LaTeX$
注意真正的最小值点也可能不满足Goldstein准则！
Wolfe准则：取定 $\rho \in (0,\frac12)$ 以及 $\sigma \in (\rho,1)$ ，要求 $t$ 使得
$Copy LaTeX$
第二个条件通常会被加强为双边条件，称为强Wolfe准则
$Copy LaTeX$

基于这些准则可以设计很多具体的非精确一维搜索算法，主要的过程都是不断使用二分法、插值法或者步长乘以比例系数的方法得到新的试探点，判定准则是否成立，成立即可结束搜索。若尚未找到步长的上界，可能需要扩张；建立上下界后，再在区间内继续搜索。以下各有一个例子。

满足 Armijo 准则的回退法

基于 Armijo 准则设计的常用算法是回退法：初始选取一个步长 $t_0=a>0$ ，选取一个指数衰减因子 $\gamma\in(0,1)$ ，检查是否满足准则。如果不满足，选取更小的步长 $t_{k+1}=\gamma t_k=\gamma^{k+1}a$ 继续尝试，接受第一个满足准则的步长：

Copy LaTeX

满足 Goldstein 准则的对分法

取初始试探步长 $a>0$ ，以及两个参数 $\rho \in (0,\frac12),\delta >0$ ，计算 $f(0),f'(0)$ 用于准则的判定。用 $x_r=\infty$ 表示尚未找到上界，初始步长 $a$ 不作为上界。

初始化 $x_l=0,\ x_r=\infty,\ x=a$ ，计算 $f(x)$ 。
若 $f(x)>f(0)+\rho f'(0)x$ ，更新上界 $x_r=x$ 。
否则，若 $f(x)\ge f(0)+(1-\rho)f'(0)x$ ，则两条准则均成立，输出 $t=x$ ；若仍不满足这条下界准则，则更新下界 $x_l=x$ 。
若 $x_r<\infty$ ，取新的试探点 $x=(x_l+x_r)/2$ ；若仍无上界，则取 $x=(1+\delta)x$ 扩张。计算新的 $f(x)$ ，回到第二步。

满足 Wolfe 准则的算法

以下算法满足普通 Wolfe 准则。取初始试探步长 $a>0$ ，参数 $\rho \in (0,\frac12),\sigma \in (\rho,1)$ ，扩张参数 $\delta>0$ ，以及插值保护参数 $\tau\in(0,\frac12)$ 。计算 $f(0),f'(0)$ ，初始化 $x_l=0,\ x_r=\infty,\ x=a$ 。

计算 $f(x)$ 。若不满足 Armijo 准则 $f(x)\le f(0)+\rho f'(0)x$ ，更新区间为 $[x_l',x_r']=[x_l,x]$ ，可用下面的左侧二次插值生成候选点。
若满足 Armijo 准则，计算 $f'(x)$ 。若 $f'(x)\ge\sigma f'(0)$ ，输出 $t=x$ ；否则更新为 $[x_l',x_r']=[x,x_r]$ 。已有有限上界时，可用下面的右侧二次插值生成候选点。
若 $x_r'=\infty$ ，取 $x'=(1+\delta)x$ 扩张。否则，只有当插值多项式为严格凸二次函数、候选点计算有效，且候选点落在
$Copy LaTeX$
内时才接受该候选点。若分母为零或数值上过小、曲率非正、候选点非有限或超出上述范围，则取中点 $x'=(x_l'+x_r')/2$ 。
更新 $x_l=x_l',\ x_r=x_r',\ x=x'$ ，回到第一步。保存下界处的函数值与导数，供下一次插值使用。

二次插值的具体公式如下。其中 $x_l,x_r,x$ 均指本轮更新前的值， $x_l',x_r'$ 指更新后的区间；下面的极小点公式仅在严格凸且分母有效时使用，并须经过第三步的保护检查。

当调整到左侧子区间 $[x_l',x_r'] = [x_l,x]$ ，取两点二次插值多项式 $p(s),s\in [x_l,x]$ ，基于如下信息（我们还没有计算 $f'(x)$ 的值）
$Copy LaTeX$
得到 $p(s)$ 的表达式
$Copy LaTeX$
极小点候选值为
$Copy LaTeX$
当调整到右侧子区间 $[x_l',x_r'] = [x,x_r]$ 且 $x_r<\infty$ 时，取二次多项式 $p(s)$ ，基于如下信息（我们已经计算了 $f'(x)$ 的值）
$Copy LaTeX$
得到 $p(s)$ 的表达式
$Copy LaTeX$
极小点候选值为
$Copy LaTeX$