一、概述
这个Python程序实现了经典的梯度下降算法和随机梯度下降算法，并在两个不同的优化问题上进行了比较实验：Rosenbrock函数和强凸二次函数。
二、功能模块
1、测试函数定义
Rosenbrock函数
- 函数:
rosenbrock(w) - 描述: 经典的非凸优化测试函数，也称为”香蕉函数”
- 数学表达式: f(x,y) = (1-x)² + 100(y-x²)²
- 最优解: (1, 1)
- 特点: 具有狭长的弯曲谷地，是测试优化算法性能的经典函数
强凸二次函数
- 函数:
quadratic(w, a=10) - 描述: 强凸二次函数，具有良好的优化性质
- 数学表达式: f(x,y) = 0.5(ax² + y²)
- 最优解: (0, 0)
- 参数: a > 0，控制x方向的曲率
2、梯度计算
grad_rosenbrock(w): Rosenbrock函数的梯度grad_quadratic(w, a=10): 二次函数的梯度
3、优化算法
标准梯度下降 (Gradient Descent)
函数: gradient_descent(f, grad_f, w0, max_iter=1000, tol=1e-6, alpha=1e-3, use_line_search=False, **kwargs)
参数说明:
f: 目标函数grad_f: 梯度函数w0: 初始点max_iter: 最大迭代次数tol: 收敛容差alpha: 学习率（固定步长）use_line_search: 是否使用自适应步长
特点:
- 确定性算法，每次使用精确梯度
- 支持固定步长和自适应步长两种模式
随机梯度下降 (Stochastic Gradient Descent)
函数: stochastic_gradient_descent(f, grad_f, w0, max_iter=1000, step=1e-3, add_noise=0.0, mult_noise=0.0, a=10)
参数说明:
add_noise: 加性噪声强度mult_noise: 乘性噪声强度- 其他参数与梯度下降相同
噪声模型:
- 加性噪声: g += add_noise * 𝒩(0,I)
- 乘性噪声: g *= (1 + mult_noise * 𝒩(0,I))
自适应步长搜索
函数: simple_line_search(f, grad_f, w, d, alpha0=1.0, c=1e-4, tau=0.5)
实现了基于Armijo准则的回溯线搜索：
alpha0: 初始步长c: Armijo参数tau: 步长收缩因子
4、可视化功能
等高线图与优化路径
函数: plot_level_sets_and_path(f, hist, title, xmin=-2, xmax=2, ymin=-1, ymax=3, levels=30)
- 绘制函数的等高线图
- 显示优化算法的迭代路径
- 标记起始点和终点
损失曲线对比
函数: plot_loss_curve(f, *paths, labels)
- 绘制不同算法的收敛曲线
- 使用对数坐标显示损失值变化
二、实验设置
1、参数配置
w0 = np.array([-1.5, 2.0]) # 初始点max_iter = 5000 # 最大迭代次数tol = 1e-8 # 收敛容差alpha = 1e-3 # 固定步长a_quad = 10 # 二次函数参数2、实验内容
-
Rosenbrock函数上的梯度下降
- 固定步长梯度下降
- 带线搜索的梯度下降
-
强凸二次函数上的梯度下降
- 固定步长梯度下降
-
随机梯度下降实验
- Rosenbrock函数 + 加性噪声
- 二次函数 + 加性噪声
- 二次函数 + 乘性噪声
-
算法性能对比
- 收敛曲线对比
- 迭代步数统计
三、使用方法
-
直接运行:
My terminal window python SGD.py -
自定义实验:
# 创建自定义优化实验hist = gradient_descent(your_function, your_gradient, initial_point)plot_level_sets_and_path(your_function, hist, "Your Experiment")
四、输出结果
程序会生成以下可视化结果：
- Rosenbrock函数上的优化路径图（固定步长 vs 自适应步长）
- 二次函数上的优化路径图
- SGD在不同噪声设置下的优化路径图
- 不同算法的损失收敛曲线对比图
五、依赖库
numpy: 数值计算matplotlib: 绘图可视化
六、算法特点分析
1、梯度下降 (GD)
- 优点: 收敛稳定，理论保证强
- 缺点: 可能陷入局部最优，收敛速度慢
2、随机梯度下降 (SGD)
- 优点: 噪声有助于跳出局部最优，适合大规模问题
- 缺点: 收敛路径不稳定，可能在最优解附近震荡
3、自适应步长
- 优点: 自动调节步长，避免步长选择问题
- 缺点: 每次迭代计算开销更大
七、注意事项
- 不同函数需要不同的学习率设置
- 噪声强度需要根据具体问题调节
- Rosenbrock函数比二次函数更难优化
- 实际应用中建议结合多种策略（动量、自适应学习率等）
import numpy as npimport matplotlib.pyplot as plt
# 1. 测试函数和梯度的定义def rosenbrock(w): """ Rosenbrock function """ x, y = w return (1 - x)**2 + 100 * (y - x**2)**2
def grad_rosenbrock(w): """ Gradient of Rosenbrock function """ x, y = w dfdx = -2 * (1 - x) - 400 * x * (y - x**2) dfdy = 200 * (y - x**2) return np.array([dfdx, dfdy])
def quadratic(w, a=10): """ Strongly convex quadratic function. Minimum at [0,0]. Parameter a>0. """ x, y = w return 0.5 * (a * x**2 + y**2)
def grad_quadratic(w, a=10): x, y = w return np.array([a * x, y])
# 2. Adaptive line search (Armijo rule as a simple example)def simple_line_search(f, grad_f, w, d, alpha0=1.0, c=1e-4, tau=0.5): """ Simple backtracking Armijo line search """ alpha = alpha0 f0 = f(w) grad0 = grad_f(w) while f(w + alpha * d) > f0 + c * alpha * np.dot(grad0, d): alpha *= tau if alpha < 1e-10: break return alpha
# 3. Gradient Descent (可选自适应步长，step_func为自适应步长搜索)def gradient_descent(f, grad_f, w0, max_iter=1000, tol=1e-6, alpha=1e-3, use_line_search=False, **kwargs): w = np.array(w0, dtype=float) hist = [w.copy()] for i in range(max_iter): g = grad_f(w) if np.linalg.norm(g) < tol: break if use_line_search: # Adaptive line search direction is always -gradient step = simple_line_search(f, grad_f, w, -g) else: step = alpha w -= step * g hist.append(w.copy()) return np.array(hist)
# 4. Stochastic Gradient Descentdef stochastic_gradient_descent(f, grad_f, w0, max_iter=1000, step=1e-3, add_noise=0.0, mult_noise=0.0, a=10): w = np.array(w0, dtype=float) hist = [w.copy()] for i in range(max_iter): g = grad_f(w) if grad_f != grad_quadratic else grad_f(w, a) # Add noise to gradient g += add_noise * np.random.randn(*g.shape) g *= (1.0 + mult_noise * np.random.randn(*g.shape)) w -= step * g hist.append(w.copy()) return np.array(hist)
# 5. 绘图辅助函数def plot_level_sets_and_path(f, hist, title, xmin=-2, xmax=2, ymin=-1, ymax=3, levels=30): x = np.linspace(xmin, xmax, 400) y = np.linspace(ymin, ymax, 400) X, Y = np.meshgrid(x, y) Z = np.array([[f([i, j]) for i, j in zip(row_x, row_y)] for row_x, row_y in zip(X, Y)]) plt.figure(figsize=(7, 5)) plt.contour(X, Y, Z, levels=levels, cmap='viridis') plt.plot(hist[:, 0], hist[:, 1], 'r.-', label='Path') plt.scatter(hist[0,0], hist[0,1], marker='o', color='blue', label='Start') plt.scatter(hist[-1,0], hist[-1,1], marker='x', color='black', label='End') plt.title(title) plt.xlabel('x') plt.ylabel('y') plt.legend() plt.show()
# ===================== ## ====== 实验区 ====== ## ===================== #
if __name__ == '__main__': # 参数设置 w0 = np.array([-1.5, 2.0]) # 初始点 max_iter = 5000 # 最大迭代 tol = 1e-8 # 收敛容忍 alpha = 1e-3 # 固定步长 a_quad = 10 # 二次函数参数a
# ---- Rosenbrock: 梯度下降与自适应步长 hist_gd_rosen = gradient_descent(rosenbrock, grad_rosenbrock, w0, max_iter, tol, alpha, use_line_search=False) hist_gd_rosen_ls = gradient_descent(rosenbrock, grad_rosenbrock, w0, max_iter, tol, alpha, use_line_search=True) plot_level_sets_and_path(rosenbrock, hist_gd_rosen, 'Gradient Descent on Rosenbrock') plot_level_sets_and_path(rosenbrock, hist_gd_rosen_ls, 'Gradient Descent (+Line Search) on Rosenbrock')
# ---- Convex Quadratic: 梯度下降与自适应步长 hist_gd_quad = gradient_descent(lambda w: quadratic(w, a=a_quad), lambda w: grad_quadratic(w, a=a_quad), w0, max_iter, tol, alpha, use_line_search=False) plot_level_sets_and_path(lambda w: quadratic(w, a=a_quad), hist_gd_quad, 'Gradient Descent on Convex Quadratic')
# ---- SGD: Rosenbrock, 随机扰动 hist_sgd_rosen = stochastic_gradient_descent(rosenbrock, grad_rosenbrock, w0, max_iter=2000, step=1e-4, add_noise=0.1, mult_noise=0.0) plot_level_sets_and_path(rosenbrock, hist_sgd_rosen, 'SGD (Additive noise) on Rosenbrock')
# ---- SGD: Convex Quadratic，加性和乘性噪声实验 hist_sgd_add = stochastic_gradient_descent(quadratic, grad_quadratic, w0, max_iter=2000, step=5e-3, add_noise=1.0, mult_noise=0.0, a=a_quad) hist_sgd_mult = stochastic_gradient_descent(quadratic, grad_quadratic, w0, max_iter=2000, step=5e-3, add_noise=0.0, mult_noise=0.5, a=a_quad) plot_level_sets_and_path(lambda w: quadratic(w, a=a_quad), hist_sgd_add, 'SGD (Add noise) Quadratic') plot_level_sets_and_path(lambda w: quadratic(w, a=a_quad), hist_sgd_mult, 'SGD (Mult noise) Quadratic')
# 对比不同实验 # 收敛曲线对比 def plot_loss_curve(f, *paths, labels): plt.figure() for path, label in zip(paths, labels): loss = [f(w) for w in path] plt.plot(loss, label=label) plt.yscale('log') plt.xlabel('iteration') plt.ylabel('f(w)') plt.legend() plt.title("Loss curve") plt.show()
plot_loss_curve(lambda w: quadratic(w, a=a_quad), hist_gd_quad, hist_sgd_add, hist_sgd_mult, labels=["GD", "SGD (add noise)", "SGD (mult noise)"])
print("Rosenbrock GD steps:", hist_gd_rosen.shape[0]) print("Quadratic GD steps:", hist_gd_quad.shape[0]) print("SGD (add noise) final point:", hist_sgd_add[-1])