解释scipy中line_search函数的amax参数

Question

在SciPy 1.0.0中，根据其文档，scipy.optimize.line_search有一个可选参数amax，它确定了“最大步长”。因此，我期望第一个返回值alpha始终小于给定的amax，但实际情况并非如此，如下面的示例所示：

from scipy.optimize import line_search

def f(x):
    return x[0]**2 + x[1]**2

def df(x):
    return 2*x

x = np.array([4, 5])
line_search(f, df, x, -df(x), amax=0.001)
# Returns (0.5, 3, 1, 0.0, 41.0, array([ 0.,  0.]))

在这里，alpha的值为0.5，但amax的值为0.001，小于0.5。

另一种解释可能是amax限制了输出值x_new和x0之间的距离，但事实并非如此。

我是否误解了文档，或者这是SciPy中的一个错误？如果按照预期工作，amax的正确解释是什么？有没有其他方法来限制执行线搜索的alpha范围？

- fuglede

---

哦，线性搜索模块。碰过一次就失败了。似乎alpha值增加（从1开始），因此第一个pick = 1就为您使用了。您需要基于Wolfe条件的线性搜索吗？如果不需要，我会尝试从1向0工作的Armijo-ls。但当然还有其他方法。如果您必须坚持使用这个，您可能会在Github的问题跟踪器中找到一些讨论，当然还有Nocedal的《数值优化》中的伪代码。 - sascha

Armijo确实执行了(我试过了)，但仍然没有回答你的问题。 - sascha

阅读代码时，感觉像是一个错误。如果初始猜测成功，amax就永远不会被触及。与Nocedal的差异也令人困惑：在那里，amax是初始化阶段的一部分。 - sascha

Answer 1

正如Sascha所说，当前的实现line_search（SciPy 1.0.0）没有正确处理amax。具体来说，函数scalar_search_wolfe2如果找到合适的alpha值，则会跳出循环for i in xrange(maxiter)，而对于amax的检查则在循环后面，并且不会被执行。

解决方法：

1. 使用较旧的例程line_search_wolfe1，它是MINPACK线搜索的包装器。它不仅强制执行amax，还强制执行最小步长amin。

from scipy.optimize.linesearch import line_search_wolfe1
line_search_wolfe1(f, df, x, -df(x), amax=0.001)

这里返回的结果是 (None, 1, 0, 41.0, 41.0, array([ 8, 10]))，其中 None 表示没有找到合适的步长。正确的答案应该是：没有满足 Wolfe 条件的步长大小小于等于 0.001。

2. 将步长要求作为extra_condition参数传递给line_search例程。

line_search(f, df, x, -df(x), extra_condition=lambda a, x, f, g: a <= 0.001)

这将返回(None, 13, 1, None, 41.0, None)，这是正确的：没有合适的步长。

3. 也许你并不是真的想强制使用Wolfe条件？毕竟得到None作为（正确的）答案并不是很有帮助。如果是这样，请使用Armijo回溯法。参数不同：它不需要df函数，但需要搜索初始点处的梯度和值。参数alpha0是初始和最大步长，算法只会在必要时减小它。

from scipy.optimize.linesearch import line_search_armijo
line_search_armijo(f, x, -df(x), df(x), f(x), alpha0=0.001)

返回结果：

返回值为(0.001, 1, 40.836164000000004)，意味着步长为0.001，经过1次函数评估后，函数值在步长之后变为40.8...，当然比最初的41小。

我没有在SciPy网站上看到line_search_armijo的文档，但我们可以在Github上阅读它的docstring。

- user6655984

---

尝试了一下，line_search_armijo确实表现更好，但它仍然有些意外。例如，使用一个（可以说是损坏的）输入方向，$\phi'(0) > 0$，它可能返回负值的alpha（这是你不会期望的，因为在scalar_search_armijo中amin=0）。 - fuglede

是的，源代码中假设alpha>0是下降方向，这意味着假设derphi0是负数。这种假设是关于alpha和amin的不等式基础。我不知道为什么线搜索在derphi0>0的情况下没有简单地出错。但是你可以自己添加保障：在调用line_search_armijo(f, xk, pk, gfk, old_fval)之前，请确保np.dot(gfk, pk)是负数。 - user6655984

我的猜测是，在一些依赖于线搜索的多变量优化例程中，如果表现不如预期，则会调整线搜索，使其更有可能继续执行，而不是引发错误并终止过程。 - user6655984

Answer 2

这个错误会在 SciPy 1.3.0 中通过 这个拉取请求 得到修复，该请求将更改行为以符合预期：结果步长为 None。

- fuglede