非线性规划中的序列二次规划法基础题
题目描述
考虑以下非线性约束优化问题：
最小化目标函数 \(f(x)1, x_2) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束条件：
- 等式约束 \(h(x_1, x_2) = x_1 + x_2 - 2 = 0\)
- 不等式约束 \(g(x_1, x_2) = x_1^2 - x_2 \leq 0\)
要求使用序列二次规划法求解该问题的最优解。
解题过程
1. 方法原理简介
序列二次规划法通过迭代求解一系列二次规划子问题来逼近原问题的最优解。每个子问题基于当前迭代点 \(x_k\) 的拉格朗日函数二阶近似和约束的一阶近似构建。其核心步骤包括：
- 构建拉格朗日函数 \(L(x, \lambda, \mu) = f(x) + \lambda h(x) + \mu g(x)\)（其中 \(\mu \geq 0\)）。
- 在迭代点 \(x_k\) 处，用二次函数近似拉格朗日函数，用线性函数近似约束条件。
- 求解该二次规划子问题，得到搜索方向 \(d_k\)。
- 沿 \(d_k\) 进行一维搜索更新迭代点。
2. 初始化
选择初始点 \(x_0 = (0, 0)\)，该点需满足不等式约束（\(g(0,0) = 0 \leq 0\)）和等式约束（\(h(0,0) = -2 \neq 0\)，但后续子问题会逐步修正）。初始拉格朗日乘子估计值设为 \(\lambda_0 = 0, \mu_0 = 0\)。
3. 第一次迭代（k=0）
步骤 3.1：计算梯度与海森矩阵
- 目标函数梯度：
\(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]\)，在 \(x_0 = (0,0)\) 处：
\(\nabla f(0,0) = [-4, -2]\)。 - 约束梯度：
\(\nabla h(x) = [1, 1]\)（常数），
\(\nabla g(x) = [2x_1, -1]\)，在 \(x_0\) 处：\(\nabla g(0,0) = [0, -1]\)。 - 拉格朗日函数海森矩阵（初始用单位矩阵近似）：
\(B_0 = I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)。
步骤 3.2：构建二次规划子问题
在 \(x_0\) 处，子问题为：
最小化 \(\frac{1}{2} d^T B_0 d + \nabla f(x_0)^T d\)
满足：
- 线性化等式约束：\(h(x_0) + \nabla h(x_0)^T d = 0 \Rightarrow -2 + [1, 1] d = 0\)
- 线性化不等式约束：\(g(x_0) + \nabla g(x_0)^T d \leq 0 \Rightarrow 0 + [0, -1] d \leq 0\)
代入数值后子问题为：
最小化 \(\frac{1}{2} (d_1^2 + d_2^2) - 4d_1 - 2d_2\)
约束：
\(d_1 + d_2 = 2\)（等式约束）
\(-d_2 \leq 0\)（即 \(d_2 \geq 0\)）
步骤 3.3：求解子问题
从等式约束得 \(d_1 = 2 - d_2\)，代入目标函数：
\(\frac{1}{2} [(2-d_2)^2 + d_2^2] - 4(2-d_2) - 2d_2 = \frac{1}{2}(4 - 4d_2 + 2d_2^2) - 8 + 4d_2 - 2d_2 = d_2^2 - 2d_2 + 2 - 8 + 2d_2 = d_2^2 - 6\)。
最小化 \(d_2^2 - 6\) 且满足 \(d_2 \geq 0\)，得 \(d_2 = 0\)，进而 \(d_1 = 2\)。
因此搜索方向 \(d_0 = (2, 0)\)。
步骤 3.4：一维搜索更新迭代点
沿方向 \(d_0\) 更新：\(x_1 = x_0 + \alpha d_0 = (0,0) + \alpha (2, 0) = (2\alpha, 0)\)，其中步长 \(\alpha \in (0, 1]\) 通过减小目标函数且满足约束确定。
代入约束：
- 等式约束 \(h(x_1) = 2\alpha + 0 - 2 = 2\alpha - 2 = 0 \Rightarrow \alpha = 1\)
- 不等式约束 \(g(x_1) = (2\alpha)^2 - 0 = 4\alpha^2 \leq 0 \Rightarrow \alpha = 0\)（与等式约束冲突）
此时需权衡约束满足度。实际SQP中可使用罚函数或过滤器法。此处简化处理，取 \(\alpha = 1\)（优先满足等式约束），得 \(x_1 = (2, 0)\)。
检查约束：\(h(2,0) = 0\)（满足），\(g(2,0) = 4 > 0\)（不满足不等式约束，后续迭代修正）。
4. 第二次迭代（k=1）
步骤 4.1：计算梯度与更新海森矩阵
在 \(x_1 = (2, 0)\) 处：
- \(\nabla f(2,0) = [0, -2]\)
- \(\nabla g(2,0) = [4, -1]\)，\(\nabla h = [1, 1]\)
- 用BFGS公式更新海森矩阵 \(B_1\)（略去详细推导，假设 \(B_1 \approx I\)）。
步骤 4.2：构建并求解新子问题
子问题：
最小化 \(\frac{1}{2} d^T B_1 d + [0, -2] d\)
约束：
\(h(2,0) + [1,1]d = 0 + d_1 + d_2 = 0\)
\(g(2,0) + [4,-1]d \leq 0 \Rightarrow 4 + 4d_1 - d_2 \leq 0\)
解得 \(d_1 = -d_2\)，代入不等式：\(4 - 4d_2 - d_2 \leq 0 \Rightarrow d_2 \geq 0.8\)。
目标函数化为 \(\frac{1}{2}(2d_2^2) - 2d_2 = d_2^2 - 2d_2\)，最小值在 \(d_2 = 1\)（满足 \(d_2 \geq 0.8\)），则 \(d_1 = -1\)。
方向 \(d_1 = (-1, 1)\)。
步骤 4.3：更新迭代点
取 \(\alpha = 1\)：\(x_2 = (2, 0) + (-1, 1) = (1, 1)\)。
检查约束：
- \(h(1,1) = 1 + 1 - 2 = 0\)（满足）
- \(g(1,1) = 1 - 1 = 0 \leq 0\)（满足）
目标函数值 \(f(1,1) = (1-2)^2 + (1-1)^2 = 1\)。
5. 最优性检验
在 \(x_2 = (1,1)\) 处，约束满足，且梯度条件验证：
拉格朗日函数梯度 \(\nabla f + \lambda \nabla h + \mu \nabla g = [-2, 0] + \lambda [1,1] + \mu [2, -1]\)。
代入 \(\lambda = 2, \mu = 2\)（通过求解KKT条件得）可使梯度为零，且 \(\mu \geq 0\)。
因此 \(x^* = (1,1)\) 为最优解，\(f^* = 1\)。
总结
通过两次SQP迭代，从不可行点 \((0,0)\) 逐步收敛到满足所有约束的最优解 \((1,1)\)。关键步骤包括线性化约束、求解二次规划子问题、谨慎选择步长平衡约束满足与目标下降。