序列二次规划法基础题
题目描述
考虑非线性约束优化问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束：
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = x_1^2 - x_2 \leq 0\)
初始点 \(x^{(0)} = (0, 0)\)，使用序列二次规划法求解该问题。
解题过程
序列二次规划法通过迭代求解一系列二次规划子问题逼近原问题的最优解。每个子问题基于当前点的函数值、梯度及Hessian信息构建。
步骤1: 初始化
设置初始点 \(x^{(0)} = (0, 0)\)，容忍误差 \(\epsilon = 10^{-6}\)，迭代计数器 \(k = 0\)。计算初始点的目标函数值 \(f(x^{(0)}) = (0-2)^2 + (0-1)^2 = 5\)，约束函数值 \(g_1(x^{(0)}) = 0 + 0 - 2 = -2\)（满足≤0），\(g_2(x^{(0)}) = 0 - 0 = 0\)（临界满足）。
步骤2: 构建当前迭代的二次规划子问题
在点 \(x^{(k)}\) 处，子问题形式为：
最小化 \(\nabla f(x^{(k)})^T d + \frac{1}{2} d^T H_k d\)
满足 \(\nabla g_i(x^{(k)})^T d + g_i(x^{(k)}) \leq 0 \quad (i=1,2)\)
其中 \(d\) 是搜索方向，\(H_k\) 是拉格朗日函数的Hessian近似。
- 计算梯度：
\(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]\)，在 \(x^{(0)}\) 处为 \([-4, -2]\)
\(\nabla g_1(x) = [1, 1]\)（常数）
\(\nabla g_2(x) = [2x_1, -1]\)，在 \(x^{(0)}\) 处为 \([0, -1]\) - 初始Hessian \(H_0\) 通常设为单位矩阵 \(I\)。
子问题具体形式：
最小化 \(-4d_1 - 2d_2 + \frac{1}{2}(d_1^2 + d_2^2)\)
满足 \(d_1 + d_2 - 2 \leq 0\)（因 \(g_1(x^{(0)}) = -2\)，约束为 \(1 \cdot d_1 + 1 \cdot d_2 + (-2) \leq 0\)）
\(-d_2 + 0 \leq 0\)（因 \(g_2(x^{(0)}) = 0\)，约束为 \(0 \cdot d_1 + (-1) \cdot d_2 + 0 \leq 0\)，即 \(d_2 \geq 0\)）
步骤3: 求解二次规划子问题
子问题为凸二次规划，可用有效集法求解。
- 目标函数改写为 \(\frac{1}{2} d^T I d + [-4, -2]^T d\)。
- 约束条件：
\(d_1 + d_2 \leq 2\)（线性不等式）
\(d_2 \geq 0\)（等价于 \(-d_2 \leq 0\)）
求解得最优解 \(d^* = (d_1, d_2)\)。通过拉格朗日法：
构造拉格朗日函数 \(L(d, \lambda) = -4d_1 - 2d_2 + \frac{1}{2}(d_1^2 + d_2^2) + \lambda_1(d_1 + d_2 - 2) + \lambda_2(-d_2)\)。
KKT条件：
- \(\frac{\partial L}{\partial d_1} = -4 + d_1 + \lambda_1 = 0\)
- \(\frac{\partial L}{\partial d_2} = -2 + d_2 + \lambda_1 - \lambda_2 = 0\)
- \(\lambda_1(d_1 + d_2 - 2) = 0\), \(\lambda_2(-d_2) = 0\)
- \(\lambda_1, \lambda_2 \geq 0\)。
试探约束活动情况：
- 若 \(\lambda_2 > 0\)（即 \(d_2 = 0\)），由条件1和2得 \(d_1 = 4 - \lambda_1\), \(-2 + \lambda_1 - \lambda_2 = 0\)。若 \(d_1 + d_2 - 2 < 0\)（非活动），则 \(\lambda_1 = 0\)，推出 \(d_1 = 4\), \(\lambda_2 = -2\)（违反非负），不可行。
- 若 \(d_1 + d_2 - 2 = 0\)（活动）且 \(d_2 > 0\)（即 \(\lambda_2 = 0\)）：
由条件1、2及约束方程：
\(d_1 = 4 - \lambda_1\), \(d_2 = 2 - \lambda_1\), 代入 \(d_1 + d_2 = 2\) 得 \((4 - \lambda_1) + (2 - \lambda_1) = 2 \Rightarrow \lambda_1 = 2\)。
则 \(d_1 = 2\), \(d_2 = 0\)，但 \(d_2 = 0\) 与假设 \(d_2 > 0\) 矛盾。 - 若两个约束均活动（\(d_2 = 0\) 且 \(d_1 + d_2 - 2 = 0\)）：
则 \(d_1 = 2\), \(d_2 = 0\)。由条件1得 \(\lambda_1 = 2\)，条件2得 \(-2 + 0 + 2 - \lambda_2 = 0 \Rightarrow \lambda_2 = 0\)。满足KKT条件。
故子问题解为 \(d^{(0)} = (2, 0)\)，拉格朗日乘子 \(\lambda^{(0)} = (2, 0)\)。
步骤4: 计算步长与更新迭代点
- 计算最大允许步长 \(\alpha_{\max}\) 确保满足约束：沿方向 \(d^{(0)}\)，约束 \(g_1\) 和 \(g_2\) 需保持≤0。检验发现 \(\alpha = 1\) 时 \(x^{(0)} + d^{(0)} = (2, 0)\)，\(g_1 = 2 + 0 - 2 = 0\)，\(g_2 = 4 - 0 = 4 > 0\)（违反）。需缩小步长。
- 使用线搜索（如Armijo准则）确定步长 \(\alpha_k\)。简单起见，本例设 \(\alpha_k = 0.5\)（实际应用需正规搜索）。
- 新点 \(x^{(1)} = x^{(0)} + 0.5 d^{(0)} = (0, 0) + 0.5 \cdot (2, 0) = (1, 0)\)。
计算 \(f(x^{(1)}) = (1-2)^2 + (0-1)^2 = 2\)，约束 \(g_1 = 1 + 0 - 2 = -1\)（满足），\(g_2 = 1 - 0 = 1 > 0\)（违反，但迭代中允许暂时违反，通过罚函数或修复处理）。
步骤5: 更新Hessian近似与检查收敛
- 使用BFGS公式更新 \(H_k\)。需计算拉格朗日函数梯度差 \(y_k = \nabla_x L(x^{(1)}, \lambda^{(1)}) - \nabla_x L(x^{(0)}, \lambda^{(0)})\)，其中拉格朗日函数 \(L(x, \lambda) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x)\)。
在 \(x^{(1)} = (1, 0)\)，乘子 \(\lambda^{(1)}\) 取自子问题解（需调整），简单起见设 \(\lambda^{(1)} = \lambda^{(0)} = (2, 0)\)。
计算 \(\nabla_x L(x^{(1)}, \lambda^{(1)}) = \nabla f(x^{(1)}) + 2 \nabla g_1(x^{(1)}) + 0 \cdot \nabla g_2(x^{(1)}) = [-2, -2] + 2 \cdot [1, 1] = [0, 0]\)。
类似地，\(\nabla_x L(x^{(0)}, \lambda^{(0)}) = [-4, -2] + 2 \cdot [1, 1] + 0 = [-2, 0]\)。
则 \(y_k = [0, 0] - [-2, 0] = [2, 0]\)，位移 \(s_k = x^{(1)} - x^{(0)} = (1, 0)\)。
BFGS更新：若 \(s_k^T y_k > 0\)，则 \(H_{k+1} = H_k - \frac{H_k s_k s_k^T H_k}{s_k^T H_k s_k} + \frac{y_k y_k^T}{s_k^T y_k}\)。
此处 \(s_k^T y_k = 1 \cdot 2 + 0 \cdot 0 = 2 > 0\)，更新后 \(H_1\) 不再为单位阵。 - 检查收敛：若 \(\| d^{(k)} \| < \epsilon\) 且约束违反量小，则停止。本例 \(\| d^{(0)} \| = 2 > \epsilon\)，继续迭代。
步骤6: 后续迭代
重复步骤2-5，直至收敛。最终逼近最优解 \(x^* \approx (1, 1)\)（实际解需验证满足KKT条件：\(f(x)\) 在约束下的最小值在 \(x = (1, 1)\) 处，\(f(1,1) = 2\)，约束 \(g_1 = 0\), \(g_2 = 0\)）。
总结
序列二次规划法通过迭代求解二次规划子问题，逐步修正搜索方向和步长，结合Hessian更新确保超线性收敛。关键点在于子问题的构建与求解，以及步长的选择以平衡约束满足和目标函数下降。