线搜索每一次迭代首先计算搜索方向$p_k$,然后计算在这个方向上移动的 距离$a_k$。迭代式如下：
(1)$$x_{k+1}=x_k+a_kp_k$$
线搜索方法的成功依赖于能否有效选取方向$p_k$和步长$a_k$。
大多数线搜索方法需要$p_k$是下降方向，即$p_k^T \nabla f_k<0$，这个属性能够保证$f$沿着这个方向减小。搜索方向通常有如下形式：
(2)
$$
p_k =-B_k^{-1}\nabla f_k
$$
这里$B_k$是对称非奇异矩阵。在最速下降法中，$B_k$是单位矩阵。在牛顿方法中，$B_k$是Hessian矩阵$\nabla ^2 f(x_k)$。在拟牛顿方法中，$B_k$是Hessian矩阵的近似。当$P_k$定义为(2)式且$B_k$正定时，我们有：
$$
p_k^T \nabla f_k=-\nabla f^T_kb_k^{-1} \nabla f_k <0
$$
步长
定义全局最小值：
$$\phi(a)=f(x_k + a p_k),a>0$$
典型的线搜索方法会实验一系列$a$的候选值，当特定的条件满足时就接受某个值。
WOLFE条件
(4)为Armijo条件，(5)为曲率条件。
(4)
$$f(x_k + a_k p_k) \leq f(x_k) +c_1 a_k \nabla f_k^Tp_k$$
(5)
$$\left | \nabla f(x_k +a_k p_k)^Tp_k \right | \leq c_2 \left | \nabla f_k^T p_k \right |$$
其中$0<c_1<c_2<1$。
对于有界光滑函数$f$存在满足WOLFE条件的步长$a_k$。
1.2 GOLDSTEN条件
$$f(x_k) + (1-c) a_k \nabla f_k^T p_k \leq f(x_k + a_k p_k) \leq f(x_k) +ca_k \nabla f_k^Tp_k$$
其中$0<c<1/2$。
回溯线搜索
算法
选择$\bar{a} >0$，$\rho \in (0,1)$，$c \in (0,1)$；赋值$a \gets \bar{a}$
循环直到 $f(x_k + a p_k) \leq f(x_k) +ca \nabla f_k^Tp_k$
$a \gets \rho a$
结束循环
终止：$a_k \gets a$
在这个过程中，初始步长$\bar{a}$在牛顿和拟牛顿方法中选为1，在其他算法中可以选择其他值。经过有限步的试验之后，最终能发现一个可接受的步长，因为$a_k$足够小以满足充分下降条件，而又不太小。实践中，约束因子$\rho$在每一次迭代中可变。例如，我们可以使用插值来选择。我们需要保证在每一次迭代中，$\rho \in [\rho _{lo},\rho _{hi}]$，这里使用固定的常熟$0 < \rho _{lo} < \rho _{hi} <1$
这个简单而流行的策略非常适合牛顿方法，而不适合拟牛顿方法和共轭梯度法。
线搜索方法的收敛
为了获得全局收敛，我们不仅要得到一个合适的步长，还要选择合适的方向。一个重要的属性是：$p+k$和最速下降方向$-\nabla f_k$之间的角度$\theta _k$可以定义如下：
$$
cos \theta _k = \frac {-\nabla f_k^T p_k}{\lVert \nabla f_k \rVert \lVert p_k \rVert}
$$
定理 （利普希茨连续条件）
假定$f$是在$R^n$下有界，在包含水平集$L \overset{def}{=} {x:f(x) \leq f(x_0)}$ （$x_0$是迭代起点）的开集$N$上连续可导，那么存在常数$L>0$使得
$$
\lVert \nabla f(x) -\nabla f(\tilde a) \leq L \rVert x- \tilde x \rVert , \text{for all }x,\tilde x \in N
$$
那么可以得到Zoutendijk条件
$$
\sum_{k \geq 0}{cos^2 \theta _k \lVert \nabla f_k \rVert ^2 <\infty}
$$
Zoutendijk条件表明
$$
cos^2 \theta _k \lVert \nabla f_k \rVert ^2 \rightarrow 0
$$
如果我们的方法 $p_k$保证角度$\theta _k$在90度范围内，那么有正的常数$\delta$
$$
cos \theta _k \geq \delta >0,\text{for all k}
$$
所以
$$
\underset {k \rightarrow \infty}{\text{lim}} \lVert \nabla f_k \rVert =0
$$
收敛速率
Hessian修正的牛顿方法
Hessian矩阵$\nabla ^2 f(x)$可能不是正定的，所以牛顿方向
$p_k^N$:
$$
\nabla ^2 f(x_k)p_k^N=-\nabla f(x_k)
$$
可能不是下降方向。
算法
给定初始点$x_0$;
for k=0,1,2,…
分解矩阵$B_k=\nabla ^2 f(x_k) +E_k$,如果$\nabla ^2 f(x_k)$充分正定，那么$E_k=0$，否则选择一个$E_k$使之充分正定。
求解：$B_kp_k=-\nabla f(x_k)$
$x_{k+1} \gets x_k +a_k p_k/4，这里$a_k$满足Whofe,Goldstein或者Aemijo回溯条件。
end
特征值改进
修正的乔勒斯基分解
原创文章，转载请注明出处。
刘文武 2016年9月7日 于 电子科大航空航空学院
