非线性规划中的约束变尺度法基础题
题目描述
考虑非线性规划问题：
最小化目标函数 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束条件：
- \(h(x) = x_1 + x_2 - 2 = 0\)（等式约束）
- \(g(x) = x_1^2 - x_2 \leq 0\)（不等式约束）
初始点 \(x^{(0)} = (0, 0)\)，要求使用约束变尺度法（如基于拉格朗日函数的拟牛顿法）求解该问题。
解题过程
约束变尺度法结合了拉格朗日乘子法和拟牛顿法的思想，通过迭代更新拉格朗日函数的Hessian矩阵近似，同时处理等式和不等式约束。以下是详细步骤：
1. 构造拉格朗日函数
拉格朗日函数为：
\[L(x, \lambda, \mu) = f(x) + \lambda h(x) + \mu g(x) \]
其中 \(\lambda\) 是等式约束的乘子，\(\mu \geq 0\) 是不等式约束的乘子。代入具体函数：
\[L(x, \lambda, \mu) = (x_1 - 2)^2 + (x_2 - 1)^2 + \lambda (x_1 + x_2 - 2) + \mu (x_1^2 - x_2) \]
2. 初始点检验与乘子初始化
在 \(x^{(0)} = (0, 0)\) 处：
- 等式约束 \(h(0,0) = -2 \neq 0\)，违反约束。
- 不等式约束 \(g(0,0) = 0 \leq 0\)，满足。
初始化乘子：通常设 \(\lambda^{(0)} = 0\)，\(\mu^{(0)} = 0\)（若约束满足则乘子为0，但此处需后续调整）。
3. 求解拉格朗日函数的KKT条件
KKT条件包括：
- 梯度条件： \(\nabla_x L = 0\)
- 等式约束： \(h(x) = 0\)
- 不等式约束： \(g(x) \leq 0, \mu \geq 0, \mu g(x) = 0\)
计算梯度：
\[\nabla_x L = \begin{bmatrix} 2(x_1 - 2) + \lambda + 2\mu x_1 \\ 2(x_2 - 1) + \lambda - \mu \end{bmatrix} \]
在迭代中，我们需逐步逼近满足这些条件的解。
4. 约束变尺度法的迭代步骤
步骤4.1 确定当前积极约束
在 \(x^{(k)}\) 处，检查不等式约束：
- 若 \(g(x^{(k)}) = 0\)，则约束积极，保留在子问题中；
- 若 \(g(x^{(k)}) < 0\)，则约束非积极，暂时忽略（设 \(\mu = 0\)）。
在 \(x^{(0)} = (0,0)\)，\(g(0,0) = 0\)，因此不等式约束积极。
步骤4.2 构建二次规划子问题
在当前点 \(x^{(k)}\)，用一阶泰勒展开近似约束，用二次函数近似拉格朗日函数：
- 目标：最小化 \(\nabla f(x^{(k)})^T d + \frac{1}{2} d^T B_k d\)（其中 \(d = x - x^{(k)}\) 是搜索方向，\(B_k\) 是拉格朗日函数Hessian的拟牛顿近似）。
- 约束： \(\nabla h(x^{(k)})^T d + h(x^{(k)}) = 0\)，\(\nabla g(x^{(k)})^T d + g(x^{(k)}) \leq 0\)。
在 \(x^{(0)}\) 处：
\[\nabla f(0,0) = [-4, -2], \quad \nabla h(0,0) = [1, 1], \quad \nabla g(0,0) = [0, -1] \]
初始 \(B_0\) 通常设为单位矩阵 \(I\)。子问题为：
最小化 \(-4d_1 - 2d_2 + \frac{1}{2} (d_1^2 + d_2^2)\)
满足 \(d_1 + d_2 - 2 = 0\) 和 \(-d_2 \leq 0\)。
步骤4.3 求解子问题得搜索方向
通过二次规划求解器或拉格朗日乘子法解子问题。本例中：
- 等式约束 \(d_1 + d_2 = 2\) 结合目标函数，代入 \(d_1 = 2 - d_2\) 后优化单变量函数，得到 \(d^{(0)} = (1, 1)\)。
- 新点 \(x^{(1)} = x^{(0)} + d^{(0)} = (1, 1)\)。
步骤4.4 更新乘子和Hessian近似
- 乘子更新：通过子问题的乘子估计当前拉格朗日乘子。例如，子问题中等式约束乘子为 \(\lambda^{(1)} \approx 2\)，不等式约束乘子 \(\mu^{(1)} \approx 1\)（需满足非负性）。
- Hessian更新：使用拟牛顿法（如BFGS公式）更新 \(B_k\)。基于拉格朗日函数梯度的变化：
\[s = x^{(1)} - x^{(0)} = (1, 1), \quad y = \nabla_x L(x^{(1)}, \lambda^{(1)}, \mu^{(1)}) - \nabla_x L(x^{(0)}, \lambda^{(1)}, \mu^{(1)}) \]
计算 \(y\) 后，应用BFGS公式： \(B_{k+1} = B_k - \frac{B_k s s^T B_k}{s^T B_k s} + \frac{y y^T}{s^T y}\)。
5. 收敛检验
重复迭代直到满足：
- 约束违反度 \(|h(x)| + \max(0, g(x)) < \epsilon\)（例如 \(\epsilon = 10^{-6}\)）
- 梯度条件 \(\|\nabla_x L\| < \epsilon\)。
最终解近似为 \(x^* = (1, 1)\)，此时 \(f(x^*) = 1\)，约束均满足。
关键点说明
- 约束变尺度法通过逐次二次规划逼近，兼顾超线性收敛和约束处理。
- 积极集策略动态调整不等式约束，避免无效计算。
- BFGS更新保持Hessian正定性，确保子问题可解。