使用 Python 进行线性搜索优化

今天药忘吃喽~ 2022-10-17 00:49 339阅读 0赞

【翻译自 ：[ Line Search Optimization With Python][Line Search Optimization With Python]】

【说明：*Jason Brownlee* PhD大神的文章个人很喜欢，所以闲暇时间里会做一点翻译和学习实践的工作，这里是相应工作的实践记录，希望能帮到有需要的人！】

线性搜索是一种优化算法，可用于具有一个或多个变量的目标函数。它提供了一种使用单变量优化算法的方法，例如对多元目标函数的二分搜索，通过使用搜索来定位从已知点到最优值的每个维度中的最佳步长。

在本教程中，您将了解如何在 Python 中执行线性搜索优化。完成本教程后，您将了解：

线性搜索是一种用于单变量和多变量优化问题的优化算法。
    SciPy 库提供了一个用于执行线性搜索的 API，它要求您知道如何计算目标函数的一阶导数。
    如何对目标函数执行线性搜索并使用结果。

# 教程概述 #

本教程分为三个部分；他们是：

什么是线性搜索
    Python 中的线性搜索
    如何执行线性搜索
        定义目标函数
        执行线性搜索
        处理线性搜索失败案例

## 什么是线性搜索 ##

线性搜索是一种用于单变量或多变量优化的优化算法。该算法需要搜索空间中的初始位置和搜索方向。然后它会从初始位置选择搜索空间中的下一个位置，这会导致更好或最好的目标函数评估。

方向是指示沿线的符号（正或负）和搜索的最大范围的大小。因此，方向最好被认为是候选搜索区域，并且必须足够大以包含最优值，或者比起点更好的点。

线性搜索将自动选择称为 alpha 的比例因子，用于从当前位置最小化目标函数的步长（方向）。这涉及使用另一种单变量优化算法在所选方向上找到最佳点，以便选择合适的 alpha。

Alpha 是方向的比例因子，因此在搜索中只考虑 0.0 到 1.0 范围内的值。线搜索的一步解决了一个最小化问题，该问题最小化当前位置加上缩放方向的目标函数：最小化目标（位置 + alpha \* 方向）因此，线搜索一次在一维中运行，并返回在选定方向上移动的距离。可以重复调用线搜索以将搜索空间导航到解决方案，如果所选方向不包含具有较低目标函数值的点，例如，线搜索可能会失败。如果算法被定向到上坡搜索。该解是近似的或不精确的，并且可能不是全局解，这取决于搜索空间的形状。该算法适用的条件称为沃尔夫条件。现在我们已经熟悉了线性搜索，让我们探讨如何在Python中执行搜索。

## python 中的线性搜索 ##

我们可以使用 line\_search() 函数在 Python 中手动执行线性搜索。它支持单变量优化以及多变量优化问题。该函数采用目标函数的名称和目标函数的梯度名称，以及搜索空间中的当前位置和移动方向。因此，您必须知道目标函数的一阶导数。 您还必须了解从何处开始搜索以及执行搜索的范围。 回想一下，您可以使用不同的方向（符号和幅度）多次执行搜索。

result = line_search(objective, gradient, point, direction)

该函数返回一个包含六个元素的元组，其中包括称为 alpha 的方向的比例因子和执行的函数评估次数，以及其他值。

结果元组中的第一个元素包含 alpha。 如果搜索未能收敛，则 alpha 的值为 None。

# retrieve the alpha value found as part of the line search
    alpha = result[0]

alpha，起点和方向可用于构造单行搜索的终点。

# construct the end point of a line search
    end = point + alpha * direction

对于具有多个输入变量的优化问题，例如多元优化，line\_search() 函数将返回所有维度的单个 alpha 值。这意味着该函数假设最优值在所有维度上与起点等距，这是一个重大限制。现在我们已经熟悉了如何在 Python 中执行搜索，让我们探索一个有效的例子。

## 如何执线性搜索 ##

我们可以演示如何使用带有简单单变量目标函数及其导数的线搜索。本节分为多个部分，包括定义测试函数、执行线搜索以及处理未找到最优值的失败情况。

### 定义目标函数 ###

首先，我们可以定义目标函数。在这种情况下，我们将使用一维目标函数，特别是x ^ 2偏离零的量很小。这是一个凸函数，选择它是因为它易于理解和计算一阶导数。

目标(x) = (-5 + x)^2  
请注意，线搜索不限于一维函数或凸函数。

下面列出了该函数的实现。

# objective function
    def objective(x):
    	return (-5.0 + x)**2.0

该函数的一阶导数可以解析计算，如下所示：

梯度（x）= 2 \*（-5 + x）  
每个输入值的梯度仅表示每个点向最优值的斜率。 下面列出了该函数的实现。

# gradient for the objective function
    def gradient(x):
    	return 2.0 * (-5.0 + x)

我们可以为 x 定义一个从 -10 到 20 的输入范围，并计算每个输入的目标值。

# define range
    r_min, r_max = -10.0, 20.0
    # prepare inputs
    inputs = arange(r_min, r_max, 0.1)
    # compute targets
    targets = [objective(x) for x in inputs]

然后我们可以绘制输入值与目标值的关系图，以了解函数的形状。

# plot inputs vs objective
    pyplot.plot(inputs, targets, '-', label='objective')
    pyplot.legend()
    pyplot.show()

将这些结合在一起，下面列出了完整的示例。

# plot a convex objective function
    from numpy import arange
    from matplotlib import pyplot
    
    # objective function
    def objective(x):
    	return (-5.0 + x)**2.0
    
    # gradient for the objective function
    def gradient(x):
    	return 2.0 * (-5.0 + x)
    
    # define range
    r_min, r_max = -10.0, 20.0
    # prepare inputs
    inputs = arange(r_min, r_max, 0.1)
    # compute targets
    targets = [objective(x) for x in inputs]
    # plot inputs vs objective
    pyplot.plot(inputs, targets, '-', label='objective')
    pyplot.legend()
    pyplot.show()

运行该示例计算 -10 到 20 范围内的输入值 (x)，并创建一个显示熟悉的抛物线 U 形的图。

该函数的最优值似乎是 x=5.0，目标值为 0.0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70][]

### 执行线性搜索 ###

接下来，我们可以对函数执行线搜索。首先，我们必须定义搜索的起点和搜索方向。在这种情况下，我们将使用 x=-5 的起点，距离最优值大约 10 个单位。 我们将向右迈出一大步，例如 正方向，在本例中为 100 个单位，这将大大超出最优值。回想一下方向就像步长一样，搜索将缩放步长以找到最优值。

# define the starting point
    point = -5.0
    # define the direction to move
    direction = 100.0
    # print the initial conditions
    print('start=%.1f, direction=%.1f' % (point, direction))
    # perform the line search
    result = line_search(objective, gradient, point, direction)

然后搜索将寻找最优值并返回 alpha 或距离以修改方向。我们可以从结果中检索 alpha，以及执行的函数评估的数量。

# summarize the result
    alpha = result[0]
    print('Alpha: %.3f' % alpha)
    print('Function evaluations: %d' % result[1])

我们可以使用 alpha、我们的起点和步长来计算最优值的位置并计算该点的目标函数（我们期望它等于 0.0）。

# define objective function minima 
    end = point + alpha * direction
    # evaluate objective function minima
    print('f(end) = %.3f' % objective(end))

然后，为了好玩，我们可以再次绘制函数并将起点显示为绿色方块，将终点显示为红色方块。

# define range
    r_min, r_max = -10.0, 20.0
    # prepare inputs
    inputs = arange(r_min, r_max, 0.1)
    # compute targets
    targets = [objective(x) for x in inputs]
    # plot inputs vs objective
    pyplot.plot(inputs, targets, '--', label='objective')
    # plot start and end of the search
    pyplot.plot([point], [objective(point)], 's', color='g')
    pyplot.plot([end], [objective(end)], 's', color='r')
    pyplot.legend()
    pyplot.show()

将这些结合在一起，下面列出了对凸目标函数执行线搜索的完整示例。

# perform a line search on a convex objective function
    from numpy import arange
    from scipy.optimize import line_search
    from matplotlib import pyplot
    
    # objective function
    def objective(x):
    	return (-5.0 + x)**2.0
    
    # gradient for the objective function
    def gradient(x):
    	return 2.0 * (-5.0 + x)
    
    # define the starting point
    point = -5.0
    # define the direction to move
    direction = 100.0
    # print the initial conditions
    print('start=%.1f, direction=%.1f' % (point, direction))
    # perform the line search
    result = line_search(objective, gradient, point, direction)
    # summarize the result
    alpha = result[0]
    print('Alpha: %.3f' % alpha)
    print('Function evaluations: %d' % result[1])
    # define objective function minima
    end = point + alpha * direction
    # evaluate objective function minima
    print('f(end) = f(%.3f) = %.3f' % (end, objective(end)))
    # define range
    r_min, r_max = -10.0, 20.0
    # prepare inputs
    inputs = arange(r_min, r_max, 0.1)
    # compute targets
    targets = [objective(x) for x in inputs]
    # plot inputs vs objective
    pyplot.plot(inputs, targets, '--', label='objective')
    # plot start and end of the search
    pyplot.plot([point], [objective(point)], 's', color='g')
    pyplot.plot([end], [objective(end)], 's', color='r')
    pyplot.legend()
    pyplot.show()

运行示例首先报告起点和方向。

执行搜索并找到一个 alpha，它修改方向以定位最优值，在本例中为 0.1，它是在三个函数评估后找到的。

最优值点位于 5.0，正如预期的那样，计算结果为 0.0。

start=-5.0, direction=100.0
    Alpha: 0.100
    Function evaluations: 3
    f(end) = f(5.000) = 0.000

最后，创建一个函数图，显示起点（绿色）和目标（红色）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70 1][]

### 处理线性搜索失败案例 ###

搜索不能保证找到函数的最优值。如果指定的方向不足以包含最优值，则可能会发生这种情况。例如，如果我们使用方向为 3，那么搜索将无法找到最优值。 我们可以用下面列出的完整示例来演示这一点。

# perform a line search on a convex objective function with a direction that is too small
    from numpy import arange
    from scipy.optimize import line_search
    from matplotlib import pyplot
    
    # objective function
    def objective(x):
    	return (-5.0 + x)**2.0
    
    # gradient for the objective function
    def gradient(x):
    	return 2.0 * (-5.0 + x)
    
    # define the starting point
    point = -5.0
    # define the direction to move
    direction = 3.0
    # print the initial conditions
    print('start=%.1f, direction=%.1f' % (point, direction))
    # perform the line search
    result = line_search(objective, gradient, point, direction)
    # summarize the result
    alpha = result[0]
    print('Alpha: %.3f' % alpha)
    # define objective function minima
    end = point + alpha * direction
    # evaluate objective function minima
    print('f(end) = f(%.3f) = %.3f' % (end, objective(end)))

运行该示例，搜索达到 1.0 的 alpha 限制，这给出了 -2 评估为 49 的终点。离 f(5) = 0.0 的最优值还有很长的路要走。

start=-5.0, direction=3.0
    Alpha: 1.000
    f(end) = f(-2.000) = 49.000

此外，我们可以选择错误的方向，这只会导致比起点更差的评估。在这种情况下，错误的方向将远离最优值，例如 从起点全部上坡。

# define the starting point
    point = -5.0
    # define the direction to move
    direction = -3.0

期望搜索不会收敛，因为它无法找到比起点更好的任何点。下面列出了无法收敛的搜索的完整示例。

# perform a line search on a convex objective function that does not converge
    from numpy import arange
    from scipy.optimize import line_search
    from matplotlib import pyplot
    
    # objective function
    def objective(x):
    	return (-5.0 + x)**2.0
    
    # gradient for the objective function
    def gradient(x):
    	return 2.0 * (-5.0 + x)
    
    # define the starting point
    point = -5.0
    # define the direction to move
    direction = -3.0
    # print the initial conditions
    print('start=%.1f, direction=%.1f' % (point, direction))
    # perform the line search
    result = line_search(objective, gradient, point, direction)
    # summarize the result
    print('Alpha: %s' % result[0])

运行示例会产生 LineSearchWarning，表明搜索无法按预期收敛。

搜索返回的 alpha 值为 None。

start=-5.0, direction=-3.0
    LineSearchWarning: The line search algorithm did not converge
    warn('The line search algorithm did not converge', LineSearchWarning)
    Alpha: None

[Line Search Optimization With Python]: https://machinelearningmastery.com/line-search-optimization-with-python/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70]: /images/20221014/041ef9a47c36420588b55c82d08a087f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvZ2V0aGVyX0Na_size_16_color_FFFFFF_t_70 1]: /images/20221014/f323e9e82c7a42fe855f489bd222c605.png