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

非精确线搜索步长规则

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

设无约束优化问题：
$$\min f(x),x\in R^n$$
参数迭代过程：$x_{k+1}\leftarrow x_k+{\alpha }_k{d}_k$

$$\begin{gathered} {\alpha }_k=\arg \min f\left(x_{k+1}\right)=\arg \underset{{\alpha }_k>0}{\min }f\left(x_k+{\alpha }_k\cdot d_k\right) \\ =\arg \underset{{\alpha }_k>0}{\min }\varphi \left({\alpha }_k\right) \end{gathered}$$

从而我们可以得到关于步长${\alpha }_k$的方程:
$$\varphi ({\alpha }_k)\triangleq f(x_k+{\alpha }_k{d}_k)$$

对$\varphi ({\alpha }_k)$求导：
$${\varphi }^{\prime }({\alpha }_k)=\nabla f(x_k+{\alpha }_k{d}_k{)}^T\cdot d_k$$

当步长${\alpha }_k=0$时，$$\varphi (0)=f(x_k)$$ $${\varphi }^{\prime }\left(0\right)=\nabla f^{\mathrm{T}}\left(x_k\right)\cdot d_k<0$$

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

我们绘制一个假设的$\varphi ({\alpha }_k)$的函数曲线：

$\varphi ({\alpha }_k)$在0处的切线方程：
$$L({\alpha }_k)=f\left(x_k\right)+\nabla f^{\mathrm{T}}\left(x_k\right)d_k\cdot {\alpha }_k$$

Armijo规则

Armijo规则是最简单的线搜索规则之一，它基于函数值的下降来决定步长。
具体而言，Armijo规则要求如下图所示：

绿色划线范围为${\alpha }_k$可取值的范围。

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

$$\varphi ({\alpha }_k)=f(x_k+{\alpha }_k\cdot d_k)\le f(x_k)+c\cdot {\alpha }_k\cdot \nabla f(x_k{)}^T{d}_k$$

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

Goldstein规则

由于Armijo规则，引入${\alpha }_k$的取值范围包含了0附近的值，为了保证迭代步长不会太小，
Goldstein规则是对Armijo规则的一种改进，它引入了一个额外的上界条件。Goldstein规则要求：

$$f(x_k+{\alpha }_k\cdot d_k)\le f(x_k)+c_1\cdot {\alpha }_k\cdot \nabla f(x_k{)}^T{d}_k$$

并且，

$$f(x_k+{\alpha }_k\cdot d_k)\ge (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条件和曲率条件，它对步长进行更为严格的控制。$\varphi ({\alpha }_k)$的斜率由负值最大逐步增加，因此新增一个斜率的约束，去掉小步长。

Wolfe规则要求两个条件：

1. Armijo条件：
   $$\varphi ({\alpha }_k)=f(x_k+{\alpha }_k\cdot d_k)\le f(x_k)+c_1\cdot {\alpha }_k\cdot \nabla f(x_k{)}^T{d}_k$$

2. 曲率条件：
   $${\varphi }^{\prime }({\alpha }_k)=\nabla f(x_k+{\alpha }_k\cdot d_k{)}^T{d}_k\ge 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`                                                                                                                         

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

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

参考链接

https://www.bilibili.com/video/BV1H14y1R7Yo/?spm_id_from=333.337.search-card.all.click