非线性规划中的投影梯度法基础题
题目描述：
考虑非线性规划问题：
\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]
满足约束：
\[x_1 + x_2 \leq 2, \quad x_1 \geq 0, \quad x_2 \geq 0. \]
要求使用投影梯度法求解该问题，从初始点 \(x^{(0)} = (0, 0)\) 开始，迭代两步，并分析结果。
解题过程：
1. 投影梯度法原理简介
投影梯度法用于求解带约束的非线性规划问题。其核心思想是：
- 在每一步迭代中，先计算目标函数的负梯度方向（最速下降方向）。
- 若沿该方向移动会超出可行域，则将移动后的点投影回可行域。
- 投影操作通过求解一个子问题（将点映射到可行域上最近的点）实现。
该方法适用于线性约束或简单凸约束问题。
2. 问题分析
目标函数 \(f(x)\) 是凸二次函数，约束为线性不等式，构成一个凸可行域（三角形区域）。投影梯度法的迭代公式为：
\[x^{(k+1)} = P_X \left( x^{(k)} - \alpha_k \nabla f(x^{(k)}) \right), \]
其中 \(P_X\) 是投影算子，\(\alpha_k\) 为步长（需选择以保证收敛性）。
3. 计算梯度与投影算子
梯度为：
\[\nabla f(x) = [2(x_1 - 2), \quad 2(x_2 - 1)]^\top. \]
可行域 \(X = \{ x \mid x_1 + x_2 \leq 2, \, x_1 \geq 0, \, x_2 \geq 0 \}\)。投影算子 \(P_X(y)\) 的定义为：
\[P_X(y) = \arg\min_{x \in X} \|x - y\|^2. \]
对于本例的三角形可行域，投影可通过几何方法或求解二次规划子问题实现。
4. 迭代步骤（固定步长 \(\alpha_k = 0.5\)）
第1步：从 \(x^{(0)} = (0, 0)\) 开始
- 计算梯度：\(\nabla f(0, 0) = [-4, -2]^\top\)。
- 沿负梯度方向移动：\(y^{(1)} = (0, 0) - 0.5 \cdot [-4, -2] = (2, 1)\)。
- 投影回可行域：点 \((2, 1)\) 满足 \(x_1 + x_2 = 3 > 2\)，需投影到边界 \(x_1 + x_2 = 2\) 上。通过最小化距离平方：
设投影点为 \((p_1, p_2)\)，解：
\[ \min (p_1 - 2)^2 + (p_2 - 1)^2 \quad \text{s.t.} \quad p_1 + p_2 = 2, \, p_1, p_2 \geq 0. \]
代入 \(p_2 = 2 - p_1\)，得：
\[ \min (p_1 - 2)^2 + (1 - p_1)^2 = 2(p_1 - 1.5)^2 + 0.5. \]
最小值在 \(p_1 = 1.5\) 处，此时 \(p_2 = 0.5\)，且满足非负约束。故投影点为 \(x^{(1)} = (1.5, 0.5)\)。
第2步：从 \(x^{(1)} = (1.5, 0.5)\) 开始
- 计算梯度：\(\nabla f(1.5, 0.5) = [-1, -1]^\top\)。
- 沿负梯度移动：\(y^{(2)} = (1.5, 0.5) - 0.5 \cdot [-1, -1] = (2, 1)\)。
- 投影：与第1步相同，得 \(x^{(2)} = (1.5, 0.5)\)。
此时迭代点不再变化，算法终止。
5. 结果分析
- 最终点 \(x^* = (1.5, 0.5)\) 在边界 \(x_1 + x_2 = 2\) 上。
- 通过KKT条件验证最优性：
拉格朗日函数 \(L = f(x) + \lambda (x_1 + x_2 - 2) - \mu_1 x_1 - \mu_2 x_2\)，
在 \(x^*\) 处，梯度条件 \(\nabla f + \lambda (1, 1) - (\mu_1, \mu_2) = 0\) 成立（\(\lambda = 1, \mu_1 = \mu_2 = 0\)），且满足互补松弛条件。 - 由于问题凸，\(x^*\) 为全局最优解。
结论
投影梯度法在两步内收敛到最优解，体现了其处理线性约束的有效性。步长选择影响收敛速度，实际中可通过线搜索优化。