梯度下降的自我实现与SciPy最小化相比

Question

这是我正在进行的凸优化 class 的作业。赋值如下：

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 是一些小的正公差。

梯度下降的自我实现与SciPy最小化相比

Self-Implementation of Gradient Descent Compared to SciPy Minimize

python

mathematical-optimization