非线性规划中的信赖域反射-投影梯度-序列二次规划混合算法进阶题
题目描述：
考虑一个具有非线性等式约束和不等式约束的非凸优化问题：
\[\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} \\ & l \leq x \leq u \end{aligned} \]
其中，\(f: \mathbb{R}^n \to \mathbb{R}\) 是非线性目标函数，\(c_i: \mathbb{R}^n \to \mathbb{R}\) 是约束函数，\(\mathcal{E}\) 是等式约束集合，\(\mathcal{I}\) 是不等式约束集合，\(l, u \in \mathbb{R}^n\) 是变量的上下界。本题目要求结合信赖域反射法、投影梯度法和序列二次规划法三种方法，构建一种高效的混合算法来处理此类非凸、有界的约束优化问题。
解题步骤详解：
-
问题分析与算法框架设计
给定问题包含等式约束、不等式约束和变量边界，是非凸的，传统单一算法可能收敛困难。混合算法的设计思路是：- 利用投影梯度法快速满足变量边界约束 \(l \leq x \leq u\)。
- 在每次迭代中，构造一个近似的二次规划子问题，该子问题在当前点附近用一阶或二阶模型逼近原问题，并施加信赖域限制以保证逼近质量。
- 通过信赖域反射法处理子问题的约束，特别是等式和不等式约束的可行性，并确保全局收敛性。
-
构建迭代格式与子问题
在第 \(k\) 次迭代，当前点为 \(x_k\)，信赖域半径为 \(\Delta_k > 0\)。首先，投影梯度步用于处理简单边界：计算梯度投影方向
\[ d_{\text{PG}} = P_{[l, u]}(x_k - \alpha_k \nabla f(x_k)) - x_k \]
其中 \(P_{[l,u]}\) 是到框约束 \([l,u]\) 的投影，\(\alpha_k\) 是通过线搜索（如Armijo准则）确定的步长。这确保每次迭代后变量满足边界约束。
接着，构建一个局部二次规划子问题来近似等式和不等式约束：
\[ \begin{aligned} \min_{d \in \mathbb{R}^n} \quad & \nabla f(x_k)^\top d + \frac{1}{2} d^\top B_k d \\ \text{s.t.} \quad & c_i(x_k) + \nabla c_i(x_k)^\top d = 0, \quad i \in \mathcal{E} \\ & c_i(x_k) + \nabla c_i(x_k)^\top d \leq 0, \quad i \in \mathcal{I} \\ & \|d\| \leq \Delta_k \end{aligned} \]
其中 \(B_k\) 是Hessian矩阵 \(\nabla^2 f(x_k)\) 的近似（例如，由拟牛顿法如BFGS更新得到），或采用Gauss-Newton近似。信赖域约束 \(\|d\| \leq \Delta_k\) 控制步长大小，避免过度偏离局部模型的有效范围。
- 信赖域反射法解子问题
子问题是带线性化约束和信赖域约束的二次规划。信赖域反射法的核心思想是：- 首先，求解忽略信赖域约束的子问题，得到无约束步 \(d_{\text{QP}}\)。
- 如果 \(\|d_{\text{QP}}\| \leq \Delta_k\)，则接受 \(d_{\text{QP}}\) 作为试探步。
- 否则，需要将步长反射回信赖域内。一种常见做法是求解带信赖域约束的二次规划，这等价于求解一个带球约束的优化问题，可通过截断共轭梯度法（Steihaug-Toint方法）或双重优化方法实现。反射步 \(d_k\) 是以下问题的解：
\[ \min_{d} \nabla f(x_k)^\top d + \frac{1}{2} d^\top B_k d \quad \text{s.t.} \quad c_i(x_k) + \nabla c_i(x_k)^\top d = 0, \; i \in \mathcal{E}; \; c_i(x_k) + \nabla c_i(x_k)^\top d \leq 0, \; i \in \mathcal{I}; \; \|d\| \leq \Delta_k \]
实践中，常将线性化约束合并到目标函数中形成拉格朗日函数，然后对信赖域约束使用反射技巧：设当前迭代点为 $x_k$，试探步为 $d_{\text{try}}$，如果违反信赖域约束，则取反射步 $d_k = \frac{\Delta_k}{\|d_{\text{try}}\|} d_{\text{try}}$，然后重新检查约束可行性，必要时进行调整。
-
组合步与接受准则
计算总试探步 \(s_k = d_{\text{PG}} + \beta_k d_k\)，其中 \(\beta_k \in (0,1]\) 是组合系数，用于平衡投影梯度步和SQP步。通常初始时 \(\beta_k\) 较小，偏向投影梯度以快速满足边界，随着迭代逐渐增加以加强约束处理。定义实际下降量：
\[ \text{Ared}_k = f(x_k) - f(x_k + s_k) + \mu_k \left( \|c(x_k)\|_1 - \|c(x_k + s_k)\|_1 \right) \]
其中 \(\mu_k > 0\) 是罚参数，用于度量约束违反的减少。预测下降量（基于子问题模型）：
\[ \text{Pred}_k = -\left( \nabla f(x_k)^\top s_k + \frac{1}{2} s_k^\top B_k s_k \right) + \mu_k \left( \|c(x_k)\|_1 - \|c(x_k) + \nabla c(x_k)^\top s_k\|_1 \right) \]
计算比值 \(r_k = \frac{\text{Ared}_k}{\text{Pred}_k}\)。接受准则为：
- 如果 \(r_k \geq \eta_1 > 0\)（如 \(\eta_1 = 0.1\)），则接受试探步，更新 \(x_{k+1} = x_k + s_k\)，并可能增大信赖域半径 \(\Delta_{k+1} = \min(\gamma_1 \Delta_k, \Delta_{\max})\)。
- 否则，拒绝试探步，保持 \(x_{k+1} = x_k\)，减小信赖域半径 \(\Delta_{k+1} = \gamma_2 \Delta_k\)，其中 \(0 < \gamma_2 < 1 < \gamma_1\)。
-
更新与收敛判断
更新矩阵 \(B_k\)：如果步被接受，则用BFGS公式更新 \(B_k\) 以近似Hessian，确保 \(B_k\) 保持正定或半正定以适应非凸性。调整罚参数 \(\mu_k\)：如果约束违反未充分下降，则增大 \(\mu_k\) 以加强惩罚。收敛性检查：当满足以下条件之一时停止迭代：
- 梯度条件：\(\|\nabla L(x_k, \lambda_k)\| \leq \epsilon_1\)，其中 \(L\) 是拉格朗日函数，\(\lambda_k\) 是拉格朗日乘子估计。
- 约束违反：\(\|c(x_k)^+\| \leq \epsilon_2\)，\(c^+\) 表示不等式约束的违反量。
- 步长大小：\(\|s_k\| \leq \epsilon_3\) 且信赖域半径 \(\Delta_k \leq \epsilon_4\)。
-
算法流程总结
- 初始化：给定初始点 \(x_0\)，信赖域半径 \(\Delta_0\)，矩阵 \(B_0 = I\)，参数 \(\mu_0 > 0\)，容差 \(\epsilon\)。
- 循环直到收敛：
a. 投影梯度步：计算 \(d_{\text{PG}} = P_{[l,u]}(x_k - \alpha_k \nabla f(x_k)) - x_k\)，用线搜索确定 \(\alpha_k\)。
b. 构建SQP子问题：在当前点线性化约束，构造二次目标模型。
c. 信赖域反射法求解子问题：得到步 \(d_k\)，满足信赖域约束和线性化约束。
d. 组合步：计算 \(s_k = d_{\text{PG}} + \beta_k d_k\)，调节 \(\beta_k\)。
e. 评估接受性：计算实际下降与预测下降比值 \(r_k\)，按准则更新 \(x_{k+1}\) 和 \(\Delta_{k+1}\)。
f. 更新矩阵 \(B_k\) 和罚参数 \(\mu_k\)。 - 输出最优解 \(x^*\)。
此混合算法结合了投影梯度法的边界处理效率、信赖域反射法的全局收敛保证以及SQP法的快速局部收敛性，适用于具有复杂非凸约束的优化问题。通过调整组合系数和信赖域半径，能在不同阶段平衡全局探索与局部细化，提高求解成功率。