非线性规划中的可行序列凸规划（Feasible Sequential Convex Programming, FSCP）基础题

1. 题目描述

我们考虑如下形式的非线性规划（NLP）问题：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p, \\ & x^L \preceq x \preceq x^U. \end{aligned} \]

其中，\(f_0, f_i, h_j\) 是连续可微但可能为非凸的函数，\(x^L, x^U\) 是变量的上下界。

“可行序列凸规划”是“序列凸规划”的一种变体。与标准的SCP在每次迭代时求解一个可能不严格的凸子问题（可能产生不可行迭代点）不同，FSCP的核心思想是始终保持在可行域内，或者生成一个严格的可行性序列。它的一个常见策略是：在每一步，不仅对目标函数和约束进行凸近似，并且额外添加一个“信赖域”或“移动限界”约束，以确保子问题的解在当前迭代点附近，从而使得凸近似足够精确，并且新解是原问题的可行点（或至少比当前点更可行）。

你的任务：解释FSCP的基本原理，并针对上述一般形式的NLP问题，描述如何构建其凸子问题，以及如何通过迭代求解这些子问题来得到原问题的一个局部最优解。特别需要说明如何保证迭代序列的可行性（或渐近可行性）和收敛性。

2. 解题过程循序渐进讲解

步骤1：理解FSCP的核心动机与框架

在标准SCP中，我们在当前迭代点 \(x^k\) 处，对非凸函数 \(f_0, f_i, h_j\) 进行一阶泰勒展开（或某种凸上/下界近似），得到一个凸子问题（通常是线性规划LP、二次规划QP或二阶锥规划SOCP）。求解这个子问题得到下一步迭代点 \(x^{k+1}\)。然而，由于近似误差， \(x^{k+1}\) 可能不满足原问题的非凸约束，即“不可行”。虽然可以通过罚函数或过滤器处理，但这可能影响算法鲁棒性。

FSCP的目标是克服这点。它要求每次迭代产生的点 \(x^{k+1}\) 是原问题的可行点，或者至少是“更可行”的点。这样做的好处是：

• 算法产生的所有中间解都是可用的、物理上可实现的（在工程应用中很重要）。
• 收敛性分析有时更简单，因为目标函数值序列 \(\{f_0(x^k)\}\) 是单调下降的（如果子问题构造得当）。
• 可以避免因不可行点导致的数值不稳定。

FSCP的通用迭代框架如下：

1. 给定一个初始可行点 \(x^0\) （满足所有约束）。
2. 对于 \(k = 0, 1, 2, \dots\)：
   a. 在当前点 \(x^k\) 处，构造一个凸的、可行的局部近似子问题。
   b. 求解该子问题，得到位移 \(d^k = x^{k+1} - x^k\) （或直接得到 \(x^{k+1}\) ）。
   c. 确保 \(x^{k+1}\) 是原问题的可行点。
   d. 检查收敛条件（如位移大小、目标函数下降量、最优性条件残差）。

步骤2：构建凸可行子问题

FSCP的关键在于如何构造步骤2a中的子问题。我们以凸上界近似和信赖域约束为例。

假设在点 \(x^k\) 处，我们计算目标函数和约束函数的值及其梯度。

• 目标函数处理：对于非凸目标 \(f_0\)，我们用一个凸函数 \(\hat{f}_0^k(x)\) 在 \(x^k\) 附近局部上界它。常见选择是一阶泰勒展开加上一个正则项（使其成为凸函数，且是 \(f_0\) 的一个上界估计）：

\[ \hat{f}_0^k(x) = f_0(x^k) + \nabla f_0(x^k)^T (x - x^k) + \frac{1}{2} (x - x^k)^T P_0^k (x - x^k). \]

其中 \(P_0^k\) 是一个对称正定矩阵（例如 \(\sigma_0^k I\)， \(\sigma_0^k > 0\) 足够大），使得 \(\hat{f}_0^k(x)\) 是凸的，并且在 \(x^k\) 附近是 \(f_0(x)\) 的一个上界（或至少是保守近似）。

• 不等式约束处理：对于非凸不等式约束 \(f_i(x) \leq 0\)，我们构造一个凸上界近似 \(\hat{f}_i^k(x)\)，使得在 \(x^k\) 附近有 \(f_i(x) \leq \hat{f}_i^k(x)\)。这样，如果子问题中要求 \(\hat{f}_i^k(x) \leq 0\)，则能保证在原约束下可行（至少局部地）。一个标准做法是线性化并添加一个凸正则项：

\[ \hat{f}_i^k(x) = f_i(x^k) + \nabla f_i(x^k)^T (x - x^k) + \frac{1}{2} (x - x^k)^T P_i^k (x - x^k). \]

其中 \(P_i^k\) 对称正半定，以确保 \(\hat{f}_i^k\) 是凸的。通常为了简单，取 \(P_i^k = \sigma_i^k I\) 且 \(\sigma_i^k \geq 0\) 足够大，以保证 \(f_i(x) \leq \hat{f}_i^k(x)\) 在某个邻域内成立。

• 等式约束处理：等式约束必须是线性的（或至少其近似是线性的），否则凸子问题中一个非线性等式约束会破坏凸性。因此，我们对 \(h_j(x) = 0\) 进行线性化：

\[ \hat{h}_j^k(x) = h_j(x^k) + \nabla h_j(x^k)^T (x - x^k) = 0. \]

• 信赖域/移动限界约束：为了保证上述近似是精确的，并且新点 \(x^{k+1}\) 离 \(x^k\) 不太远，我们添加一个凸的信赖域约束。常用的是球约束或盒子约束：

\[ \| x - x^k \| \leq \Delta^k, \quad \text{或} \quad |x_l - x_l^k| \leq \delta_l^k, \ l=1,\dots,n. \]

其中 \(\Delta^k > 0\) 是信赖域半径，是算法的关键参数。

于是，在第 \(k\) 次迭代的凸可行子问题为：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & \hat{f}_0^k(x) \\ \text{s.t.} \quad & \hat{f}_i^k(x) \leq 0, \quad i = 1, \dots, m, \\ & \hat{h}_j^k(x) = 0, \quad j = 1, \dots, p, \\ & x^L \preceq x \preceq x^U, \\ & \| x - x^k \| \leq \Delta^k. \end{aligned} \]

步骤3：确保迭代可行性

FSCP之所以称为“可行”，是因为我们要求子问题的解 \(x^{k+1}\) 必须是原问题的可行点。如何保证这一点？

1. 初始点可行：算法从一个可行点 \(x^0\) 开始。

2. 保守近似与信赖域：通过选择足够大的凸正则项 \(P_i^k\) 和足够小的信赖域半径 \(\Delta^k\)，我们可以确保在 \(x^k\) 的邻域 \(\{ x : \|x - x^k\| \leq \Delta^k \}\) 内，近似不等式满足 \(f_i(x) \leq \hat{f}_i^k(x)\)。那么，如果子问题的解 \(x^{k+1}\) 满足 \(\hat{f}_i^k(x^{k+1}) \leq 0\) 且 \(x^{k+1}\) 在此邻域内，则必有 \(f_i(x^{k+1}) \leq 0\)。对于等式约束，线性化后 \(\hat{h}_j^k(x^{k+1}) = 0\) 不能保证 \(h_j(x^{k+1}) = 0\)，但我们可以通过放松线性化等式，例如将其变为不等式：\(|\hat{h}_j^k(x)| \leq \epsilon^k\)，并逐步缩小 \(\epsilon^k \to 0\)，或者将线性化等式作为子问题约束，然后通过投影或修复步骤将得到的 \(x^{k+1}\) 映射到原等式约束流形上（如果可能）。在基础FSCP中，通常假设等式约束是线性的，或者算法能处理一定的等式违反并通过迭代驱使其为零。

3. 可行性保持更新：求解子问题后，计算 \(x^{k+1}\)。需要验证 \(x^{k+1}\) 对原约束的可行性。如果可行，则接受该点，进入下一次迭代。如果不可行（可能因为近似不够精确或信赖域太大），则拒绝这个点，缩小信赖域半径 \(\Delta^k\)（例如 \(\Delta^{k+1} = \beta \Delta^k, \beta \in (0,1)\)），然后重新求解子问题（或在同一个迭代内用更小的信赖域重解）。

步骤4：信赖域半径的适应性调整

信赖域半径 \(\Delta^k\) 是控制近似精度和步长的关键。其调整类似于信赖域方法：

定义实际下降量：\(\text{ared}_k = f_0(x^k) - f_0(x^{k+1})\)。
定义预测下降量：\(\text{pred}_k = \hat{f}_0^k(x^k) - \hat{f}_0^k(x^{k+1})\)。

计算比值 \(\rho_k = \frac{\text{ared}_k}{\text{pred}_k}\)。

• 如果 \(\rho_k\) 接近1（例如 \(\rho_k > \eta_1\)，其中 \(0 < \eta_1 < 1\)），说明近似模型很好，可以尝试扩大信赖域：\(\Delta^{k+1} = \gamma_{\text{inc}} \Delta^k\)（\(\gamma_{\text{inc}} > 1\)）。
• 如果 \(\rho_k\) 很小（例如 \(\rho_k < \eta_2\)， \(0 < \eta_2 < \eta_1\)），说明近似模型较差，需要缩小信赖域：\(\Delta^{k+1} = \gamma_{\text{dec}} \Delta^k\)（\(0 < \gamma_{\text{dec}} < 1\)）。
• 否则，保持信赖域半径不变。

此外，如果子问题不可行或无解，也需缩小 \(\Delta^k\)。

步骤5：收敛性分析要点

FSCP的收敛性通常基于以下观察：

• 由于迭代点始终可行，目标函数序列 \(\{f_0(x^k)\}\) 是非递增的（如果每次子问题的解至少不差于当前点 \(x^k\)，而 \(x^k\) 是子问题的一个可行解，且子问题目标函数是 \(f_0\) 的一个局部上界，则通常有 \(f_0(x^{k+1}) \leq f_0(x^k)\)）。
• 在合适的正则项系数 \(\sigma_i^k\) 和信赖域半径 \(\Delta^k\) 的更新策略下，可以证明任何聚点都满足原问题的一阶必要最优性条件（如KKT条件）。
• 对于等式约束，可能需要额外技术处理线性化误差，例如采用“精确罚函数”将等式约束转化为不等式，或者在收敛时强制等式满足。

步骤6：算法伪代码

输入：初始可行点 $ x^0 $，初始信赖域半径 $ \Delta^0 > 0 $，参数 $ 0 < \eta_2 < \eta_1 < 1 $， $ 0 < \gamma_{\text{dec}} < 1 < \gamma_{\text{inc}} $，公差 $ \epsilon > 0 $。

k = 0
while 未收敛（例如 $ \|x^{k+1} - x^k\| > \epsilon $ 或 最优性条件未满足） do
    1. 在当前点 $ x^k $，计算梯度 $ \nabla f_0(x^k) $, $ \nabla f_i(x^k) $, $ \nabla h_j(x^k) $。
    2. 选择凸正则化矩阵 $ P_0^k, P_i^k $（例如标量 $ \sigma_0^k, \sigma_i^k $ 乘单位矩阵）。
    3. 构建凸子问题（如步骤2所述）。
    4. 求解该凸子问题，得到候选点 $ x_c $。
    5. 检查 $ x_c $ 对原问题约束的可行性：
        if $ x_c $ 可行（在一定公差内） then
            $ x^{k+1} = x_c $
            计算实际下降 ared_k 和预测下降 pred_k，得到比率 $ \rho_k $。
            根据 $ \rho_k $ 按步骤4更新 $ \Delta^{k+1} $。
        else
            $ x^{k+1} = x^k $ （拒绝步）
            $ \Delta^{k+1} = \gamma_{\text{dec}} \Delta^k $ （缩小信赖域）
        end if
    6. k = k + 1
end while
输出： $ x^k $ 作为局部最优解。

3. 总结

FSCP通过在每个迭代点求解一个局部凸近似子问题，并借助信赖域约束和凸上界近似，确保迭代点始终保持在可行域内（或渐近可行）。它结合了序列凸规划的高效和信赖域方法的稳健性，特别适用于需要中间解可行的工程优化问题。其核心挑战在于如何构造保守的凸近似以保证可行性，以及如何自适应地调整信赖域半径以平衡收敛速度和模型精度。