02-线搜索

本章主要解决一元优化问题：

$$minimizef(\mathbf{x})subjectto\mathbf{x}\in \Omega$$

目标函数为一元单值函数 $\mathbf{f}:\mathbb{R}\to \mathbb{R}$

• 迭代算法：从初始搜索点出发，产生一个迭代序列，不断逼近极值点。

---

黄金分割法

• 原理：
  • 按黄金分割比把区间分两份（在原区间插入两点，插入点到左右端点距离相同）
  • 在两个个区间$[a_0,a_1],[b_1,b_0]$ 中比较插入处函数值大小，后去掉一个不符合条件的区间
  • 在剩下的一个区间里再次插入一个点
  • 重复上述操作，直到收敛

函数实例

黄金分割法改进-斐波那契数列法

改进示意图

• 区间压缩率： 斐波那契数列法的总压缩比为 $\left(1-{\rho }_1\right)\left(1-{\rho }_2\right)\cdots \left(1-{\rho }_N\right)=\frac{F_N}{F_{N+1}}\frac{F_{N-1}}{F_N}\cdots \frac{F_1}{F_2}=\frac{F_1}{F_{N+1}}=\frac{1}{F_{N+1}}$

由于该方法使用的最优参数序列 ${\rho }_1,{\rho }_2,\cdots$, 因此, 总压缩比比黄金分割法要小。

该迭代方法的最后一次迭代参数为1/2， 为避免这一问题，可以令最后一次的迭代参数为 ${\rho }_N=1/2-\epsilon$ 。

二分法

• 适用条件：函数 $f$ 在区间 $[a_0,b_0]$ 为单峰函数，且是连续可微的。
• 原理：利用函数的一阶导数，对区间进行二分。
  • 首先, 确定初始区间的中点 $x^{(0)}=\left(a_0+b_0\right)/2$ 。
  • 然后, 计算函数 $f$ 在 $x^{(0)}$ 处的一阶导数 $f^{\prime }\left(x^{(0)}\right)$ 。
  • 如果 $f^{\prime }\left(x^{(0)}\right)>0$, 说明极小点位于 $x^{(0)}$ 的左侧
  • 如果 $f^{\prime }\left(x^{(0)}\right)<0$, 说明极小点位于 $x^{(0)}$ 的右侧
  • 如果 $f^{\prime }\left(x^{(0)}\right)=0$, 说明 $x^{(0)}$ 就是函数 $f$ 的极小点 二分法与黄金分割法和斐波那契数列法存在两个明显的区别，二分法使用的是:函数的导数 $f^{\prime }$ ，而不是黄金分割法和斐波那契数列法所使用的函数值;迭代中, 区间的压缩比为 $1/2$ 。 $N$ 步迭代之后, 整个区间的总压缩比为 $(1/2{)}^N$ 。总压缩比比黄金分割法和斐波那契数列法的总压缩比要小。

牛顿法

• 适用条件：函数二阶连续可微。利用函数在该点处的函数值，一二阶导数。

• 原理： $q(x)=f\left(x^{(k)}\right)+f^{\prime }\left(x^{(k)}\right)\left(x-x^{(k)}\right)+\frac{1}{2}{f}^{\prime \prime }\left(x^{(k)}\right){\left(x-x^{(k)}\right)}^2$

  • 求函数 $f$ 的极小点可近似于求解 $q$ 的极小点。
  • 函数 $q$ 的极小点 $0=q^{\prime }(x)=f^{\prime }\left(x^{(k)}\right)+f^{\prime \prime }\left(x^{(k)}\right)\left(x-x^{(k)}\right)$
  • 令 $x=x^{(k+1)}$, 可得 $x^{(k+1)}=x^{(k)}-\frac{f^{\prime }\left(x^{(k)}\right)}{f^{\prime \prime }\left(x^{(k)}\right)}$
  • （牛顿法可以用于求方程的根，$x^{(k+1)}=x^{(k)}-\frac{f\left(x^{(k)}\right)}{f^{\prime }\left(x^{(k)}\right)}$ ）

牛顿法例题

例: 利用牛顿法求解如下函数的极小点: $f(x)=\frac{1}{2}{x}^2-\sin x$ 初始值为 $x^{(0)}=0.5$, 精度为 $\epsilon =10^{-5}$, 即当 $\left|x^{(k+1)}-x^{(k)}\right|<\epsilon$ 时停止迭代。 计算函数 $f$ 的一阶和二阶导数: $f^{\prime }(x)=x-\cos x,f^{\prime \prime }(x)=1+\sin x$ $\begin{array}{rl}& x^{(1)}=0.5-\frac{0.5-\cos 0.5}{1+\sin 0.5}=0.7552\\ & x^{(2)}=x^{(1)}-\frac{f^{\prime }\left(x^{(1)}\right)}{f^{\prime \prime }\left(x^{(1)}\right)}=x^{(1)}-\frac{0.02710}{1.685}=0.7391\\ & x^{(3)}=x^{(2)}-\frac{f^{\prime }\left(x^{(2)}\right)}{f^{\prime \prime }\left(x^{(2)}\right)}=x^{(2)}-\frac{9.461\times 10^{-5}}{1.673}=0.7390\\ & x^{(4)}=x^{(3)}-\frac{f^{\prime }\left(x^{(3)}\right)}{f^{\prime \prime }\left(x^{(3)}\right)}=x^{(3)}-\frac{1.17\times 10^{-9}}{1.673}=0.7390\end{array}$ 由于 $\left|x^{(4)}-x^{(3)}\right|<\epsilon =10^{-6}$, 迭代结束。 $x^{(4)}$ 处的一阶导数为 $f^{\prime }\left(x^{(4)}\right)=-8.6\times 10^{-6}\approx 0$, 且二阶导数 $f^{\prime \prime }\left(x^{(4)}\right)=1.673>0$, 说明 $x^{\ast }\approx x^{(4)}$ 是一个严格极小点。

注: $f^{\prime \prime }(x)>0$ 对于区间内所有的 $x$ 都成立时, 牛顿法能够正常运行 如果在某些点处, 有 $f^{\prime \prime }(x)<0$, 牛顿法可能收敛到极大点

牛顿法的近似-割线法

• 对二阶导数的近似：如果二阶导数不存在, 近似计算 $f^{\prime \prime }\left(x^{(k)}\right):\frac{f^{\prime }\left(x^{(k)}\right)-f^{\prime }\left(x^{(k-1)}\right)}{x^{(k)}-x^{(k-1)}}$

$$\begin{array}{rl}{x}^{(k+1)}& =x^{(k)}-\frac{x^{(k)}-x^{(k-1)}}{f^{\prime }\left(x^{(k)}\right)-f^{\prime }\left(x^{(k-1)}\right)}{f}^{\prime }\left(x^{(k)}\right)\\ & =\frac{f^{\prime }\left(x^{(k)}\right)x^{(k-1)}-f^{\prime }\left(x^{(k-1)}\right)x^{(k)}}{f^{\prime }\left(x^{(k)}\right)-f^{\prime }\left(x^{(k-1)}\right)}\end{array}$$

该方法需要两个初始点 $x^{(-1)}$ 和 $x^{(0)}$ 。

同理：割线法也可以求方程 $g(x)=0$ 其迭代公式为

$$\begin{array}{rl}{x}^{(k+1)}& =x^{(k)}-\frac{x^{(k)}-x^{(k-1)}}{g\left(x^{(k)}\right)-g\left(x^{(k-1)}\right)}g\left(x^{(k)}\right)\\ & =\frac{g\left(x^{(k)}\right)x^{(k-1)}-g\left(x^{(k-1)}\right)x^{(k)}}{g\left(x^{(k)}\right)-g\left(x^{(k-1)}\right)}\end{array}$$

注：牛顿法和割线法都属于二次拟合。割线法只用到了目标函数的一阶导数 $f^{\prime }$ ,没有用到二阶导数 $f^{\prime \prime }$

插值类方法

• 思路：在搜索区间内使用低次（不超过3次）多项式插值近似目标函数
• 三点两次插值
• 两点二次插值
• 两点三次插值

多元函数线搜索

讨论目标函数： $f:{\mathbb{R}}^n\to \mathbb{R}$ 求其极小点的迭代算法迭代公式为：

${\mathbf{x}}^{(k+1)}={\mathbf{x}}^{(k)}+{\alpha }_k{\mathbf{d}}^{(k)}$

利用割线法展开一维线搜索需要用到目标函数的梯度$\nabla \mathbf{f}$ ，初始搜索点 ${\mathbf{x}}^{(0)}$ 和搜索方向 ${\mathbf{d}}^{(0)}$ 。 其确定方式为使函数

$${\varphi }_k(\alpha )=f\left({\mathbf{x}}^{(k)}+\alpha {\mathbf{d}}^{(k)}\right)$$

达到最小。

实际应用中存在一些常用的停止条件。首先, 选定 3 个常数: $\epsilon \in (0,1),\gamma >1$ 和 $\eta \in (\epsilon ,1)$ 。通过要求

$${\varphi }_k\left({\alpha }_k\right)⩽{\varphi }_k(0)+\epsilon {\alpha }_k{\varphi }_k^{\prime }(0)$$

可以保证 ${\alpha }_k$ 不会太大。通过要求（${\alpha }_k$ 乘上系数 $\gamma$ )

$${\varphi }_k\left(\gamma {\alpha }_k\right)⩾{\varphi }_k(0)+\epsilon \gamma {\alpha }_k{\varphi }_k^{\prime }(0)$$

可保证 ${\alpha }_k$ 不会太小。这称为 Armijo 条件。 如果将 Armijo 条件中第二个不等式调整为

$${\varphi }_k\left({\alpha }_k\right)⩾{\varphi }_k(0)+\eta {\alpha }_k{\varphi }_k^{\prime }(0)$$

就成为了 Goldstein 条件。 Armijo 条件中的第一个不等式和 Goldstein 条件联合称为 Armijo-Goldstein 条件。 Wolfe 条件只包括函数 ${\varphi }_k$ 的一阶导数 ${\varphi }_k^{\prime }$ :（对 goldstein条件关于 ${\alpha }_k$ 求导）

$${\varphi }_k^{\prime }\left({\alpha }_k\right)⩾\eta {\varphi }_k^{\prime }(0)$$

Wolfe 条件的一个变体称为强 Wolfe 条件:

$$\left|{\varphi }_k^{\prime }\left({\alpha }_k\right)\right|⩽\eta \left|{\varphi }_k^{\prime }(0)\right|$$

信赖域方法

定义 (信赖域： 迭代点 $x_k$ 的邻域) ${\Omega }_k:=\left\{x\mid \Vert x-x_k\Vert \le r_k\right\}$, 其中 $r_k$ 称为信赖域半径。

信赖域求解思想 在信赖域 ${\Omega }_k$ 内, 做函数 $f$ 的二次 Taylor逼近函数 $q_k$, 通过选取适当的信赖域 半径, 使得 $f$ 与 $q_k$ 逼近的效果足够好。我们称 $f\approx q_k$ 在 ${\Omega }_k$ 内是可信的。

信赖域模型：给定当前点 $x_k$ ，求解如下约束优化获得 $x_{k+1}$

$$\underset{x}{\min }{m}_k(x)=g_k^{\top }\underset{\mathcal{S}}{\underbrace{(x-x_k}})+\frac{1}{2}\underset{\mathcal{S}}{\underbrace{(x-x_k}}{)}^{\top }{B}_k\underset{\mathcal{S}}{\underbrace{(x-x_k}})\text{ s.t. }\underset{\mathcal{S}}{\underbrace{\Vert x-x_k}}\Vert \le r_k$$

• $B_k=I$, 基于梯度下降的信赖域方法
• $B_k={\nabla }^{2}f\left(x_k\right)$, 基于牛顿法的信赖域方法
• $B_k\approx {\nabla }^{2}f\left(x_k\right)$, 基于拟牛顿法的信赖域方法

与线搜索方法区别

两种方法比较|课程PPT

定义 $s:=x-x_k$, 则问题 (1) 可以写成 ${\min }_s{g}_k^{\top }s+\frac{1}{2}{s}^{\top }{B}_{k}s,$ s.t. $\Vert s\Vert \le r_k$ 信赖域子问题: $x_{k+1}=x_k+s_k$, 其中 $s_k$ 是如上优化问题的解

等价于求解如下 ${\ell }^p$ 范数球约束的二次规划问题

$$\min q(s)=\frac{1}{2}{s}^{\top }Bs+g^{\top }s\text{ s.t. }\Vert s\Vert \le 1\text{\hspace{1em}(2)}$$

当采用 ${\ell }^2$-范数时, 上述优化问题 (2) 的解为:

• 若 $g=0$, 则最优解为

$$s^{\ast }=\{\begin{array}{ll}0,& \text{ 如果 }{\lambda }_{\min }(B)\ge 0\\ {\lambda }_{\min }(B)\text{ 所对应的特征向量, }& \text{ 如果 }{\lambda }_{\min }(B)<0\end{array}$$

即 $B{s}^{\ast }={\lambda }_{\min }(B)s^{\ast }$ 且 ${\Vert s^{\ast }\Vert }_2=1$.

• 若 $g\ne 0$, 则需要用KKT条件求解优化问题 (2)

$$B{s}^{\ast }+g+{\lambda }^{\ast }{s}^{\ast }=0,\left({\Vert s^{\ast }\Vert }^2-1\right){\lambda }^{\ast }=0,{\lambda }^{\ast }\ge 0,B+{\lambda }^{\ast }I⪰0.$$

参考文献