非线性规划中的自适应记忆梯度法 (Adaptive Memory Gradient Method) 基础题
题目描述
考虑以下无约束非线性规划问题：
\[\min_{x \in \mathbb{R}^n} f(x) \]
其中目标函数 \(f(x): \mathbb{R}^n \to \mathbb{R}\) 是连续可微但不一定是凸的。已知该函数在最优解附近可能具有病态 Hessian 矩阵（即特征值差异很大），导致标准梯度下降或共轭梯度法收敛缓慢。
你的任务是：应用自适应记忆梯度法 (AMGM) 来求解此问题，并解释该方法如何通过利用过往迭代点的梯度信息来动态调整搜索方向，以改善收敛性能。
为了具体说明，我们取 \(n=2\)，并假设：
\[f(x) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2 \]
（即经典 Rosenbrock 函数，它是病态测试函数）。初始点设为 \(x_0 = (-1.2, 1)^T\)。要求使用自适应记忆梯度法进行迭代，并详细说明每一步的计算过程。
解题过程
自适应记忆梯度法是一种改进的梯度类方法，它在每次迭代中不仅使用当前梯度，还利用前几步的梯度信息构造一个“记忆”方向，以加速收敛。其核心思想是：通过组合多个历史梯度，动态生成一个下降方向，该方向能更好地适应目标函数的局部曲率。
下面，我们按照 初始化、迭代步骤、方向计算、步长选择、终止判断 的顺序，一步步讲解如何用自适应记忆梯度法求解上述问题。
第一步：理解算法框架
自适应记忆梯度法的迭代格式为：
\[x_{k+1} = x_k + \alpha_k d_k \]
其中：
- \(d_k\) 是搜索方向，由当前梯度与历史梯度的线性组合构成。
- \(\alpha_k > 0\) 是步长，通常通过线搜索（如 Armijo 条件）确定。
方向 \(d_k\) 的构造公式为：
\[d_k = -\nabla f(x_k) + \beta_k d_{k-1} + \sum_{i=1}^{m} \gamma_{k,i} \nabla f(x_{k-i}) \]
其中 \(\beta_k\) 和 \(\gamma_{k,i}\) 是自适应参数，用于调整历史信息的影响。在简化版本中，常取 \(m=1\)（即只记忆上一步梯度），此时：
\[d_k = -\nabla f(x_k) + \beta_k (d_{k-1} + \theta_k \nabla f(x_{k-1})) \]
其中 \(\beta_k, \theta_k\) 是根据梯度变化自适应计算的参数。
为了简化，我们采用一种经典的自适应记忆梯度公式（Shor 等提出），其中方向更新为：
\[d_k = -\nabla f(x_k) + \beta_k s_{k-1} + \gamma_k y_{k-1} \]
其中：
- \(s_{k-1} = x_k - x_{k-1}\)（上一步的位移向量）。
- \(y_{k-1} = \nabla f(x_k) - \nabla f(x_{k-1})\)（上一步的梯度变化）。
- \(\beta_k, \gamma_k\) 是自适应参数，计算公式为：
\[\beta_k = \frac{s_{k-1}^T \nabla f(x_k)}{s_{k-1}^T y_{k-1}}, \quad \gamma_k = -\frac{y_{k-1}^T \nabla f(x_k)}{s_{k-1}^T y_{k-1}} \]
但此公式需保证 \(s_{k-1}^T y_{k-1} > 0\)（可通过 Wolfe 线搜索条件保证）。
在基础题中，我们可以采用一种更简单的自适应策略：将方向设为当前负梯度与前一步方向的凸组合，权重根据梯度夹角自适应调整。
我们使用的简化算法步骤如下：
- 令初始方向 \(d_0 = -\nabla f(x_0)\)。
- 在第 \(k\) 步 (\(k \ge 1\))，计算当前梯度 \(g_k = \nabla f(x_k)\) 和前一步梯度 \(g_{k-1}\)。
- 计算梯度变化角度的余弦值：
\[\cos\theta_k = \frac{g_k^T g_{k-1}}{\|g_k\| \|g_{k-1}\|} \]
- 设定自适应参数：
\[\beta_k = \eta \cdot \max(0, \cos\theta_k) \]
其中 \(\eta \in (0,1)\) 是预设常数（如 \(\eta=0.5\)），用于控制记忆强度。
5. 更新方向：
\[d_k = -g_k + \beta_k d_{k-1} \]
- 用 Armijo 线搜索确定步长 \(\alpha_k\)。
- 更新迭代点：\(x_{k+1} = x_k + \alpha_k d_k\)。
- 检查终止条件（如 \(\|g_k\| < 10^{-6}\) 或达到最大迭代次数）。
第二步：计算初始点信息
给定 \(f(x) = 100(x_2 - x_1^2)^2 + (1 - x_1)^2\)，计算梯度：
\[\nabla f(x) = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \end{pmatrix} = \begin{pmatrix} -400 x_1 (x_2 - x_1^2) - 2(1 - x_1) \\ 200 (x_2 - x_1^2) \end{pmatrix} \]
在初始点 \(x_0 = (-1.2, 1)^T\) 处：
\[\nabla f(x_0) = \begin{pmatrix} -400(-1.2)(1 - (-1.2)^2) - 2(1 - (-1.2)) \\ 200(1 - (-1.2)^2) \end{pmatrix} = \begin{pmatrix} 480(1 - 1.44) - 2(2.2) \\ 200(1 - 1.44) \end{pmatrix} = \begin{pmatrix} 480(-0.44) - 4.4 \\ 200(-0.44) \end{pmatrix} = \begin{pmatrix} -211.2 - 4.4 \\ -88 \end{pmatrix} = \begin{pmatrix} -215.6 \\ -88 \end{pmatrix} \]
初始方向取负梯度：
\[d_0 = -\nabla f(x_0) = \begin{pmatrix} 215.6 \\ 88 \end{pmatrix} \]
第三步：第一次迭代（\(k=1\)）
1. 线搜索求步长 \(\alpha_0\)
我们使用 Armijo 条件：选择 \(\alpha\) 使得
\[f(x_0 + \alpha d_0) \le f(x_0) + c \alpha \nabla f(x_0)^T d_0 \]
其中 \(c=10^{-4}\)（常用值）。由于 \(d_0\) 是下降方向（\(\nabla f(x_0)^T d_0 = -\| \nabla f(x_0) \|^2 < 0\)），可通过回溯法找到合适的 \(\alpha\)。
为简化演示，我们通过尝试几个值快速确定。手工估算：
取 \(\alpha_0 = 0.001\)，计算 \(x_1 = x_0 + 0.001 d_0 = \begin{pmatrix} -1.2 + 0.2156 \\ 1 + 0.088 \end{pmatrix} = \begin{pmatrix} -0.9844 \\ 1.088 \end{pmatrix}\)。
计算 \(f(x_1)\) 和 \(f(x_0)\)：
- \(f(x_0) = 100(1 - 1.44)^2 + (1 - (-1.2))^2 = 100(0.1936) + (2.2)^2 = 19.36 + 4.84 = 24.2\)。
- 快速估算 \(f(x_1)\)：因 \(x_2 - x_1^2 = 1.088 - (-0.9844)^2 \approx 1.088 - 0.969 \approx 0.119\)，所以第一项约 \(100(0.119^2) \approx 1.416\)，第二项 \((1 - (-0.9844))^2 \approx (1.9844)^2 \approx 3.938\)，合计约 \(5.354\)，确实下降。
Armijo 检查：左端 \(f(x_1) \approx 5.354\)，右端 \(f(x_0) + c \alpha \nabla f(x_0)^T d_0 = 24.2 + 10^{-4} \cdot 0.001 \cdot (- \| \nabla f(x_0) \|^2)\)，由于 \(\| \nabla f(x_0) \|^2 = 215.6^2 + 88^2 \approx 46483.36 + 7744 = 54227.36\)，右端项约为 \(24.2 - 0.0054227 \approx 24.1946\)，显然条件满足。
2. 计算 \(x_1\) 处的梯度
在 \(x_1 = (-0.9844, 1.088)^T\)：
\[\nabla f(x_1) = \begin{pmatrix} -400(-0.9844)(1.088 - (-0.9844)^2) - 2(1 - (-0.9844)) \\ 200(1.088 - (-0.9844)^2) \end{pmatrix} \]
先算 \((-0.9844)^2 \approx 0.969\)，则 \(x_2 - x_1^2 \approx 1.088 - 0.969 = 0.119\)。
于是：
\[\frac{\partial f}{\partial x_2} = 200 \times 0.119 = 23.8 \]
\[ \frac{\partial f}{\partial x_1} = -400(-0.9844)(0.119) - 2(1.9844) = 400 \times 0.9844 \times 0.119 - 3.9688 \]
\(0.9844 \times 0.119 \approx 0.1171\)，乘以 400 得 46.84，减去 3.9688 得 42.8712。
所以：
\[g_1 = \nabla f(x_1) \approx \begin{pmatrix} 42.8712 \\ 23.8 \end{pmatrix} \]
3. 计算自适应参数 \(\beta_1\)
计算梯度夹角余弦：
\[\cos\theta_1 = \frac{g_1^T g_0}{\|g_1\| \|g_0\|} = \frac{42.8712 \times (-215.6) + 23.8 \times (-88)}{\|g_1\| \|g_0\|} \]
分子 ≈ \(-9243.5 - 2094.4 = -11337.9\)。
分母：\(\|g_0\| = \sqrt{215.6^2 + 88^2} \approx \sqrt{46483.36 + 7744} = \sqrt{54227.36} \approx 232.86\)；\(\|g_1\| = \sqrt{42.8712^2 + 23.8^2} \approx \sqrt{1838.0 + 566.44} = \sqrt{2404.44} \approx 49.04\)。
分母乘积 ≈ \(232.86 \times 49.04 \approx 11419.6\)。
所以 \(\cos\theta_1 \approx -11337.9 / 11419.6 \approx -0.9928\)。
由于 \(\cos\theta_1 < 0\)，表示梯度方向发生了较大变化（说明函数曲率变化大），我们取 \(\beta_1 = \eta \cdot \max(0, \cos\theta_1) = 0.5 \times 0 = 0\)。这意味着我们暂时放弃记忆，方向完全由当前负梯度决定。
4. 更新方向
\[d_1 = -g_1 + \beta_1 d_0 = -g_1 = \begin{pmatrix} -42.8712 \\ -23.8 \end{pmatrix} \]
5. 第二次迭代（\(k=2\)）
用 Armijo 线搜索求 \(\alpha_1\)（过程类似，此处略），更新 \(x_2 = x_1 + \alpha_1 d_1\)，然后计算 \(g_2\)，再计算 \(\cos\theta_2 = \frac{g_2^T g_1}{\|g_2\| \|g_1\|}\)，若 \(\cos\theta_2 > 0\)，则 \(\beta_2 = 0.5 \cos\theta_2\)，方向更新为 \(d_2 = -g_2 + \beta_2 d_1\)；否则 \(\beta_2=0\)，方向重置为负梯度。
第四步：算法特性与终止
通过上述流程，自适应记忆梯度法能够：
- 当连续梯度方向相近（\(\cos\theta_k > 0\)）时，引入历史方向以加速（类似共轭梯度效果）。
- 当梯度方向剧烈变化（\(\cos\theta_k \le 0\)）时，自动退化为最速下降，避免错误累积。
- 对于 Rosenbrock 函数，初始阶段梯度方向变化大，记忆项常为零；接近谷底时梯度方向趋于一致，记忆项可帮助沿谷底方向快速前进。
终止条件通常为梯度范数小于给定容差（如 \(10^{-6}\)）或达到最大迭代次数。
关键点总结
- 记忆机制：通过 \(\cos\theta_k\) 衡量梯度变化，自适应地混合历史方向。
- 方向构造：\(d_k = -g_k + \beta_k d_{k-1}\)，其中 \(\beta_k = \eta \max(0, \cos\theta_k)\)。
- 步长选择：使用 Armijo 线搜索保证下降性。
- 适用场景：适用于 Hessian 病态、梯度方向变化不剧烈的区域，能比纯梯度下降更快收敛。
通过这个基础题目，你掌握了自适应记忆梯度法的核心思想和基本步骤。该方法在无约束优化中是一种简单而有效的梯度类改进算法。