非线性规划中的序列二次规划-近似Hessian-积极集-信赖域-乘子法混合算法基础题
题目描述
考虑如下非线性规划问题：
\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) = 0, \quad i \in \mathcal{E} \\ & c_i(x) \leq 0, \quad i \in \mathcal{I} \end{aligned} \]
其中：
- \(f(x)\) 是二次连续可微的目标函数，
- \(c_i(x)\) 是二次连续可微的约束函数，
- \(\mathcal{E}\) 和 \(\mathcal{I}\) 分别表示等式和不等式约束的索引集。
本题目要求使用序列二次规划（SQP） 框架，但在每个子问题中采用近似Hessian矩阵（例如BFGS或SR1拟牛顿更新），结合积极集策略识别有效约束，并使用信赖域方法控制步长，同时引入乘子法处理约束违反。最终构造一个混合算法，并应用于以下具体实例：
\[\begin{aligned} \min_{x_1, x_2} \quad & f(x) = (x_1 - 1)^2 + (x_2 - 2.5)^2 \\ \text{s.t.} \quad & x_1 - 2x_2 + 2 \geq 0 \\ & -x_1 - 2x_2 + 6 \geq 0 \\ & -x_1 + 2x_2 + 2 \geq 0 \\ & x_1 \geq 0, \quad x_2 \geq 0 \end{aligned} \]
解题过程循序渐进讲解
步骤1：理解算法框架
序列二次规划（SQP）的核心思想是：在当前迭代点 \(x_k\) 处，构造一个二次规划（QP）子问题来近似原问题，通过求解该QP子问题得到搜索方向 \(p_k\)，然后沿该方向进行线搜索或信赖域步长更新。
本算法的特殊混合设计：
- 近似Hessian：由于精确计算Hessian矩阵计算量大，采用拟牛顿法（如BFGS）更新拉格朗日函数的Hessian近似矩阵 \(B_k\)。
- 积极集策略：在每个QP子问题中，只考虑可能起作用的约束（积极约束），减少计算规模。
- 信赖域：在求解QP子问题时添加信赖域约束 \(\|p\| \leq \Delta_k\)，控制步长以保证逼近质量。
- 乘子法思想：在目标函数中引入乘子项，将约束违反惩罚与拉格朗日函数结合，提升收敛稳定性。
步骤2：构造拉格朗日函数与近似QP子问题
原问题的拉格朗日函数为：
\[\mathcal{L}(x, \lambda) = f(x) + \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i c_i(x) \]
其中 \(\lambda_i\) 是拉格朗日乘子。
在迭代点 \(x_k\)，构造如下QP子问题：
\[\begin{aligned} \min_{p \in \mathbb{R}^n} \quad & \frac{1}{2} p^\top B_k p + \nabla f(x_k)^\top p \\ \text{s.t.} \quad & \nabla c_i(x_k)^\top p + c_i(x_k) = 0, \quad i \in \mathcal{E} \\ & \nabla c_i(x_k)^\top p + c_i(x_k) \leq 0, \quad i \in \mathcal{I} \\ & \|p\| \leq \Delta_k \end{aligned} \]
这里：
- \(B_k\) 是 \(\nabla_{xx}^2 \mathcal{L}(x_k, \lambda_k)\) 的近似（通过BFGS更新），
- \(\Delta_k > 0\) 是信赖域半径。
步骤3：积极集策略的引入
在每次迭代，根据当前点 \(x_k\) 和乘子估计 \(\lambda_k\) 确定积极集：
- 对于不等式约束 \(c_i(x) \leq 0\)，如果 \(c_i(x_k) \geq -\epsilon\) 或 \(\lambda_i > 0\)（\(\epsilon\) 是小正数，如 \(10^{-6}\)），则将其视为积极约束，否则暂时忽略。
- 在QP子问题中只保留积极约束和所有等式约束，从而降低问题规模。
步骤4：求解带信赖域的QP子问题
求解上述QP可得到候选步长 \(p_k\)。由于加入了信赖域约束 \(\|p\| \leq \Delta_k\)，该QP是一个带椭球约束的凸二次规划（当 \(B_k\) 正定时）。常用解法包括：
- 内点法 或 积极集法 结合投影梯度，处理信赖域约束。
- 实际中，可先忽略信赖域约束求解，如果解满足 \(\|p\| \leq \Delta_k\) 则接受；否则在信赖域边界上求解约化问题。
步骤5：接受准则与信赖域半径更新
定义实际下降量：
\[\text{ared}_k = f(x_k) - f(x_k + p_k) \]
预测下降量（基于QP模型）：
\[\text{pred}_k = -\left( \frac{1}{2} p_k^\top B_k p_k + \nabla f(x_k)^\top p_k \right) \]
计算比值：
\[\rho_k = \frac{\text{ared}_k}{\text{pred}_k} \]
更新信赖域半径：
\[\Delta_{k+1} = \begin{cases} 0.5 \Delta_k, & \text{if } \rho_k < 0.25 \\ \Delta_k, & \text{if } 0.25 \leq \rho_k \leq 0.75 \\ 2 \Delta_k, & \text{if } \rho_k > 0.75 \end{cases} \]
如果 \(\rho_k > \eta\)（例如 \(\eta = 10^{-4}\)），则接受步长：\(x_{k+1} = x_k + p_k\)；否则拒绝步长，保持 \(x_{k+1} = x_k\)，缩小信赖域重新求解。
步骤6：乘子更新与Hessian近似更新
- 乘子更新：求解QP子问题后得到乘子估计 \(\lambda_{k+1}^\text{QP}\)，可用以下方式平滑更新：
\[\lambda_{k+1} = \lambda_k + \alpha (\lambda_{k+1}^\text{QP} - \lambda_k) \]
其中 \(\alpha \in (0,1]\) 是松弛因子。
- BFGS更新：令 \(s_k = x_{k+1} - x_k\)，\(y_k = \nabla_x \mathcal{L}(x_{k+1}, \lambda_{k+1}) - \nabla_x \mathcal{L}(x_k, \lambda_{k+1})\)，更新公式为：
\[B_{k+1} = B_k - \frac{B_k s_k s_k^\top B_k}{s_k^\top B_k s_k} + \frac{y_k y_k^\top}{s_k^\top y_k} \]
要求 \(s_k^\top y_k > 0\) 以保证正定性，否则跳过本次更新。
步骤7：应用于给定例题
具体参数与初值设置：
- 初始点 \(x_0 = (2, 0)^\top\)，乘子初值 \(\lambda_0 = 0\)，\(B_0 = I\)（单位阵），\(\Delta_0 = 1\)。
- 积极集阈值 \(\epsilon = 10^{-6}\)，信赖域接受阈值 \(\eta = 10^{-4}\)。
迭代过程简述：
- 计算梯度 \(\nabla f = [2(x_1-1), 2(x_2-2.5)]^\top\)，约束函数值及梯度。
- 在 \(x_0 = (2,0)\) 处，约束 \(c_1 = 2 - 0 + 2 = 4 > 0\)，\(c_2 = -2 - 0 + 6 = 4 > 0\)，\(c_3 = -2 + 0 + 2 = 0\)，边界约束 \(x_1, x_2 \geq 0\) 都满足。积极集可包含 \(c_3\)（紧约束）。
- 构建QP子问题，求解得到 \(p_0\) 和乘子估计。
- 根据 \(\rho_0\) 决定是否接受步长，更新信赖域半径。
- 更新乘子，用BFGS更新 \(B_1\)。
- 重复至收敛（如 \(\|p_k\| < 10^{-6}\) 且约束违反小于 \(10^{-6}\)）。
最终结果：该问题的最优解为 \(x^* = (1.4, 1.7)^\top\)，最优值 \(f^* = 0.2\)。通过大约 5-6 次迭代可达到此解。
步骤8：算法总结与特点
该混合算法结合了：
- SQP 的快速局部收敛，
- 近似Hessian 降低计算成本，
- 积极集 减少子问题规模，
- 信赖域 增强全局收敛性，
- 乘子法 改善约束处理。
适用于中小规模、光滑的非线性规划问题，能稳定收敛到局部最优解。
练习思考
- 如果初始 Hessian 近似 \(B_0\) 不是单位阵，而是对角占优矩阵，对收敛速度有何影响？
- 在积极集识别中，如何调整阈值 \(\epsilon\) 以平衡可靠性与效率？
- 信赖域半径更新规则中，若将收缩因子从 0.5 改为 0.1，会对迭代过程产生什么影响？
如果需要，我可以进一步解释算法中任一环节的数学推导或实现细节。