数学与统计-线搜索

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

备查手册-梯度法_共轭梯度法_线搜索，本文为第三部分。

2.3 线搜索 line search

代码与例子来源于https://blog.csdn.net/u014791046/article/details/50831017

线搜加入了对步长的计算。

名为Backtracking Line Search(BLS)的梯度下降法以Armijo-Goldstein条件为方法，在以2.2为基础的搜索方向上选取不越过最优点的最大步长：

1. 定义$0<\beta<1$，及$0<\alpha\leq\frac{1}{2}$
2. 从$t=1$开始迭代$t=\beta t$，计算$$f(x_k-t\nabla f(x_k)) > f(x_k)-\alpha_k t|\nabla f(x_k)|_2^2$$

其中Armijo条件为
$$f(x_k+\alpha_kd_k) \leq f(x_k)+\alpha_k\beta\nabla f(x_k)^Td_k, where \beta \in (0,1)$$

# -*- coding: utf-8 -*-

# min 𝑓(𝑥)=(x-3)**2

import matplotlib.pyplot as plt

def f(x):
    '''The function we want to minimize'''
    
    return (x-3)**2
    
def f_grad(x):
    '''gradient of function f'''
    
    return (x-3)*2
 
    
x = 6
y = f(x)
MAX_ITER = 300
curve = [y]
i = 0
step = 0.1
previous_step_size = 1.0
precision = 1e-4

#下面展示的是我之前用的方法，看上去貌似还挺合理的，但是很慢
while previous_step_size > precision  and i < MAX_ITER:
    prev_x = x
    gradient = f_grad(x)
    x = x - gradient * step
    new_y = f(x)
    if new_y > y: #如果出现divergence的迹象，就减小step size
        step *= 0.8
    curve.append(new_y)
    previous_step_size = abs(x - prev_x)
    i += 1
     
print("The local minimum occurs at", x)
print("The number of iterations is", i)

plt.figure()
plt.show() 
plt.plot(curve, 'r*-')

plt.xlabel('iterations')
plt.ylabel('objective function value')
 
#下面展示的是backtracking line search，速度很快
x = 6
y = f(x)
alpha = 0.25
beta = 0.8
curve2 = [y]
i = 0
previous_step_size = 1.0
precision = 1e-4
 
while previous_step_size > precision  and i < MAX_ITER:
    prev_x = x
    gradient = f_grad(x)
    step = 1.0
    while f(x - step * gradient) > f(x) - alpha * step * gradient**2:
        step *= beta
    x = x - step * gradient
    new_y = f(x)
    curve2.append(new_y)
    previous_step_size = abs(x - prev_x)
    i += 1
    
print("The local minimum occurs at", x)
print("The number of iterations is", i)

plt.plot(curve2, 'bo-')
plt.legend(['gradient descent', 'BLS'])
plt.show()

运行结果如图

The local minimum occurs at 3.0003987683987354
The number of iterations is 40
<Figure size 432x288 with 0 Axes>
The local minimum occurs at 3.000008885903001
The number of iterations is 10

3 其他方法

其他方法还有如Riccati与Collocation，以后有时间再单独总结。

都看到这儿了，不如关注每日推送的“科文路”、互动起来~