资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

非精线搜索步长规则Armijo规则&Goldstein规则&Wolfe规则

创作时间:

作者:

@小白创作中心

非精线搜索步长规则Armijo规则&Goldstein规则&Wolfe规则

引用

CSDN

https://blog.csdn.net/weixin_41469272/article/details/136011925

在优化算法中，线搜索是一种寻找合适步长的策略，以确保在目标函数上获得足够的下降。本文将详细介绍Armijo规则、Goldstein规则和Wolfe规则等非精确线搜索步长规则，帮助读者更好地理解这些规则的数学原理和应用场景。

线搜索介绍

一维线搜索（1D Line Search）

一维线搜索是在优化问题中，沿某一特定方向找到目标函数的最优值（最小值或最大值）。

给定一个当前点$x_k$和搜索方向$p_k$，线搜索的核心是确定一个标量步长$\alpha$，使得：

$$
\alpha^* = \arg\min_{\alpha} f(\mathbf{x}_k + \alpha \mathbf{p}_k)
$$

其中，$f(x)$是待优化的目标函数。

搜索方向$p_k$是固定的，一维线搜索仅优化沿着$p_k$的步长$\alpha$。
常见的搜索方向包括负梯度方向（如梯度下降法）或共轭方向（如共轭梯度法）。

方法

精确线搜索：尝试精确找到最优步长$\alpha^*$（计算量大）。
不精确线搜索：采用近似方法，如：
Armijo条件：保证下降的同时控制步长大小。
Wolfe条件：控制下降速率和曲率。

二维线搜索（2D Line Search）

二维线搜索是扩展的一维线搜索，在两个方向上同时进行优化。对于某点$x_k$，选择两个独立方向$p_k^1$和$p_k^2$，优化步长$\alpha_1$和$\alpha_2$使得：

$$
(\alpha_1^, \alpha_2^) = \arg\min_{\alpha_1, \alpha_2} f(\mathbf{x}_k + \alpha_1 \mathbf{p}_k^1 + \alpha_2 \mathbf{p}_k^2)
$$

优化变量为两个步长$(\alpha_1, \alpha_2)$，对应一个二维搜索平面。
增加了计算复杂度，但可以加速收敛，尤其在目标函数的形状在多个方向上变化较大时更有效。

特性对比

特性	一维线搜索	二维线搜索
搜索空间	沿单一方向的标量步长($\alpha$)	沿两个方向的标量步长($\alpha_1, \alpha_2$)
计算复杂度	较低，计算简单	较高，需要同时优化两个变量
适用场景	梯度下降法、共轭梯度法等	复杂目标函数或更高效的优化
效果	单步改进较慢，迭代多次收敛	单步改进更大，可能减少迭代次数
方法扩展	常见的Armijo或Wolfe条件	可扩展为高维搜索（如信赖域方法）

一维线搜索是优化中的基本工具，简单高效，适用于大多数优化算法。但当目标函数在多个方向上梯度差异较大时，二维线搜索（或多维线搜索）可以更好地适应优化需求。二者本质相同，只是扩展了优化维度，在计算效率和效果上需要权衡。

非精确线搜索步长规则

在数值优化中，线搜索是一种寻找合适步长的策略，以确保在目标函数上获得足够的下降。如最速下降法，拟牛顿法这些常用的优化算法等，其中的线搜索步骤通常使用Armijo规则、Goldstein规则或Wolfe规则等。

设无约束优化问题：

$$
\min f(x), , x \in \mathbb{R}^n
$$

参数迭代过程：

$$
x_{k+1} \leftarrow x_k + \alpha_k d_k
$$

$$
\alpha_k = \arg\min f(x_{k+1}) = \arg\min_{\alpha_k > 0} f(x_k + \alpha_k \cdot d_k) = \arg\min_{\alpha_k > 0} \phi(\alpha_k)
$$

从而我们可以得到关于步长$\alpha_k$的方程：

$$
\phi(\alpha_k) \triangleq f(x_k + \alpha_k d_k)
$$

对$\phi(\alpha_k)$求导：

$$
\phi'(\alpha_k) = \nabla f(x_k + \alpha_k d_k)^T \cdot d_k
$$

当步长$\alpha_k = 0$时：

$$
\phi(0) = f(x_k)
$$

$$
\phi'(0) = \nabla f^T(x_k) \cdot d_k < 0
$$

Tips: 当$\nabla f(x_k) \cdot d_k < 0$时，即下降方向与负梯度方向的夹角为锐角时，下降有效

我们绘制一个假设的$\phi(\alpha_k)$的函数曲线：

$\phi(\alpha_k)$在0处的切线方程：

$$
L(\alpha_k) = f(x_k) + \nabla f^T(x_k) d_k \cdot \alpha_k
$$

Armijo规则

Armijo规则是最简单的线搜索规则之一，它基于函数值的下降来决定步长。

具体而言，Armijo规则要求如下图所示：

绿色划线范围为$\alpha_k$可取值的范围。

设置连接0点$\phi(0) = f(x_k)$和射线$L(\alpha_k) = f(x_k) + \nabla f^T(x_k) d_k \cdot \alpha_k$之间作一条过$(0, f(x_k))$斜率为$c \cdot \nabla f(x_k)^T d_k$的射线。所有满足以下方程的$\alpha_k$便可作为步长。即图中绿线划出的取值范围。

$$
\phi(\alpha_k) = f(x_k + \alpha_k \cdot d_k) \leq f(x_k) + c \cdot \alpha_k \cdot \nabla f(x_k)^T d_k
$$

其中，$\alpha_k$是步长，$c$是Armijo规则的参数，通常取小于1的值。Armijo规则保证在朝着梯度方向（即搜索方向$d_k$）移动时，目标函数能够有足够的下降。

Tips：

Armijo规则的实际搜索伪代码：

设置系数$\rho = 0.9$，控制步幅系数，0.9为示例，保证步长够大。

设置系数$0 < c < 1$为Armijo规则系数

设置$\alpha = 1$为步长

/当步长过大，使得$f(x_{k+1})$过大，则缩小步长/

while($f(x_k + \alpha_k \cdot d_k) > f(x_k) + c \cdot \alpha_k \cdot \nabla f(x_k)^T d_k$)

{

alpha *= rho

}

Goldstein规则

由于Armijo规则，引入$\alpha_k$的取值范围包含了0附近的值，为了保证迭代步长不会太小，

Goldstein规则是对Armijo规则的一种改进，它引入了一个额外的上界条件。Goldstein规则要求：

$$
f(x_k + \alpha_k \cdot d_k) \leq f(x_k) + c_1 \cdot \alpha_k \cdot \nabla f(x_k)^T d_k
$$

并且，

$$
f(x_k + \alpha_k \cdot d_k) \geq (1 - c_1) \cdot \alpha_k \cdot \nabla f(x_k)^T d_k
$$

其中，$c_1$是Goldstein规则的参数，通常取小于0.5的值。Goldstein规则的引入使得步长既要满足下降条件，又要限制在一个合理的范围内。

其示意图如下：

蓝色划线范围为$\alpha_k$可取值的范围。

Wolfe规则

Wolfe规则结合了Armijo条件和曲率条件，它对步长进行更为严格的控制。$\phi(\alpha_k)$的斜率由负值最大逐步增加，因此新增一个斜率的约束，去掉小步长。

Wolfe规则要求两个条件：

Armijo条件：

$$
\phi(\alpha_k) = f(x_k + \alpha_k \cdot d_k) \leq f(x_k) + c_1 \cdot \alpha_k \cdot \nabla f(x_k)^T d_k
$$

曲率条件：

$$
\phi'(\alpha_k) = \nabla f(x_k + \alpha_k \cdot d_k)^T d_k \geq c_2 \cdot \nabla f(x_k)^T d_k
$$

其中，$c_1$和$c_2$是Wolfe规则的参数，通常$0 < c_1 < c_2 < 1$。Wolfe规则旨在确保步长既满足足够的下降条件，又满足足够的曲率条件，以保证收敛性和数值稳定性。

蓝色划线范围为$\alpha_k$可取值的范围。

C++示例代码

以上规则在实际应用中通常作为拟牛顿法的一部分。以下是一个简单的C++示例程序，演示了Armijo、Goldstein和Wolfe规则的使用。

#include <iostream>
#include <cmath>
#include <Eigen/Dense>
#include <limits>
using namespace Eigen;
double objectiveFunction(const VectorXd& x) {
    return x[0]*x[0] + 2*x[1]*x[1];
}
VectorXd gradient(const VectorXd& x) {
    VectorXd grad(2);
    grad[0] = 2*x[0];
    grad[1] = 4*x[1];
    return grad;
}
bool armijoRule(const VectorXd& x, const VectorXd& d, double alpha, double beta) {
    double c = 0.5; // Armijo参数
    double expectedReduction = c * alpha * gradient(x).dot(d);
    double actualReduction = objectiveFunction(x - alpha * d) - objectiveFunction(x);
    return actualReduction >= expectedReduction;
}
void armijoExample() {
    VectorXd x(2);
    x << 1.0, 1.0;  // Initial guess
    VectorXd d = -gradient(x); // Descent direction
    double alpha = 1.0; // Initial step size
    double beta = 0.5;  // Step size reduction factor
    while (!armijoRule(x, d, alpha, beta)) {
        alpha *= beta;
    }
    std::cout << "Armijo rule: Optimal step size = " << alpha << std::endl;
}
bool goldsteinRule(const VectorXd& x, const VectorXd& d, double alpha, double beta, double gamma) {
    double c1 = 0.5; // Goldstein参数
    double expectedReduction = c1 * alpha * gradient(x).dot(d);
    double actualReduction = objectiveFunction(x - alpha * d) - objectiveFunction(x);
    double upperBound = (1 - c1) * alpha * gradient(x).dot(d);
    return actualReduction >= expectedReduction && actualReduction <= upperBound;
}
void goldsteinExample() {
    VectorXd x(2);
    x << 1.0, 1.0;  // Initial guess
    VectorXd d = -gradient(x); // Descent direction
    double alpha = 1.0; // Initial step size
    double beta = 0.5;  // Step size reduction factor
    double gamma = 2.0; // Additional parameter for Goldstein rule
    while (!goldsteinRule(x, d, alpha, beta, gamma)) {
        alpha *= beta;
    }
    std::cout << "Goldstein rule: Optimal step size = " << alpha << std::endl;
}
bool wolfeRule(const VectorXd& x, const VectorXd& d, double alpha, double c1, double c2) {
    double phi0 = objectiveFunction(x);
    double phi_alpha = objectiveFunction(x + alpha * d);
    double phi_prime_0 = gradient(x).dot(d);
    double phi_prime_alpha = gradient(x + alpha * d).dot(d);
    // Armijo条件
    if (phi_alpha > phi0 + c1 * alpha * phi_prime_0)
        return false;
    // 曲率条件
    if (phi_prime_alpha < c2 * phi_prime_0)
        return false;
    return true;
}
void wolfeExample() {
    VectorXd x(2);
    x << 1.0, 1.0;  // Initial guess
    VectorXd d = -gradient(x); // Descent direction
    double alpha = 1.0; // Initial step size
    double c1 = 1e-4;   // Armijo条件参数
    double c2 = 0.9;    // 曲率条件参数
    while (!wolfeRule(x, d, alpha, c1, c2)) {
        alpha *= 0.5; // Reduce step size
    }
    std::cout << "Wolfe rule: Optimal step size = " << alpha << std::endl;
}
int main()
{
   armijoExample();
   goldsteinExample();
   wolfeExample();
}
//g++ xiansousuo.cpp `pkg-config eigen3 --libs --cflags`

以上代码通过迭代求得最佳的步长。

在实际应用中，选择适当的线搜索规则和参数非常重要。这些规则的性能可能因问题的性质而异，因此需要根据具体情况进行调整。线搜索规则的选择直接影响了优化算法的性能和收敛速度，因此在应用中需要进行仔细的实验和调优。