python - 梯度下降的 self 实现与 SciPy Minimize 的比较

Question

这是我正在接受的凸优化类的作业。任务如下:

Implement the gradient descent algorithm with backtracking line search to find the optimal step size. Your implementation will be compared to Python's scipy.optimize.minimize function.

The specific function to minimize is the least squares function. The error between the solution found by the Python library and your implementation must be smaller than 0.001.

我已经实现了，但错误值徘徊在 1 左右，并且一直在寻找改进它的方法，但遇到了一些麻烦。这是我编写的代码:

梯度下降+回溯线搜索实现

import numpy as np

# Gradient descent.
def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8

    delta_x = -grad(x0, *args)
    t = backtracking_line_search(fun, x0, grad, delta_x, alpha, beta, args)
    x_new = x0 + (t * delta_x)

    if np.linalg.norm(x_new) ** 2 > np.linalg.norm(x0) ** 2:
        return min_gd(fun, x_new, grad, args)
    else:
        return x_new
    
# Line search function returns optimal step size.
def backtracking_line_search(fun, x, grad, delta_x, alpha, beta, args=()):
    t = 1
    derprod = grad(x, *args) @ delta_x

    while fun((x + (t * delta_x)), *args) > fun(x, *args) + (alpha * t * derprod):
        t *= beta

    return t

其他给定函数

import numpy as np
from scipy.optimize import minimize
import gd

# Least Squares function
def LeastSquares(x, A, b):
    return np.linalg.norm(A @ x - b) ** 2

# gradient  
def grad_LeastSquares(x, A, b):
    return 2 * ((A.T @ A) @ x - A.T @ b)

两个结果之间的误差基本上是使用L2范数计算的。

我提出的一些想法是我的梯度下降函数中的容差检查点可能有缺陷。现在我本质上只是检查下一步是否比上一步更大。然而，我也无法思考如何改进这一点。

欢迎任何反馈。

编辑

如果有人对我编写的最终代码感到好奇，使其以所需的方式工作:

def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8

    delta_x = -grad(x0, *args)
    t = backtracking_line_search(fun, x0, grad, delta_x, alpha, beta, args)
    x_new = x0 + (t * delta_x)
    
    if np.linalg.norm(grad(x_new, *args)) < 0.01:
        return x_new
    else:
        return min_gd(fun, x_new, grad, args)

我只是修复了条件语句，这样我不仅可以比较规范，还可以检查该值是否小于预定的容差水平。

希望这对将来的任何人都有帮助。

Answer 1

您对容差检查的猜测是正确的:当前向量的范数与收敛无关。典型的标准是小梯度，因此 min_gd 应该看起来像

def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8
    eps = 0.001

    x_new = x0
    delta_x = -grad(x0, *args)
    while np.linalg.norm(delta_x) > eps:
        t = backtracking_line_search(fun, x_new, grad, delta_x, alpha, beta, args)
        x_new = x_new + (t * delta_x)
        delta_x = -grad(x_new, *args)

    return x_new

其中 eps 是一些小的正容差。