非线性规划中的改进的序列二次规划(SQP)算法基础题
题目描述
考虑如下非线性规划问题：
\[\min f(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1 \]
\[\text{s.t. } g_1(x) = x_1 + x_2 - 2 \leq 0, \]
\[g_2(x) = -x_1 + 2x_2 - 3 \leq 0, \]
\[x_1 \geq 0, x_2 \geq 0. \]
要求使用改进的序列二次规划（SQP）算法，从初始点 \(x^{(0)} = (0, 0)\) 开始，迭代求解该问题。改进的SQP通过引入适当的Hessian矩阵修正和线搜索策略，增强传统SQP的收敛性和稳定性。
解题过程
1. 算法原理概述
改进的SQP算法在每一步迭代中：
- 构建当前迭代点 \(x^{(k)}\) 处的二次规划（QP）子问题，用目标函数的二阶近似（Hessian矩阵）和约束的一阶近似（梯度）代替原问题；
- 通过求解QP子问题得到搜索方向 \(d^{(k)}\)；
- 使用线搜索（如Armijo准则）确定步长 \(\alpha_k\)，确保目标函数充分下降且满足约束；
- 更新迭代点：\(x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}\)。
改进的关键在于：- 用拟牛顿法（如BFGS公式）更新Hessian矩阵，避免计算精确Hessian；
- 引入罚函数或滤子法处理约束，保证全局收敛性。
2. 第一次迭代（k=0）
初始点：\(x^{(0)} = (0, 0)\)，目标函数值 \(f(x^{(0)}) = 0\)。
2.1 计算梯度和约束值
- 目标函数梯度：\(\nabla f(x) = [2x_1 - 2x_2 - 4, 4x_2 - 2x_1]\)，
\(\nabla f(x^{(0)}) = [-4, 0]\)。 - 约束梯度：
\(\nabla g_1(x) = [1, 1]\)，\(\nabla g_2(x) = [-1, 2]\)。 - 约束值：
\(g_1(x^{(0)}) = -2 \leq 0\)（非活跃），
\(g_2(x^{(0)}) = -3 \leq 0\)（非活跃）。
2.2 构建QP子问题
初始Hessian矩阵 \(H_0\) 取单位矩阵 \(I_2\)。
QP子问题为：
\[\min_d \frac{1}{2} d^T H_0 d + \nabla f(x^{(0)})^T d = \frac{1}{2} (d_1^2 + d_2^2) - 4d_1 \]
\[\text{s.t. } \nabla g_1(x^{(0)})^T d + g_1(x^{(0)}) \leq 0 \Rightarrow d_1 + d_2 - 2 \leq 0, \]
\[\nabla g_2(x^{(0)})^T d + g_2(x^{(0)}) \leq 0 \Rightarrow -d_1 + 2d_2 - 3 \leq 0, \]
\[d_1 \geq -x_1^{(0)} = 0, \quad d_2 \geq -x_2^{(0)} = 0. \]
2.3 求解QP子问题
忽略非活跃约束（因约束值远小于0），仅保留边界约束 \(d_1 \geq 0, d_2 \geq 0\)。
目标函数凸，最小值在梯度为零处：
\[d_1 - 4 = 0 \Rightarrow d_1 = 4, \quad d_2 = 0. \]
验证约束：\(d_1 + d_2 - 2 = 2 > 0\)，违反 \(g_1\) 的线性化约束！需重新求解带约束的QP。
精确求解QP：
使用拉格朗日法，引入乘子 \(\lambda_1, \lambda_2 \geq 0\) 对应两个不等式约束，及 \(\mu_1, \mu_2 \geq 0\) 对应边界约束。
通过KKT条件解得：
\(d^{(0)} = (2, 0)\)，对应活跃约束为 \(d_1 + d_2 - 2 = 0\) 和 \(d_1 \geq 0\)。
2.4 线搜索
尝试步长 \(\alpha = 1\)：
\(x^{(1)} = (0, 0) + 1 \cdot (2, 0) = (2, 0)\)，
\(f(x^{(1)}) = 4 + 0 - 0 - 8 = -4\)，
约束：\(g_1(2,0) = 2 + 0 - 2 = 0\)（活跃），\(g_2(2,0) = -2 + 0 - 3 = -5\)（满足）。
目标函数下降（从0到-4），接受 \(\alpha = 1\)。
3. 第二次迭代（k=1）
当前点：\(x^{(1)} = (2, 0)\)，\(f(x^{(1)}) = -4\)。
3.1 计算梯度和约束值
- \(\nabla f(x^{(1)}) = [2\cdot2 - 2\cdot0 - 4, 4\cdot0 - 2\cdot2] = [0, -4]\)。
- 约束值：\(g_1(x^{(1)}) = 0\)（活跃），\(g_2(x^{(1)}) = -5\)（非活跃）。
3.2 更新Hessian矩阵（BFGS公式）
令 \(s_0 = x^{(1)} - x^{(0)} = (2, 0)\)，
\(y_0 = \nabla f(x^{(1)}) - \nabla f(x^{(0)}) = [0 - (-4), -4 - 0] = [4, -4]\)。
BFGS更新：
\[H_1 = H_0 - \frac{H_0 s_0 s_0^T H_0}{s_0^T H_0 s_0} + \frac{y_0 y_0^T}{y_0^T s_0}. \]
计算得：
\(H_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} - \frac{1}{4} \begin{bmatrix} 4 & 0 \\ 0 & 0 \end{bmatrix} + \frac{1}{-8} \begin{bmatrix} 16 & -16 \\ -16 & 16 \end{bmatrix} = \begin{bmatrix} 0 & 2 \\ 2 & 1 \end{bmatrix}\)。
3.3 构建QP子问题
\[\min_d \frac{1}{2} d^T H_1 d + [0, -4] d = \frac{1}{2} (2d_1 d_2 + d_2^2) - 4d_2 \]
\[\text{s.t. } d_1 + d_2 + 0 \leq 0 \quad (\text{因 } g_1 \text{活跃}), \]
\[-d_1 + 2d_2 - 5 \leq 0, \]
\[d_1 \geq -2, \quad d_2 \geq 0. \]
3.4 求解QP子问题
约束 \(d_1 + d_2 \leq 0\) 和 \(d_2 \geq 0\) 结合得 \(d_1 \leq -d_2 \leq 0\)。
目标函数简化后关于 \(d_2\) 凸，最小值在 \(d_2 = 0\) 处，代入得 \(d_1 = 0\)。
解为 \(d^{(1)} = (0, 0)\)，说明当前点已是QP子问题的稳定点。
4. 收敛判断
在 \(x^{(1)} = (2, 0)\) 处，检查原问题的KKT条件：
- 梯度条件：\(\nabla f + \lambda_1 \nabla g_1 + \lambda_2 \nabla g_2 = 0\)
\(\Rightarrow [0, -4] + \lambda_1 [1, 1] + \lambda_2 [-1, 2] = 0\)。
解得 \(\lambda_1 = 4, \lambda_2 = 0\)（非负，且对应约束 \(g_2\) 非活跃）。 - 互补松弛条件满足。
因此 \(x^{(1)}\) 是原问题的KKT点，且由于问题凸，它就是全局最优解。
5. 结果
最优解：\(x^* = (2, 0)\)，最优值：\(f(x^*) = -4\)。
改进的SQP通过两次迭代收敛，BFGS更新提升了Hessian近似精度，线搜索确保了稳定性。