（最优化理论与方法）第六章无约束优化算法-第一节：线搜索方法

文章目录

• 一：无约束优化问题概述
• 二：线搜索方法
• • （1）概述
  • （2）线搜索准则
  • • A：Armijo准则
    • • ①：概述
      • ②：Armjio准则缺陷
      • ③：回退法
      • ④：代码
    • B：Goldstein准则
    • • ①：概述
      • ②：代码
    • C：Wolfe准则
    • • ①：概述
      • ②：代码
    • D：非单调线搜索准则
  • （3）线搜索方法

一：无约束优化问题概述

考虑如下无约束优化问题

无约束优化问题是众多优化问题中最基本的一类问题，它对自变量的取值范围不加限制，所以无需考虑的可行性

• 对于光滑函数，我们可以较容易地利用梯度和海瑟矩阵的信息来设计算法
• 对于非光滑函数，我们可以利用次梯度来构造迭代格式

无约束优化问题的优化算法主要分为如下两类

• 线搜索类型：根据搜索方向的不同可以分为如下几种，一旦确定了搜索的方向，下一步即沿着该方向寻找下一个迭代点

  • 梯度类算法
  • 次梯度算法
  • 牛顿算法
  • 拟牛顿算法
  • …

• 信赖域类型：主要针对二阶可微的情形，它是在一个给定的区域内使用二阶模型近似原问题，通过不断直接求解该二阶模型从而找到最优值点

二：线搜索方法

（1）概述

线搜索方法：对于本文最开始的优化问题，采用线搜索方法求解最小值点的过程类似于盲人下山：假设一个人处于某个点处，表示此地的高度，为了寻找最低点，在点处需要确定如下两件事情

• 下一步应该向哪一个方向行走？
• 沿着该方向行走多远后停下以便选取下一个下山方向

以上这两个因素确定后，便可以一直重复，直到到达的最小值点

线搜索类算法的数学表述为：给定当前迭代点，首先通过某种算法选取向量，之后确定正数，则下一步迭代点可以写作

• ：是迭代点处的搜索方向。此处要求是一个下降方向，也即，这个下降性质保证了沿着此方向搜索函数值会减小
• ：是相应的步长

所以线搜索类算法的关键是如何选取一个好的方向和合适的步长

不同的线搜索算法对于的选取有着不同的方式，但的选取方法却基本一致。首先构造辅助函数

• ：是给定的下降方向
• ：是该辅助函数的自变量

函数的几何意义非常直观：它是目标函数在射线上的限制。线搜索的目标时选取合适的使得尽可能小，这要求

• 应该使得充分下降
• 不应该在寻找上花费过度的计算量

所以一个自然的想法是寻找使得

这种线搜索方法称之为精确线搜索算法，虽然精确线搜索算法可以在多数情况下找到问题的解，但这通常需要非常大的计算量，所以实际应用中很少使用。所以另一个想法是不要求是的最小值点，而仅仅要求满足某些不等式性质，因此这类方法称之为非精确线搜索算法，所以我们接下来介绍该类算法的结构

（2）线搜索准则

线搜索准则：在非精确线搜索算法中，选取需要满足一定的要求，这些要求被称为线搜索准则。不合适的线搜索准则会导致算法无法收敛

• 例如下面这个例子，由于迭代过程中函数值的下降量不够充分，以至于算法无法收敛至极小值点
  

所以为了避免这种情况发生，必须要引入一些更合理的线搜索准则来确保迭代的收敛性

A：Armijo准则

①：概述

Armijo准则：设是点处的下降方向，若

则称步长满足Armijo准则，其中是一个常数。其几何意义是指点必须在直线

的下方

如下图所示，区间中的点均满足Armijo准则。为下降方向，这说明方向，这说明斜率为负，选取符合条件的确实会使得函数值下降

②：Armjio准则缺陷

Armjio准则缺陷：实际应用中，参数通常选为一个很小的正数（例如），这使得Armijo准则非常容易得到满足，但仅仅使用Armijo准则无法保证迭代的收敛性。这是因为时显然满足条件，而这意味着迭代序列中的点固定不变，研究这样的步长是没有意义的，为此Armjio准则需要配合其他准则共同使用

③：回退法

回退法：在优化算法的实现中，寻找一个满足Armijo准则的步长是比较容易的，一个最常用的算法是回退法。给定初值，回退法通过不断以指数方式缩小试探步长，找到第一个满足Armjio准则的点。具体来说，回退法选取

其中

参数为一个定的实数，回退法基本过程如下所示

④：代码

import numpy as np
from sympy import *

# 计算梯度函数
def cal_grad_funciton(function):
    res = []
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    for i in range(len(x)):
        res.append(diff(function, x[i]))
    return res

# 定义目标函数
def function_define():
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    # y = 2 * (x[0] - x[1] ** 2) ** 2 + (1 + x[1]) ** 2
    # Rosenbrock函数
    y = 100 * (x[1] - x[0] ** 2) ** 2 + (1 - x[0]) ** 2
    
    return y

# 计算函数返回值
def cal_function_ret(function, x):
    res = function.subs([('x1', x[0]), ('x2', x[1])])
    return res

# 计算梯度
def cal_grad_ret(grad_function, x):
    res = []
    
    for i in range(len(x)):
        res.append(grad_function[i].subs([('x1', x[0]), ('x2', x[1])]))
    return res

# armijo准则
"""
Parameter：
    function：函数
    grad_function：梯度函数
    x：初始迭代点
    d：下降方向
    c：armijo准的参数，范围为[0-1]
Return:
    alpha：步长

"""
def armijo(function, grad_function, x, d, c = 0.3):
    # 指定初始步长
    alpha = 1.0
    # 回退参数
    gamma = 0.333
    # 迭代次数
    k = 1.0
    
   # fd 表示 f(x + alpha * d)
    fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
    # fk 表示 f(x) + c * alpha * gradf(x) * d
    fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
    while fd  > fk :
        fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
        fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
        alpha *= gamma
        k += 1.0
    print("迭代次数：", k)
    return alpha


# armijo-goldstein准则
    
if __name__ == '__main__':
    function = function_define()
    grad_function = cal_grad_funciton(function)
    print("函数为：", function)
    print("梯度函数为：", grad_function)

    x0 = [-10, 10]
    d = cal_grad_ret(grad_function, x0)
    d = np.dot(-1, d).tolist()
    alpha = armijo(function, grad_function, x0, d)
    xk = np.add(x0, np.dot(alpha, d))
    f = cal_function_ret(function, xk)
    
    print("初始迭代点：", x0)
    print("搜索方向为：", d)
    print("获取步长为：", alpha)
    print("下降点为：", xk)
    print("下降点函数值为：", f)

B：Goldstein准则

①：概述

Goldstein准则：为了克服Armijo准则的缺陷，我们需要引入其他准则来保证每一步的不会太小。既然Armijo准则只要求点必须在某直线下方，那么我们也可以使用相同的形式使得该点必须处在另一条直线的上方，这便是Armijo-Goldstein准则，简称Goldstein准则。设是点处的下降方向，若

则称步长满足Goldstein准则，其中

同样，Goldstein准则也有非常直观的几何意义，它指的是点必须在以下两条直线之间

②：代码

import numpy as np
from sympy import *

# 计算梯度函数
def cal_grad_funciton(function):
    res = []
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    for i in range(len(x)):
        res.append(diff(function, x[i]))
    return res

# 定义目标函数
def function_define():
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    # y = 2 * (x[0] - x[1] ** 2) ** 2 + (1 + x[1]) ** 2
    # Rosenbrock函数
    y = 100 * (x[1] - x[0] ** 2) ** 2 + (1 - x[0]) ** 2
    
    return y

# 计算函数返回值
def cal_function_ret(function, x):
    res = function.subs([('x1', x[0]), ('x2', x[1])])
    return res

# 计算梯度
def cal_grad_ret(grad_function, x):
    res = []
    
    for i in range(len(x)):
        res.append(grad_function[i].subs([('x1', x[0]), ('x2', x[1])]))
    return res

# armijo-goldstein准则
def armijo_goldstein(function, grad_function, x0, d, c = 0.3):
    # 指定初始步长
    alpha = 1.0
    # 回退参数
    gamma = 0.333
    # 迭代次数
    k = 1.0

    # fd 表示 f(x + alpha * d)
    fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
    # fk 表示 f(x) + c * alpha * gradf(x) * d
    fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
    # fp 表示 f(x) + (1-c) * alpha * gradf(x) * d
    fp = cal_function_ret(function, x0) + (1-c) * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
    while fd > fk or fd < fp:
        alpha *= gamma
        fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
        fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
        fp = cal_function_ret(function, x0) + (1-c) * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
        k += 1.0
    print("迭代次数：", k)
    return alpha
    
if __name__ == '__main__':
    function = function_define()
    grad_function = cal_grad_funciton(function)
    print("函数为：", function)
    print("梯度函数为：", grad_function)

    x0 = [-10, 10]
    d = cal_grad_ret(grad_function, x0)
    d = np.dot(-1, d).tolist()
    alpha = armijo_goldstein(function, grad_function, x0, d)
    xk = np.add(x0, np.dot(alpha, d))
    f = cal_function_ret(function, xk)
    
    print("初始迭代点：", x0)
    print("搜索方向为：", d)
    print("获取步长为：", alpha)
    print("下降点为：", xk)
    print("下降点函数值为：", f)

C：Wolfe准则

①：概述

Wolfe准则：Goldstein准则能够使得函数值充分下降，但是它可能避开了最优函数值

• 如下图所示，一维函数的最小值点并不在满足Goldstein准则的区间中

为此，我们引入Armijo准则-Wolfe准则，简称Wolfe准则。设是点处的下降方向，若

• 
• （Wolfe准则本质要求）

恰好就是的导数，所以Wolfe助阵实则要求在点处的切线斜率不能小于的倍，如下图所示，区间中的点均满足Wolfe准则，在实际应用中参数一般取为0.9

②：代码

import numpy as np
from sympy import *

# 计算梯度函数
def cal_grad_funciton(function):
    res = []
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    for i in range(len(x)):
        res.append(diff(function, x[i]))
    return res

# 定义目标函数
def function_define():
    x = []
    x.append(Symbol('x1'))
    x.append(Symbol('x2'))
    # y = 2 * (x[0] - x[1] ** 2) ** 2 + (1 + x[1]) ** 2
    # Rosenbrock函数
    y = 100 * (x[1] - x[0] ** 2) ** 2 + (1 - x[0]) ** 2
    
    return y

# 计算函数返回值
def cal_function_ret(function, x):
    res = function.subs([('x1', x[0]), ('x2', x[1])])
    return res

# 计算梯度
def cal_grad_ret(grad_function, x):
    res = []
    
    for i in range(len(x)):
        res.append(grad_function[i].subs([('x1', x[0]), ('x2', x[1])]))
    return res


# armijo-wolfe准则
def armijo_wlofe(function, grad_function, x0, d, c = 0.3):
    # wolfe准则参数
    c2 = 0.9
    # 指定初始步长
    alpha = 1.0
    # 二分法确定alpah
    a, b = 0, np.inf
    # 迭代次数
    k = 1.0
    
    # gk表示gradf(x)
    gk = cal_grad_ret(grad_function, x0)
    # fd 表示 f(x + alpha * d)
    fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
    # fk 表示 f(x) + c * alpha * gradf(x) * d
    fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
    # gp表示gradf(x + alpha * d)
    gp = cal_grad_ret(grad_function, np.add(x0, np.dot(alpha, d)))
    while True:
        if fd > fk:
            b = alpha
            alpha = (a + b) / 2
            fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
            fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
            gp = cal_grad_ret(grad_function, np.add(x0, np.dot(alpha, d)))
            k = k + 1
            continue
        if np.dot(gp, d) < c2 * np.dot(gk, d):
            a = alpha
            alpha = np.min(2 * alpha, (a + b) / 2)
            fd = cal_function_ret(function, np.add(x0, np.dot(alpha, d))) 
            fk = cal_function_ret(function, x0) + c * alpha * np.dot(cal_grad_ret(grad_function, x0), d)
            gp = cal_grad_ret(grad_function, np.add(x0, np.dot(alpha, d)))
            k = k + 1
            continue
        break
    print("迭代次数：", k)
    return alpha
            
if __name__ == '__main__':
    function = function_define()
    grad_function = cal_grad_funciton(function)
    print("函数为：", function)
    print("梯度函数为：", grad_function)

    x0 = [-10, 10]
    d = cal_grad_ret(grad_function, x0)
    d = np.dot(-1, d).tolist()
    # alpha = armijo(function, grad_function, x0, d)
    alpha = armijo_wlofe(function, grad_function, x0, d)
    xk = np.add(x0, np.dot(alpha, d))
    f = cal_function_ret(function, xk)
    
    print("初始迭代点：", x0)
    print("搜索方向为：", d)
    print("获取步长为：", alpha)
    print("下降点为：", xk)
    print("下降点函数值为：", f)

D：非单调线搜索准则

以上三种准则都有一个共同点：使用这些准则产生的迭代点序列都是单调的，但在实际应用中，非单调算法有时会有更好的效果，这里主要介绍两种

Grippo准则：设是点处的下降方向，为给定的正整数，以下不等式可以作为一种线搜索准则

其中为给定的常数。该准则和Armijo准非常相似，区别在于Armijo准则要求下一次迭代的函数值相对于本次迭代的函数值有充分的下降，而上述准则只需要下一步函数值相比前面至多步以内迭代的函数值有下降就可以了，显然该准则的要求要比Armijo准则更宽，它也不要求的单调性

Zhang,Hager准则：设是点处的下降方向，为给定的正整数，以下不等式可以作为一种线搜索准则

我们可以用以下的方式理解此准则：

• 变量实际上是本次搜索准则的参照函数值，也即充分下降性质的起始标准
• 而下一步的标准则是函数值和的凸组合，并非仅仅依赖于，而凸组合的两个系数由参数决定。可以看到，当时，此准则就是Armijo准则

（3）线搜索方法