局部搜索方法是解决无约束优化的一种方法，一般只能得到局部最优解。

如果自变量 $x$ 是一维的，即一个实数，我们要优化 $f(x)$ ，就只能将 $x$ 向左移动或向右移动，如下图所示。我们希望$f(x)$最大，就将 $x$ 向使能使$f(x)$增大的方向移动（左或右）。对于A和B，它们分别向右向左移动，最终到达全局最优点P；而对于C和D，它们只能到达局部最优点Q。所以这些方法称为局部搜索方法。一般来说，$x$ 是 $n$ 维向量，即$x \in \mathbb R^n$，这样的话，$x$可以移动的方向就有很多个。$n$ 维情况下，$f(x):\mathbb R^n \to \mathbb R$

局部搜索算法可分为线性搜索法(Line Search)和信赖域法(Trust Region)。

线性搜索法中：从初始点开始，先选出一个方向 $p_k$，然后沿这个方向，从当前迭代点 $x_k$ 开始，搜索出一个使目标函数值更低的新的迭代点 $x_{k+1}$（也可以视为确定一个前进的步长 $\alpha_k$），即
$$\min_{\alpha_k>0}f(x_k+\alpha_k p_k)$$一般来说，精确地求解 $\alpha_k$ 代价太大，求解的意义也不大，所以多使用近似结果。
信赖域法的思想则不同：信赖域法通过使用从 $f$ 中得到的信息来构建出一个函数 $m_k$ 使得 $m_k$ 和 $f$ 在 $x_k$ 附近十分近似，确定一个最大的边界限制 $\Delta$（超出这个边界后 $m_k$ 的近似效果不好），然后进行下面的最小化
$$\min_p m_k(x_k+p)\quad\quad \text{s.t. } ||p||_2<\Delta$$

本篇只介绍线性搜索法。

线性搜索法的一般过程：

找到初始点 $x^{(0)} \in \mathcal S$
设 $k=0$
$\mathtt {repeat}$
- 评价 $f(x_k)$
- 计算一个搜索方向 $p_k$
- 计算步长 $\alpha_k$
- 令$x_{k+1}$为$x_k+\alpha_k p_k$
- $k = k + 1$
$\mathtt {until}$ 终止条件满足
返回 $x_k$ 作为解

$x_k$ 指的是迭代 $k$ 次后 $x$ 的取值
终止条件一般使用精度，即梯度值；也就是说，再进行优化，每一步优化的效果微乎其微，小于一个我们设定好的值时，便停止迭代。另一种常用的终止条件就是显式地规定迭代次数。

1. 确定搜索方向

线性搜索法中最重要的一步就是确定搜索方向 $p_k$，一般有下面几种方法来确定 $p_k$：最速下降法，牛顿法，拟牛顿法。

1.1 最速下降法（Steepest Descent）

最速下降法是通过不断更新 $x$ 的值，使得$f(x)$不断变小，直到收敛。由于负梯度方向是使函数值下降最快的方向，所以在迭代的每一步，以负梯度方向更新$x$的值。

为什么负梯度下降速度最快
若第 $k$ 次迭代值为 $x_k$，则可以将 $f(x)$ 在 $x_k$ 附近进行一阶泰勒展开：
$$f(x) = f(x_k) + g_k \cdot (x-x_k)$$其中，$g_k=g(x_k)=\nabla f(x_k)$ 为 $f(x)$ 在 $x_k$ 的梯度。上面的式子是一维的情况，下面的式子是 $n$ 维的情况（即 $x$ 不再是一个实数，而是一个 $n$ 维向量）
$$f(x) = f(x_k) + g_k^T \cdot (x-x_k)$$则 $x-x_k = -g_k$ 时，$f(x)$ 下降最快（向量反向时内积最小）。

最速下降法的讨论

当目标函数是凸函数时，最速下降法的解是全局最优解。一般情况下，其解不保证是全局最优解。
最速下降法只利用了一阶导数的信息，计算量小，但在一些复杂问题上，收敛速度可能得不到保证。（详见参考资料2）
如果步长 $\alpha_k$ 是精确计算得到的，那么最速下降相邻两步的方向互相垂直，如下图所示

1.2 牛顿法

牛顿法使用函数的二阶导数信息来获得下降方向 $p_k$。用二阶泰勒展开近似 $f(x_k+p)$，我们得到
$$f(x_k+p)\simeq f(x_k)+p^T\nabla f_k+\frac{1}{2}p^T\nabla^2f_k p$$将上式右端记为 $m_k(p)$，若 $\nabla^2f_k$ 是正定的，我们就可以通过最小化 $m_k(p)$ 来找到方向 $p$
$$m’_k(p)=0 \quad \Rightarrow p_k^N=-\nabla^2f_k^{-1}\nabla f_k$$上标 $N$ 表示牛顿方向

由于 $\cfrac{\partial \mathbf{x}^T \mathbf{a}}{\partial \mathbf{x}}=\mathbf{a}$，$\cfrac{\partial\mathbf{x}^T\mathbf{B}\mathbf{x}}{\partial \mathbf{x}}=(\mathbf{B}+\mathbf{B}^T)\mathbf{x}$
$m’_k(p) = \nabla f_k+ \cfrac{1}{2}(\nabla^2f_k+(\nabla^2f_k)^T)p$
由于 $\nabla^2f_k$ 是正定的，则 $\nabla^2f_k=(\nabla^2f_k)^T$
故而 $m’_k(p) = \nabla f_k+ \nabla^2f_k p$

牛顿法的讨论

只有当 $f(x_k+p)$ 和 $m_k$ 之间的差距不大时，牛顿法才是可靠的
大多数牛顿法的线性搜索实现使用固定的步长 $\alpha=1$，只有当不能给出一个满意的目标函数下降时才会调节 $\alpha$
当 $\nabla^2f_k$ 不是正定的时候，牛顿方向无法定义，所以也就不存在牛顿法
由于牛顿法用到了二阶导数的信息，所以收敛速度很快

1.3 拟牛顿法

一般来说，计算Hessian矩阵是很耗时的，拟牛顿法的思想是用一个矩阵 $B_k$ 来近似真实的海塞矩阵 $\nabla^2f_k$，同时仍然保证超线性的收敛率。它是利用一阶导数的变化 $\nabla f_{k+1}-\nabla f_k$ 来近似得到二阶导数的信息。

$f(x)\approx f(x_{k+1})+\nabla f(x_{k+1})(x-x_{k+1})+\frac{1}{2}(x-x_{k+1})^T\nabla^2f(x_{k+1})(x-x_{k+1})$
两边关于 $x$ 求导可以得到
$\nabla f(x)\approx \nabla f(x_{k+1})+\nabla^2f(x_{k+1})(x-x_{k+1})$
令 $x=x_k$，则有
$\nabla f_k\approx \nabla f_{k+1}+\nabla^2f_{k+1}(x_k-x_{k+1})$
$\nabla^2f_{k+1}(x_{x+1}-x_k)\approx \nabla f_{k+1}-\nabla f_k$

故我们可以用 $B_{k}$ 来近似 $\nabla^2f_k$
$$B_{k+1}s_k=y_k$$其中 $s_k=x_{k+1}-x_k$，$y_k=\nabla f_{k+1}-\nabla f_k$
通常，我们还对 $B_k$ 做以下要求：

对称性：因为真实的海塞矩阵是对称的
低秩(Low Rank)：相邻两次近似 $B_k$ 和 $B_{k+1}$ 之间的差值是低秩的。

初始的近似值 $B_0$ 必须自己提供，更新 $B_k$ 时，有不同的更新公式，最著名的有以下两个：

对称秩一公式（Symmetric-Rank-One Formula）
$$B_{k+1}=B_k+\cfrac{(y_k-B_ks_k)(y_k-B_ks_k)^T}{(y_k-B_ks_k)^Ts_k}$$
BFGS公式
$$B_{k+1}=B_k-\cfrac{B_ks_ks_k^TB_k}{s_k^TB_ks_k}+\cfrac{y_ky_k^T}{y_k^Ts_k}$$
由拟牛顿法给出的搜索方向为
$$p_k=-B_k^{-1}\nabla f_k$$
在实际的实现中，更新的是 $B_k$ 的逆而不是 $B_k$，若定义 $H_k:=B_k^{-1}$，则有
$$H_{k+1}=H_k-\cfrac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}+\cfrac{s_ks_k^T}{s_k^Ty_k}$$
那么$p_k=-H_k\nabla f_k$

1.4 方向选择小结

大多数线性搜索算法需要选一个下降方向 $p_k$，即满足$$p_k^T\nabla f_k<0$$搜索方向通常具有以下形式$$p_k=-B_k^{-1}\nabla f_k$$
上述三种算法既可以总结为
$$B_k=\begin{cases}
I&\text{最速下降法}\\
\nabla^2 f(x_k)&\text{牛顿法} \\
\text{海塞矩阵的近似}&\text{拟牛顿法}
\end{cases}$$

2. 确定搜索策略

选择好搜索方向后，下一步要做的就是确定步长，一般有两种搜索策略：精确线搜索和非精确线搜索

2.1 精确线搜索

线搜索实际是一维最小化问题，目标是在一个闭区间 $[x_s,x_f]$ 上找到函数 $f$ 的最小值，一般我们假设 $f$ 是单峰函数，即在给定区间上只有一个最小值。有两种很优秀的方法：斐波那契搜索法和黄金分割搜索法。

通过测量许多点处的函数值 $f(x)$ 来确定 $f$ 的最小值点，或者说至少近似地确定。我们面临的挑战是：如何尽可能少地计算函数值同时得到一个尽可能小的区间 $[x’,x’’]$ 使得 $x\in[x’,x’’]$

以两个点 $x^1,x^2$ 为例，来展示基本的计算过程，其中 $x_s<x^1<x^2<x_f$：

如果 $f(x^1)<f(x^2)$，则丢弃区间 $[x^2,x_f]$
如果 $f(x^1)>f(x^2)$，则丢弃区间 $[x_s,x^1]$
如果 $f(x^1)=f(x^2)$，则上面两个区间均被丢弃

设 $f(\cdot)$ 是一个给定区间 $[x_s,x_f]$ 的单峰函数，如果我们打算只计算 $n$ 次函数值，我们应该怎么安排这 $n$ 个点的位置和顺序使得最终得到的区间 $[x’,x’’]$ 最小？

穷举搜索

穷举搜索很容易想到，即计算函数 $f(\cdot)$ 在预先确定的 $n$ 个点处的值，有 $x_s<x^1<\cdots<x^n<x_f$。如果这 $n$ 个值中的最小值是 $x_k$，那么最终确定的区间即为 $[x^{k-1},x^{k+1}]$，长度即为$$L_n=x^{k+1}-x^{k-1}=\cfrac{2}{n+1}L_0$$其中 $L_0=x_f-x_s$

二分搜索

如图，通过比较两点处的函数值 $f(\cdot)$，利用单峰性的假设，每次可以丢弃将近一半的区间。
$n$ 次后得到最终的区间长度为$$L_n=\cfrac{L_0}{2^{n/2}}+\delta(1-\cfrac{1}{2^{n/2}})$$

我们注意到：每次我们都需要计算新的两个点处的函数值 $f(x^1)$ 和 $f(x^2)$，丢弃掉的区间长度至少为 $\frac{1}{2}L_0-\cfrac{\delta}{2}$，剩下的区间长度至多为 $\frac{1}{2}L_0+\cfrac{\delta}{2}$。要使区间长度收缩得快，则越小 $\delta>0$ 更好，然而，当 $\delta$ 太小的时候，$x^1\simeq x^2$。
我们怎么能安全地分开 $x^1$ 和 $x^2$ 又不至于失去太多收缩速度？另一方面，在上面的二分搜索中，每次都需要计算两个新的点，我们怎么能是 $f(x^1),f(x^2)$ 的信息被多次利用呢？

斐波那契搜索

斐波那契数列
$F_0=F_1=1,\quad F_n=F_{n-1}+F_{n-2},\quad n=2,3,4,\cdots$
即 $\{F_n\}=\{1,1,2,3,5,8,13,21,\cdots\}$

在斐波那契搜索中，每次只需要计算一个新的划分点，即每次都会有一个点将会被再次作为划分点，二次利用。

定义$L_2^{*}=\cfrac{F_{n-2}}{F_n}L_0$，第一次划分的两个点距区间两端均为这个距离。利用单峰性，则新的区间为 $$L_2=L_0-L^{*}_2=L_0\left(1-\cfrac{F_{n-2}}{F_n}\right)=\cfrac{F_{n-1}}{F_n}L_0$$
不论是 $x^1$ 还是 $x^2$ 留在了新的区间 $L_2$ 中，都会有：它距区间一端的距离为$$L_2^{*}=\cfrac{F_{n-2}}{F_n}L_0=\cfrac{F_{n-2}}{F_{n-2}}L_2$$距另外一端的距离为$$L_2-L_2^{*}=\cfrac{F_{n-3}}{F_n}L_0=\cfrac{F_{n-3}}{F_{n-1}}L_2$$
我们新选择一个划分点 $x^3$ 使得 $L_2$ 内部的两个划分点距区间两端的距离均为$$L_3^{*}=\cfrac{F_{n-3}}{F_n}$$则这一轮产生的不确定区间的长度为$$L_3=L_2-L_3^{*}=L_2-\cfrac{F_{n-3}}{F_{n-1}}L_2=\cfrac{F_{n-2}}{F_{n-1}}L_2=\cfrac{F_{n-2}}{F_n}L_0$$
一般化的算法过程如下：$$L_j^{*}=\cfrac{F_{n-j}}{F_{n-(j-2)}}L_{j-1},\quad L_j=\cfrac{F_{n-(j-1)}}{F_n}L_0$$最终得到的区间长度为 $L_n=\frac{F_1}{F_n}L_0=\frac{1}{F_n}L_0$

黄金分割搜索

和斐波那契搜索类似，黄金分割搜索每次也只需要计算一个新的划分点，每次都会有一个点将会被再次作为划分点，二次利用，如下图所示。

则 $L_n=0.618^n L_0$

精确性 VS 代价

我们在计算步长 $\alpha_k$ 时，面临一个权衡：越精确地计算 $\alpha_k$，开销就会越大

2.2 非精确线搜索

大多数实际的策略都采用非精确线搜索的办法，在最小的计算开销下使函数值 $f(\cdot)$ 充分变小（考虑最小化问题）。经典的线搜索算法通常尝试一个 $\alpha$ 的序列，当满足某些停止条件时，选择那个 $\alpha$ 并结束。
下面来介绍一些不同的停止条件。

充分下降条件

一个常用的停止条件是 $\alpha_k$ 可以使目标函数 $f(\cdot)$ 产生充分的下降，即$$f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f_k^T p_k$$其中 $c_1 \in (0,1)$ 为一常数。

曲率条件

仅靠充分下降条件并不能保证算法每一步都能有很好的进步（make reasonable progress）。事实上，我们可以发现，当 $\alpha$ 充分小时，充分下降条件总是满足的。所以，算法可能会常常产生令人无法接受的小步长。
为了避免这种情况，我们引入另一个条件，称为曲率条件，即需要 $\alpha_k$ 满足$$\nabla f(x_k+\alpha_k p_k)^T p_k\ge c_2\nabla f_k^T p_k$$其中 $c_2 \in (0,1)$ 为一常数。

Wolfe条件

将上面两个条件结合起来，就得到了Wolfe条件，如图

强Wolfe条件

强Wolfe条件对 $\alpha_k$ 的限制为 $$\begin{array}{c}f(x_k+\alpha_k p_k)\le f(x_k)+c_1\alpha_k\nabla f_k^T p_k \\
|\nabla f(x_k+\alpha_k p_k)^T p_k|\le c_2|\nabla f_k^T p_k|
\end{array}$$
注意到，这个条件比上面只多了绝对值符号。强Wolfe条件实际上限制了 $\phi’(\alpha_k)$ 不能为一个很大的正数，即可行的 $\alpha$ 不能离最低点太远。

Goldstein条件

像Wolfe条件一样，Goldstein条件也保证了步长 $\alpha$ 不至于太小，同时又能使函数值 $f$ 产生充分下降。

后向跟踪方法（Backtracking Approach）

如果备选的步长合适，那么通过后向跟踪方法，我们可以只用充分下降条件来做终止条件，同时选出一个不错的步长。（因为这时候 $\alpha$ 是从大往小变化，所以不可能变得太小）

Choose $\overline{\alpha}>0,\rho,c\in(0,1)$；set $\alpha\leftarrow\overline{\alpha}$
repeat until $f(x_k+\alpha p_k)\le f(x_k)+c\alpha\nabla f_k^T p_k$
$\qquad \alpha\leftarrow\rho\alpha$
end(repeat)
Terminate with $\alpha_k=\alpha$

特点：

在有限次尝试后可以得到一个可接受的步长
最终得到的步长要么是给定的值 $\overline{\alpha}$，要么就是一个比较小（但不是过于小）的满足充分下降条件的步长
在实际中，收缩因子 $\rho$ 通常被设置为在每轮迭代中在一个区间 $[\rho_{\text{lo}},\rho_{\text{hi}}]$
这种简单的终止线搜索的方法很适合牛顿法

凸二次规划
特别地，对于凸二次规划 $f(x)=\frac{1}{2}x^TQx+b^Tx+c$，$\min_{\alpha>0}\phi(\alpha)=f(x_k+\alpha p_k)$ 可以直接计算出结果$$\alpha_k=-\cfrac{\nabla f_k^Tp_k}{p_k^TQp_k}$$
对于其它一般非线性函数，则需要用迭代的方法求解。

局部搜索方法——线性搜索