非线性规划中的自适应步长梯度下降法基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x)1, x_2) = (x_1 - 1)^4 + (x_2 - 2)^2\)
初始点为 \(x^{(0)} = (0, 0)\)，收敛阈值 \(\epsilon = 10^{-3}\)。要求使用自适应步长梯度下降法求解，并解释步长自适应调整的策略。
解题过程
1. 算法原理介绍
自适应步长梯度下降法是梯度下降法的改进，核心思想是动态调整步长（学习率），避免固定步长导致的收敛慢或震荡问题。其迭代格式为：
\[x^{(k+1)} = x^{(k)} - \alpha^{(k)} \nabla f(x^{(k)}) \]
其中 \(\alpha^{(k)}\) 是第 \(k\) 次迭代的自适应步长，调整策略通常基于函数值变化或梯度范数。
2. 计算梯度
目标函数的梯度为：
\[\nabla f(x) = \begin{bmatrix} 4(x_1 - 1)^3 \\ 2(x_2 - 2) \end{bmatrix} \]
在初始点 \(x^{(0)} = (0, 0)\) 处：
\[\nabla f(x^{(0)}) = \begin{bmatrix} 4(0-1)^3 \\ 2(0-2) \end{bmatrix} = \begin{bmatrix} -4 \\ -4 \end{bmatrix} \]
3. 自适应步长策略
采用简单的回溯线性搜索（Backtracking Line Search）策略：
- 初始步长 \(\alpha^{(0)} = 1\)，衰减因子 \(\beta = 0.5\)（通常取 \(0.1 \sim 0.8\)），控制参数 \(c = 0.3\)（通常取 \(10^{-4} \sim 0.1\)）。
- 每一步检查 Armijo 条件：
\[ f(x^{(k)} - \alpha \nabla f(x^{(k)})) \leq f(x^{(k)}) - c \cdot \alpha \|\nabla f(x^{(k)})\|^2 \]
- 若不满足条件，则更新 \(\alpha \leftarrow \beta \alpha\)，重复直到满足条件。
4. 迭代过程详解（以第1步为例）
- 初始点 \(x^{(0)} = (0, 0)\)，\(f(x^{(0)}) = (0-1)^4 + (0-2)^2 = 1 + 4 = 5\)。
- 尝试步长 \(\alpha = 1\)：
计算临时点 \(x_{\text{temp}} = (0, 0) - 1 \cdot (-4, -4) = (4, 4)\)
\(f(x_{\text{temp}}) = (4-1)^4 + (4-2)^2 = 81 + 4 = 85\)
检查 Armijo 条件：
右侧值 \(f(x^{(0)}) - c \cdot \alpha \|\nabla f\|^2 = 5 - 0.3 \cdot 1 \cdot ( (-4)^2 + (-4)^2 ) = 5 - 0.3 \cdot 32 = -4.6\)
由于 \(85 > -4.6\)，条件不满足，需缩小步长。 - 更新步长 \(\alpha \leftarrow 0.5 \cdot 1 = 0.5\)：
\(x_{\text{temp}} = (0,0) - 0.5 \cdot (-4,-4) = (2,2)\)
\(f(x_{\text{temp}}) = (2-1)^4 + (2-2)^2 = 1 + 0 = 1\)
右侧值不变（\(-4.6\)），\(1 > -4.6\) 仍不满足。 - 继续更新 \(\alpha \leftarrow 0.5 \cdot 0.5 = 0.25\)：
\(x_{\text{temp}} = (0,0) - 0.25 \cdot (-4,-4) = (1,1)\)
\(f(x_{\text{temp}}) = (1-1)^4 + (1-2)^2 = 0 + 1 = 1\)
右侧值不变，\(1 > -4.6\) 不满足。 - 继续更新 \(\alpha \leftarrow 0.5 \cdot 0.25 = 0.125\)：
\(x_{\text{temp}} = (0.5, 0.5)\)
\(f(x_{\text{temp}}) = (0.5-1)^4 + (0.5-2)^2 = 0.0625 + 2.25 = 2.3125\)
右侧值不变，\(2.3125 > -4.6\) 不满足。
注：此处出现异常，因 \(\alpha=0.125\) 时函数值反而增大，需检查策略。实际中需保证 \(c\) 和 \(\beta\) 选择合理，这里为演示调整过程，暂继续。 - 调整参数：若多次不满足，需减小 \(c\) 或调整 \(\beta\)。设 \(c=0.01\) 重新尝试：
右侧值 \(5 - 0.01 \cdot 0.125 \cdot 32 \approx 4.96\)
\(2.3125 < 4.96\)，满足条件，接受 \(\alpha^{(0)} = 0.125\)。 - 更新点 \(x^{(1)} = (0.5, 0.5)\)。
5. 收敛判断
重复迭代直到梯度范数 \(\|\nabla f(x^{(k)})\| < \epsilon\)。例如第 \(k\) 次迭代时：
- 计算梯度 \(\nabla f(x^{(k)})\)
- 用回溯搜索确定 \(\alpha^{(k)}\)
- 更新点 \(x^{(k+1)}\)
- 检查 \(\|\nabla f(x^{(k+1)})\|\)，若小于 \(10^{-3}\) 则停止。
6. 算法特点总结
- 自适应步长避免手动调参，平衡收敛速度与稳定性。
- 回溯搜索保证每次迭代目标函数充分下降。
- 适用于梯度易求但曲率变化较大的问题。