【动手学运动规划】 5.3.c 线搜索方法代码解析

欲说还休，欲说还休。却道天凉好个秋. — 辛弃疾

🏰代码及环境配置：请参考 环境配置和代码运行!

---

本节提供了 线搜索方法的代码测试：

python tests/optimization/line_search_test.py

5.3.c.1 优化问题

在中定义了一个3维空间的二次函数:

$$\min f(x)=x^2+6y^2$$

显然, 这是一个凸函数并且最小点在$(0,0)$.

函数和函数导数如下:

def function(x) -> float:return x[0] ** 2 + 6 * x[1] ** 2def function_gradient(x):return np.array([x[0] * 2, x[1] * 12])

5.3.c.2 Armijo准则代码解析

在armijo(x, d) 函数中, 我们定义了基于Armijo准则的线搜索方法.

输入决策变量x和下降方向d, 在while 循环中, 不停的缩小

def armijo(x, d) -> float:c1 = 1e-3gamma = 0.9alpha = 1.0while function(x + alpha * d) > function(x) + c1 * alpha * np.dot(function_gradient(x).T, d):alpha = gamma * alphareturn alpha

5.3.c.3 Goldstein准则代码解析

在goldstein(x, d)中, 我们使用了二分的方式, 快速找到满足两个不等式要求的点.

def goldstein(x, d):a = 0b = np.infalpha = 1c1 = 0.1  # 可接受系数c2 = 1 - c1beta = 2  # 试探点系数while np.fabs(a - b) > 1e-5:if function(x + alpha * d) <= function(x) + c1 * alpha * np.dot(function_gradient(x).T, d):if function(x + alpha * d) >= function(x) + c2 * alpha * np.dot(function_gradient(x).T, d):breakelse:a = alpha# alpha = (a + b) / 2if b < np.inf:alpha = (a + b) / 2else:alpha = beta * alphaelse:b = alphaalpha = (a + b) / 2return alpha

5.3.c.3 Wolfe准则代码解析

类似的, 在wolfe(x, d)中, 也使用了二分的方式, 快速找到满足两个不等式要求的点.

def wolfe(x, d):c1 = 0.3c2 = 0.9alpha = 1a = 0b = np.infwhile a < b:if function(x + alpha * d) <= function(x) + c1 * alpha * np.dot(function_gradient(x).T, d):if np.dot(function_gradient(x + alpha * d).T, d) >= c2 * alpha * np.dot(function_gradient(x).T, d):breakelse:a = alphaalpha = (a + b) / 2else:b = alphaalpha = (a + b) / 2return alpha

5.3.c.4 不同线搜索方法测试

在line_search_test() 中, 定义了初始点$(-5,8)$, 基于梯度下降法, 使用不同的线搜索方法求最优解.

def line_search_test():x0 = np.array([-5, 8])solution, armijo_x_i = gradient_descent_optimize(copy.deepcopy(x0), armijo)solution, goldstein_x_i = gradient_descent_optimize(copy.deepcopy(x0), goldstein)solution, wolfe_x_i = gradient_descent_optimize(copy.deepcopy(x0), wolfe)

测试结果如下:

• Armijo: Step 67:[-1.77436662e-10 -5.51975406e-06]
• Goldstein: Step 35:[-1.24015340e-05 -3.81469727e-06]
• Wolfe: Step 35:[-1.89816443e-05 -2.27373675e-06]

可以看到Armijo方法迭代次数最多, Wolfe在前几次迭代时, 路径比Goldstein更优.