Skip to content

Latest commit

 

History

History
157 lines (94 loc) · 4.93 KB

线搜索.md

File metadata and controls

157 lines (94 loc) · 4.93 KB
Raw

无约束非线性优化

Unconstrained Nonlinear Programming

一个典型的UNP问题可以写为： $$ \text{minimize} \ f(x) $$

通用下降方法

General Descent Method

是一种用迭代的方式求目标函数最小值的方法，每次迭代都会计算搜索方向和步长 $$ x_{k+1} = x_k + t_k p_k $$

其中，$p$ 是搜索方向， $t$ 是步长

之所叫下降方法，是因为满足 $f\left(x_{k+1}\right)<f\left(x_{k}\right)$

下降方向

Descent Direction

引入梯度（Gradient）的概念，用 $\nabla$ 来表示，梯度默认指正梯度，这里下降使用的是负梯度，即 $-\nabla f(x)$ 。只要搜索方向和负梯度方向的夹角小于90°，且步长合适的情况下，都是下降方向，表示为：$\nabla f\left(x_{k}\right)^{T} p_{k}<0$ 。

搜索方向有个一般式： $p_k=−B_k^{−1}\nabla f(x_k)$

其中 $B_k$ 是一个对称非奇异矩阵，有以下几种常见的下降方法

  1. 梯度下降法（也叫最陡下降法）（Steepest Descent）

    $B_k$ 是单位阵，即直接选负梯度为搜索方向，表示为：$p_{k}=-\nabla f\left(x_{k}\right)$

  2. 牛顿方法（Newton）

    $B_k = ∇^2f(x_k)$ 是海森（Hessian）矩阵

  3. 拟牛顿法

  4. 共轭梯度法

补充一点，我们将一般式两边同乘，得到 $\nabla f\left(x_{k}\right)^{T} p_k=−\nabla f\left(x_{k}\right)^{T} B_k^{−1}\nabla f(x_k)$，当 $B_k$ 是正定矩阵时，$B_k^{-1}$ 也是正定的，因此根据正定的性质，这个式子是满足 $\nabla f\left(x_{k}\right)^{T} p_k &lt; 0$ 的，印证了下降方向。

步长

Stepsize

很多时候我们用的步长是一个固定值，但在这里，我们使用线搜索（Line Search）的方法，每一次迭代都会重新计算步长，有两种方式：

  1. 精确线搜索（Exact Line Search）

    求解下面这个优化问题，其实很容易理解。步长如果太小，则下降不够快；步长如果太大，则可能不降反升，因此我们想找到步长的一个上界。 $$ t_k = \underset{\alpha \geq 0}{\arg\min} f(x_k + \alpha p_k) $$

  2. 回溯线搜索（Backtracking Line Search）

    上面精确计算有时候会很复杂，其实只要近似估计就可以了，设想是先初始化一个较大的步长，然后逐渐缩小，以使得新的函数值与旧的函数值的减少程度大于预设的期望值。可以考虑步长从单位1开始。

    如果 $f(x_k+t_k p_k)&gt;f(x_k)+\alpha t_k \nabla f(x_k)^{T} p_k$ ，则令 $t_{k+1} = \beta t_k$

    其中 $\alpha \in(0,0.5)$ $\beta \in(0,1)$ $t_0 = 1$

    $f(x_k+t_k p_k) \leq f(x_k)+\alpha t_k \nabla f(x_k)^{T} p_k$ 被称为Armijo准则，和 $\nabla f\left(x_{k}+t_{k} p_{k}\right)^{T} p_{k} \geq \alpha_{2} \nabla f(x_k)^{T} p_{k}$ 一起构成了Wolfe条件

补充：之所以叫线搜索是因为选定的步长 $t$ 将决定从直线 {$x+tp$} 上哪一点开始下一步迭代，其实更准确的应该被叫做射线搜索（Ray Search）

需要知道Armijo准则是一定能满足的，因为只要步长足够小，就一定有 $$ f(x+t \Delta x) \approx f(x)+t \nabla f(x)^{T} \Delta x<f(x)+\alpha t \nabla f(x)^{T} \Delta x $$

例子

用梯度下降和精确先搜索方法求解如下问题： $$ \text { minimize } f(x)=\frac{1}{2}\left(x_{1}^{2}+\gamma x_{2}^{2}\right) $$

  1. 确定搜索方向，这里直接用负梯度： $$ p_k = (-x_{1(k)}, -\gamma x_{2(k)})^T $$

  2. 确定步长： $$ t_k = \underset{\alpha \geq 0}{\arg\min} \frac{1}{2}\left[(1-\alpha)^{2} x_{1(k)}^{2}+\gamma(1-\alpha \gamma)^{2} x_{2(k)}^{2}\right] $$ 可以直接用配方法得到： $$ t_k = \frac{x_{1(k)}^2 + \gamma^2 x_{2(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} $$

  3. 应用下降方法： $$ x_{k+1} = x_k + \frac{x_{1(k)}^2 + \gamma^2 x_{2(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} (-x_{1(k)}, -\gamma x_{2(k)})^T $$ 将 $x_1, x_2$ 分成两项即： $$ x_{1(k+1)} = x_{1(k)} - \frac{x_{1(k)}^2 + \gamma^2 x_{2(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} x_{1(k)} = \frac{(\gamma - 1)\gamma^2 x_{2(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} x_{1(k)} $$

    $$ x_{2(k+1)} = x_{2(k)} - \frac{x_{1(k)}^2 + \gamma^2 x_{2(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} \gamma x_{2(k)} = \frac{(1 - \gamma) x_{1(k)}^2}{x_{1(k)}^2 + \gamma^3 x_{2(k)}^2} x_{2(k)} $$

  4. 选择一个初始点开始迭代，这里选一个较特殊的点 $x_{1(0)} = \gamma$，$x_{2(0)} = 1$

    当 $k =0$ 时，有： $$ x_{1(1)} = \gamma\left(\frac{\gamma-1}{\gamma+1}\right) $$

    $$ x_{2(1)} = -\left(\frac{\gamma-1}{\gamma+1}\right) $$

    当 $k =1$ 时，有： $$ x_{1(2)} = \gamma\left(\frac{\gamma-1}{\gamma+1}\right)^2 $$

    $$ x_{2(2)} = -\left(\frac{\gamma-1}{\gamma+1}\right)^2 $$

    通过数学归纳法，我们可以得到一个通式：

    $$ x_{1(k)} = \gamma\left(\frac{\gamma-1}{\gamma+1}\right)^k $$

    $$ x_{2(k)} = -\left(\frac{\gamma-1}{\gamma+1}\right)^k $$