不精确一维搜索——Armijo-Goldstein方法
文章目录
不精确一维搜索
不精确一维搜索法是求一维函数在区间 [ 0 , ∞ ) [0, \infty) [0,∞) 上的近似极小值，而这个近似精度由一个可接受参数来度量，用不精确一维搜索能求得极值的条件是函数在零点处的导数小于0，即 f ′ ( 0 ) < 0 f^{\prime}(0)<0 f′(0)<0 。主要有两种不精确一维搜索法：Armijo-Goldstein法和Wolfe-Powell法。
Armijo-Goldstein准则
Armijo-Goldstein准则的核心思想有两个：
①目标函数值应该有足够的下降；②一维搜索的步长 λ \lambda λ不应该太小。
这两个思想的意图非常明显。由于最优化问题的目的就是寻找极小值，因此，让目标函数函数值“下降”是我们努力的方向，所以①正是想要保证这一点。
同理，②也类似：如果一维搜索的步长 λ \lambda λ太小了，那么我们的搜索类似于在原地打转，可能也是在浪费时间和精力。
有了这两个指导思想，我们来看看Armijo-Goldstein准则的数学表达式：
f
(
x
k
+
λ
k
d
k
)
−
f
(
x
k
)
≤
λ
k
ρ
g
k
T
d
k
(1)
\begin{array}{l} f\left(x^{k}+\lambda_{k} d^{k}\right)-f\left(x^{k}\right) \leq \lambda_{k} \rho g_{k}^{T} d^{k}\\ \end{array}\tag{1}
f(xk+λkdk)−f(xk)≤λkρgkTdk(1)
f ( x k + λ k d k ) − f ( x k ) ≥ λ k ( 1 − ρ ) g k T d k (2) \begin{array}{l} f\left(x^{k}+\lambda_{k} d^{k}\right)-f\left(x^{k}\right) \geq \lambda_{k}(1-\rho) g_{k}^{T} d^{k} \end{array}\tag{2} f(xk+λkdk)−f(xk)≥λk(1−ρ)gkTdk(2)
其中， 0 < ρ < 1 2 0 < \rho < \frac{1}{2} 0<ρ<21
公式推导
在非精确一维搜索中，通常要求 f ( x k + 1 ) f(x^{k+1}) f(xk+1)比 f ( x k ) f(x^{k}) f(xk)下降一定的数量，从而使得 f ( x k + 1 ) − f ( x k ) f(x^{k+1})-f(x^{k}) f(xk+1)−f(xk)达到一个满意水平，此时的 λ k \lambda_k λk，就是可接受步长。
如何选取可接受步长 λ k \lambda_k λk呢?
(1)不等式的左边式子的泰勒展开式为：
f
(
x
k
+
λ
k
d
k
)
=
f
(
x
k
)
+
λ
k
g
k
T
d
k
+
o
(
∥
λ
k
d
k
∥
)
(3)
f({x^k} + {\lambda_k}{d^k}) = f({x^k}) + {\lambda_k}{g_k}^T{d^k} + o(\|{\lambda_k}{d_k}\|)\tag{3}
f(xk+λkdk)=f(xk)+λkgkTdk+o(∥λkdk∥)(3)
其中
g
k
=
▽
f
(
x
k
)
{g_k} = \triangledown f({x^k})
gk=▽f(xk),我们已知了
g
k
T
d
k
<
0
{g_k}^T{d^k} < 0
gkTdk<0（这是
d
k
{d^k}
dk 为下降方向的充要条件），并且
0
<
ρ
<
1
2
0 < \rho < \frac{1}{2}
0<ρ<21
去掉高阶无穷小，剩下的部分为： f ( x k ) + λ k g k T d k f({x^k}) + {\lambda_k}{g_k}^T{d^k} f(xk)+λkgkTdk
而(*)不等式右边与之只差一个系数 ρ \rho ρ
因此，3式右边仍然是一个比
f
(
x
k
)
f({x^k})
f(xk) 小的数，即：
f
(
x
k
)
+
λ
k
ρ
g
k
T
d
k
<
f
(
x
k
)
f({x^k}) + {\lambda_k}\rho{g_k}^T{d^k}< f({x_k})
f(xk)+λkρgkTdk<f(xk)
也就是说函数值是下降的（下降是最优化的目标）。
由于
g
k
T
d
k
<
0
{g_k}^T{d^k} < 0
gkTdk<0，并且
0
<
ρ
<
1
2
0 < \rho < \frac{1}{2}
0<ρ<21，故
（
2
）
（2）
（2）式子右边比
（
1
）
（1）
（1）式子右边要小，即：
λ
k
(
1
−
ρ
)
g
k
T
d
k
<
λ
k
ρ
g
k
T
d
k
<
0
{\lambda_k}(1-\rho){g_k}^T{d^k} < {\lambda_k}\rho{g_k}^T{d^k} < 0
λk(1−ρ)gkTdk<λkρgkTdk<0
如果步长
λ
k
\lambda_k
λk太小的话，会导致这个不等式接近于不成立的边缘。因此，式2就保证了
λ
k
\lambda_k
λk不能太小。
为减少计算量,可以给出
f
f
f下降量的一个合适的下界
f
(
x
k
)
−
f
(
x
k
+
λ
d
k
)
≥
−
λ
ρ
g
k
T
d
k
f\left(x^{k}\right)-f\left(x^{k}+\lambda d^{k}\right) \geq-\lambda \rho g_{k}^{T} d^{k}
f(xk)−f(xk+λdk)≥−λρgkTdk
并且只需要
f
f
f下降到一定程度，比如要求下降量不超过
−
λ
k
(
1
−
ρ
)
g
k
T
d
k
-{\lambda_k}(1-\rho){g_k}^T{d^k}
−λk(1−ρ)gkTdk，即
f
(
x
k
)
−
f
(
x
k
+
λ
d
k
)
≤
−
λ
(
1
−
ρ
)
g
k
T
d
k
f\left(x^{k}\right)-f\left(x^{k}+\lambda d^{k}\right) \leq-\lambda(1-\rho) g_{k}^{T} d^{k}
f(xk)−f(xk+λdk)≤−λ(1−ρ)gkTdk
这就是Armijo-Goldstein准则，交换下位置就得到了 （ 1 ） 和 （ 2 ） （1）和（2） （1）和（2）
Armijo-Goldstein法
- 原理：从原点出发进行探测，探测点能够接受的上限值为 f ( 0 ) + σ 1 t k f ′ ( 0 ) f(0)+\sigma_{1} t_{k} f^{\prime}(0) f(0)+σ1tkf′(0) ，如果探测点处的函数值小于此值，则减小探测步长；探测点能够接受的下限值为 f ( 0 ) + σ 2 t k f ′ ( 0 ) f(0)+\sigma_{2} t_{k} f^{\prime}(0) f(0)+σ2tkf′(0) ，如果探测点处的函数值大于此值（且小于上限值），则停止迭代输出结果，否则增大迭代步长。
- 算法步骤：用Armijo-Goldstein法求无约束问题 min f ( x ) , x ∈ R \min f(x), x \in \mathbf{R} minf(x),x∈R 的算法步骤如下
【1】在搜索区间 [ 0 , ∞ ) [0, \infty) [0,∞) 或 ( [ 0 , λ max ] ) \left(\left[0, \lambda_{\max }\right]\right) ([0,λmax])上取定初始探测点，计算 f ( 0 ) , f ′ ( 0 ) f(0), f^{\prime}(0) f(0),f′(0) ，给出可接受系数 σ 1 ∈ ( 0 , 1 ) \sigma_{1} \in(0,1) σ1∈(0,1) 和 σ 2 ( σ 2 > σ 1 ) \sigma_{2}\left(\sigma_{2}>\sigma_{1}\right) σ2(σ2>σ1) ，增大探索点系数 α > 1 \alpha>1 α>1 ，令 a 0 = 0 , b 0 = + ∞ a_{0}=0, b_{0}=+\infty a0=0,b0=+∞ 或 ( λ max ) , k = 0 \left(\lambda_{\max }\right), k=0 (λmax),k=0；
【2】检查下降量要求
计算 f ( t k ) f\left(t_{k}\right) f(tk) ，若 f ( λ k ) ⩽ f ( 0 ) + σ 1 λ k f ′ ( 0 ) f\left(\lambda_{k}\right) \leqslant f(0)+\sigma_{1} \lambda_{k} f^{\prime}(0) f(λk)⩽f(0)+σ1λkf′(0) ，则转【3】，否则令 a k + 1 = a k , b k + 1 = λ k a_{k+1}=a_{k}, b_{k+1}=\lambda_{k} ak+1=ak,bk+1=λk ，转【4】；
【3】检查避免探索点过小的要求
若 f ( t k ) ⩾ f ( 0 ) + σ 2 λ k f ′ ( 0 ) f\left(t_{k}\right) \geqslant f(0)+\sigma_{2} \lambda_{k} f^{\prime}(0) f(tk)⩾f(0)+σ2λkf′(0) ，停止迭代输出 λ k \lambda_{k} λk ；否则令 a k + 1 = λ k , b k + 1 = b k a_{k+1}=\lambda_{k}, b_{k+1}=b_{k} ak+1=λk,bk+1=bk ，若 b k + 1 < + ∞ b_{k+1}<+\infty bk+1<+∞ 转【4】，否则令 λ k + 1 = α λ k , k = k + 1 \lambda_{k+1}=\alpha \lambda_{k}, \quad k=k+1 λk+1=αλk,k=k+1 转【2】；
【4】选取新的试探点
令 λ k + 1 = a k + 1 + b k + 1 2 \lambda_{k+1}=\frac{a_{k+1}+b_{k+1}}{2} λk+1=2ak+1+bk+1 ，置 k = k + 1 k=k+1 k=k+1 转【2】
一般取 σ 1 ∈ ( 0 , 0.5 ] , σ 2 ∈ ( 0.5 , 1 ) , α = 2 \sigma_{1} \in(0,0.5], \quad \sigma_{2} \in(0.5,1), \quad \alpha=2 σ1∈(0,0.5],σ2∈(0.5,1),α=2 。
python实现
def goldsteinsearch(f,df,d,x,lambdamax,rho,t):
'''
线性搜索子函数
数f，导数df，当前迭代点x和当前搜索方向d
'''
flag = 0
a = 0
b = lambdamax
fk = f(x)
gk = df(x)
phi0 = fk
dphi0 = np.dot(gk, d)
lambda0=b*random.uniform(0,1)
while(flag==0):
newfk = f(x + lambda0 * d)
phi = newfk
# print(phi,phi0,rho,alpha ,dphi0)
if (phi - phi0 )<= (rho * lambda0 * dphi0):
if (phi - phi0) >= ((1 - rho) * lambda0 * dphi0):
flag = 1
else:
a = lambda0
b = b
if (b < lambdamax):
lambda0 = (a + b) / 2
else:
lambda0 = t * lambda0
else:
a = a
b = lambda0
lambda0 = (a + b) / 2
return lambda0
参考资料
《精通MATLAB最优化计算（第二版）》
用“人话”解释不精确线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则
《最优化理论与方法》袁亚湘
Cauchy’s method of minimization