目录
线搜索
对于迭代式 x k + 1 = x k + α p k x_{k+1} = x_k +\alpha p_k xk+1=xk+αpk，其中 p k p_k pk是由梯度法，牛顿法，CG法等方法计算出的下降方向， α \alpha α是下降的步长。
- 寻找最优值 α = min α f ( x k + α p k ) \alpha = {\underset {\alpha}{\operatorname {min} }} f(x_k + \alpha p_k) α=αminf(xk+αpk)的过程称为精确搜索
- 如果只是想找到一个 α \alpha α使得 f ( x k + α p k ) f(x_k + \alpha p_k) f(xk+αpk)相对于 f ( x k ) f(x_k) f(xk)有足够的下降，那么这样的过程称为非精确搜索
非精确线搜索（Armijo条件，Wolfe条件，Goldstein条件）
Armijo条件
要求
f
(
x
k
+
α
p
k
)
f(x_k + \alpha p_k)
f(xk+αpk)相对于
f
(
x
k
)
f(x_k)
f(xk)有足够的下降，可以写作：
f
(
x
k
+
α
p
k
)
≤
f
(
x
k
)
+
c
1
α
∇
f
(
x
k
)
T
p
k
f(x_k + \alpha p_k) \leq f(x_k) + c_1\alpha \nabla f(x_k)^T p_k
f(xk+αpk)≤f(xk)+c1α∇f(xk)Tpk
因为
f
(
x
k
)
T
p
k
<
0
f(x_k)^T p_k < 0
f(xk)Tpk<0，所以要求
c
1
>
0
c_1 > 0
c1>0，但如果
c
1
≥
1
c_1 \geq 1
c1≥1那么对于某些函数（例如强凸函数）就找不到满足不等式的解。因此上式中
c
1
∈
(
0
,
1
)
c_1 \in (0,1)
c1∈(0,1)。
记
ϕ
(
α
)
=
f
(
x
k
+
α
p
k
)
,
l
(
α
)
=
f
(
x
k
)
+
c
1
α
∇
f
(
x
k
)
T
p
k
\phi(\alpha) = f(x_k + \alpha p_k), l(\alpha) = f(x_k) + c_1\alpha \nabla f(x_k)^T p_k
ϕ(α)=f(xk+αpk),l(α)=f(xk)+c1α∇f(xk)Tpk，那么Armijo条件框定的范围如下：
实际应用中，
c
1
c_1
c1一般取得很小，例如
c
1
=
1
0
−
4
c_1 = 10^{-4}
c1=10−4
curvature条件
从上图不难发现只要
α
\alpha
α足够小就会满足Armijo条件，但这样会导致下降的量不够大，为了避免
α
\alpha
α取过小的值，又有了下面的的curvature条件：
∇
f
(
x
k
+
α
k
p
k
)
T
p
k
≥
c
2
∇
f
(
x
k
)
T
p
k
\nabla f(x_k + \alpha_k p_k)^T p_k \geq c_2 \nabla f(x_k)^T p_k
∇f(xk+αkpk)Tpk≥c2∇f(xk)Tpk
其中
c
2
∈
(
c
1
,
1
)
c_2 \in (c_1, 1)
c2∈(c1,1)。
- 如果满足上式， ∇ f ( x k + α k p k ) T p k \nabla f(x_k + \alpha_k p_k)^T p_k ∇f(xk+αkpk)Tpk要么是轻微的负值（表明 x k + α k p k x_k + \alpha_k p_k xk+αkpk已经趋于极小值附近），要么是正值（表明 x k + α k p k x_k + \alpha_k p_k xk+αkpk已经越过了极小值），那么此时停止线搜索是合理的
- 如果不满足上式， ∇ f ( x k + α k p k ) T p k \nabla f(x_k + \alpha_k p_k)^T p_k ∇f(xk+αkpk)Tpk就是负得比较多的负值，那么说明在 p k p_k pk方向 f f f还有比较大的下降空间，可以继续搜索更优的 α \alpha α值
上式等价于 ϕ ′ ( α k ) ≥ c 2 ϕ ′ ( 0 ) \phi'(\alpha_k) \geq c_2 \phi'(0) ϕ′(αk)≥c2ϕ′(0)，因此curvature条件框住的范围为：
由上图可以看出curvature条件可以避开很小的
α
\alpha
α。一般情况如果
p
k
p_k
pk是Newton或者quasi-Newton法求得的方向，那么
c
2
=
0.9
c_2 = 0.9
c2=0.9，如果
p
k
p_k
pk是非线性CG法求得的，那么
c
2
=
0.1
c_2 = 0.1
c2=0.1。
Wolfe条件，强Wolfe条件
Wolfe条件 = Armijo条件 + curvature条件
f
(
x
k
+
α
k
p
k
)
≤
f
(
x
k
)
+
c
1
α
k
∇
f
(
x
k
)
T
p
k
∇
f
(
x
k
+
α
k
p
k
)
T
p
k
≥
c
2
∇
f
(
x
k
)
T
p
k
\begin{aligned} f(x_k + \alpha_k p_k) &\leq f(x_k) + c_1\alpha_k \nabla f(x_k)^T p_k\\ \nabla f(x_k + \alpha_k p_k)^T p_k &\geq c_2 \nabla f(x_k)^T p_k \end{aligned}
f(xk+αkpk)∇f(xk+αkpk)Tpk≤f(xk)+c1αk∇f(xk)Tpk≥c2∇f(xk)Tpk
其中
0
<
c
1
<
c
2
<
1
0< c_1 < c_2 < 1
0<c1<c2<1
但Wolfe条件找到的
α
\alpha
α有可能离极小值较远，比如：
因此又提出了强Wolfe条件:
f
(
x
k
+
α
k
p
k
)
≤
f
(
x
k
)
+
c
1
α
k
∇
f
(
x
k
)
T
p
k
∣
∇
f
(
x
k
+
α
k
p
k
)
T
p
k
∣
≤
c
2
∣
∇
f
(
x
k
)
T
p
k
∣
\begin{aligned} f(x_k + \alpha_k p_k) &\leq f(x_k) + c_1\alpha_k \nabla f(x_k)^T p_k\\ |\nabla f(x_k + \alpha_k p_k)^T p_k| &\leq c_2 |\nabla f(x_k)^T p_k| \end{aligned}
f(xk+αkpk)∣∇f(xk+αkpk)Tpk∣≤f(xk)+c1αk∇f(xk)Tpk≤c2∣∇f(xk)Tpk∣
与Wolfe条件相比，强Wolfe条件不允许
ϕ
′
(
α
k
)
\phi'(\alpha_k)
ϕ′(αk)正得太大，也就是不能越过极小值太远。
(Wolfe条件存在性定理)假设 f : R n → R f: \mathbb{R^n} \rightarrow \mathbb{R} f:Rn→R连续可微， p k p_k pk是 x k x_k xk处的下降方向，并且 f f f在 { x k + α p k ∣ α > 0 } \{x_k + \alpha p_k | \alpha > 0\} {xk+αpk∣α>0}上有下界。如果 0 < c 1 < c 2 < 1 0 < c_1 < c_2 <1 0<c1<c2<1，那么存在一个步长区间即满足Wolfe条件也满足强Wolfe条件
Proof：因为
ϕ
(
α
)
=
f
(
x
k
+
α
p
k
)
\phi(\alpha) = f(x_k + \alpha p_k)
ϕ(α)=f(xk+αpk)有下界，而
l
(
α
)
=
f
(
x
k
)
+
c
1
α
∇
f
(
x
k
)
T
p
k
l(\alpha) = f(x_k) + c_1\alpha \nabla f(x_k)^T p_k
l(α)=f(xk)+c1α∇f(xk)Tpk是*减函数，因此
l
(
α
)
l(\alpha)
l(α)和
ϕ
(
α
)
\phi(\alpha)
ϕ(α)一定有交点。记
α
′
\alpha'
α′为最小的交点，那么有：
f
(
x
k
+
α
′
p
k
)
=
f
(
x
k
)
+
c
1
α
′
∇
f
(
x
k
)
T
p
k
f(x_k + \alpha' p_k) = f(x_k) + c_1\alpha' \nabla f(x_k)^T p_k
f(xk+α′pk)=f(xk)+c1α′∇f(xk)Tpk
并且对所有小于
α
′
\alpha'
α′的值，Armijo条件都成立。
又由中值定理，存在
α
′
′
∈
(
0
,
α
′
)
\alpha'' \in (0, \alpha')
α′′∈(0,α′)使得：
f
(
x
k
+
α
′
p
k
)
−
f
(
x
k
)
=
α
′
∇
f
(
x
k
+
α
′
′
p
k
)
T
p
k
f(x_k + \alpha' p_k) - f(x_k) = \alpha' \nabla f(x_k + \alpha'' p_k)^T p_k
f(xk+α′pk)−f(xk)=α′∇f(xk+α′′pk)Tpk
⇒
∇
f
(
x
k
+
α
′
′
p
k
)
T
p
k
=
c
1
f
(
x
k
)
T
p
k
≥
c
2
f
(
x
k
)
T
p
k
\Rightarrow \nabla f(x_k + \alpha'' p_k)^T p_k = c_1 f(x_k)^T p_k \geq c_2 f(x_k)^T p_k
⇒∇f(xk+α′′pk)Tpk=c1f(xk)Tpk≥c2f(xk)Tpk
因此
α
′
′
\alpha''
α′′满足Wolfe条件，又由f的连续可微性，
α
′
′
\alpha''
α′′的领域也满足Wolfe条件，
c
1
f
(
x
k
)
T
p
k
c_1 f(x_k)^T p_k
c1f(xk)Tpk又是负值，因此该区间也满足强Wolfe条件，得证。
Goldstein条件
Goldstein条件如下：
f
(
x
k
)
+
(
1
−
c
)
α
k
∇
f
(
x
k
)
T
p
k
≤
f
(
x
k
+
α
k
p
k
)
≤
f
(
x
k
)
+
c
α
k
∇
f
(
x
k
)
T
p
k
f(x_k) + (1-c)\alpha_k \nabla f(x_k)^T p_k \leq f(x_k + \alpha_k p_k) \leq f(x_k) + c\alpha_k \nabla f(x_k)^T p_k
f(xk)+(1−c)αk∇f(xk)Tpk≤f(xk+αkpk)≤f(xk)+cαk∇f(xk)Tpk
其中
0
<
c
<
1
/
2
0 < c < 1/2
0<c<1/2
上式的右边即为Armijo条件，而左边是为了避免找到的
α
\alpha
α太小：
但Goldstein条件的问题是它左边的不等式有可能会将所有的极小值点排除在外。一般情况下Goldstein条件常用于Newton-type方法，但不适用于quasi-Newton方法
Backtracking线搜索
因为Wolfe条件的实现比较复杂，如果只是为了解决Armijo条件可能取值太小的问题，我们可以使用Backtracking线搜索：
只要初始的
α
‾
\overline{\alpha}
α取得足够大，那么Backtracking线搜索方法就可以找到一个足够大的满足Armijo条件的
α
\alpha
α。
强Wolfe条件线搜索算法
如果要使用Wolfe条件来搜索步长，[3]中提供了如下两步式算法：
算法解释如下：
- 如果 ϕ ( α i ) > ϕ ( 0 ) + c 1 α i ϕ ′ ( 0 ) \phi(\alpha_i) > \phi(0) + c_1 \alpha_i \phi'(0) ϕ(αi)>ϕ(0)+c1αiϕ′(0)（即 α i \alpha_i αi不满足Armijo条件）；或者 ϕ ( α i ) > ϕ ( α i − 1 ) \phi(\alpha_i) > \phi(\alpha_{i-1}) ϕ(αi)>ϕ(αi−1)；或者 ϕ ′ ( α i ) ≥ 0 \phi'(\alpha_i) \geq 0 ϕ′(αi)≥0均说明 α i \alpha_i αi已经越过了极小值点 ϕ ( α ) \phi(\alpha) ϕ(α)开始上升了，因此区间 ( α i − 1 , α i ) (\alpha_{i-1}, \alpha_i) (αi−1,αi)包含了满足强Wolfe条件的点，则转入zoom算法在区间 ( α i − 1 , α i ) (\alpha_{i-1}, \alpha_i) (αi−1,αi)中寻找符合条件的 α \alpha α
- 如果 ϕ ( α i ) ≤ ϕ ( 0 ) + c 1 α i ϕ ′ ( 0 ) \phi(\alpha_i) \leq \phi(0) + c_1 \alpha_i \phi'(0) ϕ(αi)≤ϕ(0)+c1αiϕ′(0)并且 ∣ ϕ ′ ( α i ) ∣ ≤ − c 2 ϕ ′ ( 0 ) |\phi'(\alpha_i)| \leq -c_2\phi'(0) ∣ϕ′(αi)∣≤−c2ϕ′(0)，那么 α i \alpha_i αi即是满足强Wolfe条件的步长，搜索停止
- 若上述都不符合，则迭代重复以上。一般这个位置会设置一个最大迭代次数，避免线搜寻陷在某一步一直出不来
Reference:
- Numerical Optimization, Jorge Nocedal, Stephen J. Wright, 2006