非线性规划中的序列二次约束二次规划（SQCQP）算法进阶题
题目描述
考虑以下非线性规划问题：
最小化 \(f(x) = x_1^2 + 2x_2^2 + \sin(x_1 + x_2)\)
约束条件：
- \(g_1(x) = x_1^2 + x_2^2 - 4 \leq 0\) （非线性不等式约束）
- \(g_2(x) = x_1 - x_2 + 1 \leq 0\) （线性不等式约束）
- \(h(x) = x_1 + x_2 - 1 = 0\) （线性等式约束）
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。要求使用序列二次约束二次规划（SQCQP）算法求解该问题，重点说明如何通过迭代将非线性约束局部近似为二次约束，并保证收敛性。
解题过程
步骤1: 理解SQCQP算法的核心思想
SQCQP是序列二次规划（SQP）的扩展，适用于目标函数或约束高度非线性的问题。其核心思想是：
- 在每次迭代点 \(x_k\) 处，将原问题近似为一个二次约束二次规划（QCQP）子问题。
- 对于非线性约束 \(g_i(x) \leq 0\)，不仅像SQP那样线性化（一阶近似），还可能保留或添加二次项，以更好地捕捉曲率信息。
- 通过调节二次项的系数（如基于Hessian矩阵），控制近似精度和收敛速度。
步骤2: 构建当前迭代点的QCQP子问题
设当前迭代点为 \(x_k = (x_{1k}, x_{2k})\)。子问题的构造如下：
- 目标函数近似：
对 \(f(x)\) 进行二阶泰勒展开：
\[ \tilde{f}(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T H_k (x - x_k) \]
其中 \(H_k\) 是 \(f(x)\) 在 \(x_k\) 的Hessian矩阵或其拟牛顿近似（例如BFGS更新）。
本例中：
\[ \nabla f(x) = \begin{bmatrix} 2x_1 + \cos(x_1 + x_2) \\ 4x_2 + \cos(x_1 + x_2) \end{bmatrix}, \quad \nabla^2 f(x) = \begin{bmatrix} 2 - \sin(x_1 + x_2) & -\sin(x_1 + x_2) \\ -\sin(x_1 + x_2) & 4 - \sin(x_1 + x_2) \end{bmatrix}. \]
代入 \(x_k\) 计算 \(H_k\)。
- 非线性约束 \(g_1(x)\) 的近似：
- 一阶近似（线性化）： \(g_1(x) \approx g_1(x_k) + \nabla g_1(x_k)^T (x - x_k)\)。
- 但SQCQP可能保留二次项。例如，若 \(g_1(x)\) 本身是二次型（如本例），可直接保留原形式：
\[ \tilde{g}_1(x) = x_1^2 + x_2^2 - 4 \leq 0. \]
若 $ g_1(x) $ 非二次，可添加正则化项，如 $ \frac{\rho}{2} \|x - x_k\|^2 $（$ \rho > 0 $），使子问题更稳定。
- 线性约束 \(g_2(x)\) 和 \(h(x)\)：
直接保留原形式，因它们已是线性或二次型。
子问题形式：
\[\begin{aligned} \min_{d} \quad & \nabla f(x_k)^T d + \frac{1}{2} d^T H_k d \\ \text{s.t.} \quad & x_1^2 + x_2^2 - 4 \leq 0 \quad (\text{精确二次约束}) \\ & x_1 - x_2 + 1 \leq 0 \\ & x_1 + x_2 - 1 = 0 \\ & d = x - x_k \end{aligned} \]
注意：若迭代点 \(x_k\) 可行，子问题需保证 \(x_k\) 是可行点；否则需修复可行性。
步骤3: 求解QCQP子问题
QCQP是凸优化问题若 \(H_k\) 正定且二次约束凸（本例中 \(g_1(x)\) 的Hessian为 \(2I \succ 0\)，故凸）。
- 可用内点法、积极集法或专用QCQP求解器。
- 解得位移 \(d_k\) 和新迭代点 \(x_{k+1} = x_k + d_k\)。
步骤4: 收敛性判断与迭代更新
- 收敛准则：
- 检查KKT条件的残差：
\[ \|\nabla f(x_k) + \lambda_1 \nabla g_1(x_k) + \lambda_2 \nabla g_2(x_k) + \mu \nabla h(x_k)\| \leq \epsilon_1, \quad |\text{约束违反度}| \leq \epsilon_2. \]
- 或检查相邻迭代点变化 \(\|x_{k+1} - x_k\| \leq \epsilon\)。
-
Hessian更新：
若使用拟牛顿法（如BFGS），根据 \(x_{k+1}\) 和梯度信息更新 \(H_k\)。 -
保证全局收敛：
- 可能结合线搜索或信赖域法，调节步长以确保目标函数下降和约束满足。
步骤5: 算法流程总结
- 初始化 \(x_0\)，容忍度 \(\epsilon > 0\)，设置 \(k = 0\)。
- 循环直到收敛：
a. 计算 \(f(x_k), \nabla f(x_k), H_k\)。
b. 构造QCQP子问题（保留二次约束 \(g_1(x)\)，线性化其他项若需）。
c. 求解子问题得 \(d_k\)。
d. 更新 \(x_{k+1} = x_k + \alpha_k d_k\)（\(\alpha_k\) 通过线搜索确定）。
e. 更新 \(H_{k+1}\)（拟牛顿法）。
f. 检查收敛条件，若满足则退出。 - 输出最优解 \(x^*\)。
关键点说明
- SQCQP通过精确处理二次约束（如 \(g_1(x)\)）避免线性近似误差，尤其适用于曲率显著的约束。
- 若所有约束均为线性，SQCQP退化为标准SQP。
- 本例中 \(g_1(x)\) 是凸二次约束，子问题恒为凸QCQP，保证高效求解。