序列凸规划(Sequential Convex Programming, SCP)在非凸约束二次规划中的应用进阶题

字数 5170 2025-12-14 10:57:09

序列凸规划(Sequential Convex Programming, SCP)在非凸约束二次规划中的应用进阶题

题目描述

考虑一个非凸约束二次规划（Nonconvex Quadratically Constrained Program, NCQCP）问题。目标函数为二次型，但可能非凸（即Hessian矩阵非正定），同时包含非凸二次约束。具体问题形式如下：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) = \frac{1}{2} x^T P x + q^T x \\ \text{s.t.} \quad & g_i(x) = \frac{1}{2} x^T A_i x + b_i^T x + c_i \leq 0, \quad i = 1, \dots, m, \\ & l \leq x \leq u, \end{aligned} \]

其中，矩阵 $P, A_i \in \mathbb{R}^{n \times n}$ 为对称矩阵，但不一定是半正定的（即可能存在负特征值，导致目标函数或约束非凸）。向量 $q, b_i \in \mathbb{R}^n$，标量 $c_i \in \mathbb{R}$，以及 $l, u \in \mathbb{R}^n$ 为变量上下界。假设函数 $f$ 和 $g_i$ 是二次连续可微的。

你的任务是：运用序列凸规划（SCP）的核心思想，通过构造一系列凸近似子问题来逐步逼近原问题的局部最优解。你需要设计具体的凸近似方法（如基于一阶泰勒展开的线性化，或基于凸上/下界函数的构造），确保每个子问题是凸规划（通常是凸二次规划或二阶锥规划），从而可以用内点法等高效求解。请详细推导算法步骤，并讨论算法收敛的关键条件。

解题过程

1. 理解问题难点

原问题是非凸的，因为目标函数 $f(x)$ 的 Hessian 矩阵 $P$ 可能不定，且约束 $g_i(x)$ 的 Hessian 矩阵 $A_i$ 也可能不定。直接求解这样的非凸问题通常是 NP-hard 的。SCP 的核心思想是：在每次迭代点 $x_k$ 处，用一个“更容易求解”的凸优化子问题来近似原问题，求解该凸子问题得到下一步迭代点 $x_{k+1}$，如此反复直至收敛。关键是如何构造凸近似，既保证子问题的凸性，又能使序列收敛到原问题的一个稳定点（通常是局部极小点）。

2. 构造凸近似子问题

我们采用一种常见且有效的凸近似策略：在非凸二次函数中，将不定矩阵分解为半正定部分和负定部分，然后对负定部分进行线性化。

具体来说，对任意对称矩阵 $M$，可以进行特征值分解，得到：

\[M = M_+ + M_-, \]

其中 $M_+ \succeq 0$（半正定部分），$M_- \preceq 0$（负半定部分）。一种实用的分解是：令 $M_+ = M + \rho I$，$M_- = -\rho I$，其中 $\rho \geq -\lambda_{\min}(M)$ 确保 $M_+ \succeq 0$，但这需要特征值计算。更简便的做法是：利用矩阵 $M$ 的谱分解，但计算量大。另一种常用方法是：对非凸二次项进行一阶泰勒展开，并添加一个正则项（trust region 或 penalty）来控制逼近误差，从而得到一个凸的二次上界或下界。

这里我们采用凸上界近似（适用于最小化问题，我们希望目标函数近似值是原目标的上界，以保证迭代下降）：

对于目标函数 $f(x)$，在当前点 $x_k$ 处，构造：

\[\tilde{f}(x; x_k) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T Q_k (x - x_k), \]

其中 $Q_k \succeq 0$ 是一个凸近似矩阵，通常取 $Q_k = \max(0, P)$（即将 $P$ 的负特征值置零）或 $Q_k = P + \rho I$ 且选择 $\rho$ 使得 $Q_k \succeq 0$。更鲁棒的做法是取 $Q_k = \gamma I$，其中 $\gamma > 0$ 足够大，使得 $Q_k$ 正定，这实际上就是梯度方法加二次正则。

对于约束 $g_i(x)$，我们同样构造凸上界（因为约束是 $\leq 0$，上界更严格）：

\[\tilde{g}_i(x; x_k) = g_i(x_k) + \nabla g_i(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T B_{i,k} (x - x_k) \leq 0, \]

其中 $B_{i,k} \succeq 0$ 是对 $A_i$ 的凸近似，例如取 $B_{i,k} = \max(0, A_i)$（半正定部分）或 $B_{i,k} = A_i + \sigma_i I$ 且选择 $\sigma_i \geq -\lambda_{\min}(A_i)$。

3. 设计具体的凸子问题形式

在每一步迭代 $k$，给定当前点 $x_k$，我们求解如下凸优化子问题（通常是一个凸二次约束二次规划，若 $Q_k, B_{i,k}$ 为半正定矩阵，则该问题是凸的）：

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & \tilde{f}(x; x_k) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T Q_k (x - x_k) \\ \text{s.t.} \quad & \tilde{g}_i(x; x_k) = g_i(x_k) + \nabla g_i(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T B_{i,k} (x - x_k) \leq 0, \\ & l \leq x \leq u. \end{aligned} \tag{1} \]

其中梯度为：

\[\nabla f(x_k) = P x_k + q, \quad \nabla g_i(x_k) = A_i x_k + b_i. \]

矩阵 $Q_k$ 和 $B_{i,k}$ 的选择至关重要，必须保证子问题凸且可行，同时逼近原问题。常用选择：

$Q_k = \max(0, P)$（即 $P$ 的正特征值部分），但计算需要特征值分解。
更简单实用的选择：取 $Q_k = \lambda_{\max}(P) I$（即最大特征值乘以单位阵），这能确保 $f(x) \leq \tilde{f}(x; x_k)$（因为 $P \preceq \lambda_{\max}(P) I$），从而子问题目标函数是原目标的上界，有利于保证下降性。类似地，对约束矩阵 $A_i$，可取 $B_{i,k} = \max(0, \lambda_{\max}(A_i)) I$ 或更保守的 $B_{i,k} = \sigma_i I$ 且 $\sigma_i \geq \max(0, \lambda_{\max}(A_i))$。

4. 算法迭代步骤

给定初始点 $x_0$（需满足原始约束，或至少子问题初始可行），容忍误差 $\epsilon > 0$，最大迭代次数 $K$。

第1步：初始化
设 $k = 0$，选择初始点 $x_0$（可通过求解一个凸松弛或可行性问题得到）。选择凸近似矩阵 $Q_k, B_{i,k}$ 的构造方式（例如使用特征值界或固定正定矩阵）。

第2步：构造凸子问题
在当前点 $x_k$，计算梯度 $\nabla f(x_k)$, $\nabla g_i(x_k)$，并确定 $Q_k, B_{i,k}$。

简单策略：设 $Q_k = \gamma I$，其中 $\gamma \geq \max(0, \lambda_{\max}(P))$；设 $B_{i,k} = \sigma_i I$，其中 $\sigma_i \geq \max(0, \lambda_{\max}(A_i))$。
自适应策略：可根据迭代动态调整 $\gamma, \sigma_i$ 以改善收敛速度。

第3步：求解凸子问题
求解凸规划问题 (1)。由于目标函数是凸二次，约束是凸二次不等式加框约束，该问题是一个凸二次约束二次规划（QCQP），可用内点法（如IPOPT、MOSEK）或序列二次规划（若转化为二阶锥形式）高效求解。得到解 $x_{k+1}$。

第4步：检查收敛
计算连续迭代点的变化量 $\|x_{k+1} - x_k\|$ 和目标函数变化 $|f(x_{k+1}) - f(x_k)|$。若小于容忍误差 $\epsilon$，则停止，输出 $x_{k+1}$ 作为近似局部最优解。否则，令 $k := k+1$，返回第2步。

第5步：确保可行性（可行SCP）
如果子问题 (1) 对某些 $k$ 不可行，则需要放松约束或调整凸近似。常见做法是：在约束中添加松弛变量 $s_i \geq 0$，将约束改为 $\tilde{g}_i(x; x_k) \leq s_i$，并在目标中加上惩罚项 $\mu \sum_i s_i$，其中 $\mu > 0$ 是惩罚参数。这样可保证子问题始终可行，并驱动 $s_i \to 0$ 以恢复原约束。

5. 收敛性讨论

SCP 算法收敛的关键条件包括：

凸近似的精确性：近似函数 $\tilde{f}, \tilde{g}_i$ 应在 $x_k$ 处与原函数有一阶一致性，即函数值和梯度匹配：$\tilde{f}(x_k; x_k) = f(x_k)$，$\nabla \tilde{f}(x_k; x_k) = \nabla f(x_k)$，对约束同理。这保证了子问题在 $x_k$ 处与原问题局部等价。
凸上界性质：若选择 $Q_k, B_{i,k}$ 使得 $\tilde{f}(x; x_k) \geq f(x)$ 且 $\tilde{g}_i(x; x_k) \geq g_i(x)$ 对所有 $x$ 成立，则子问题的最优值给出了原问题目标的一个上界，迭代可能单调下降。但实际中，我们更关注稳定点收敛。
子问题可行性与稳定性：需保证子问题可行且解序列有界。通过添加松弛变量或控制信赖域半径可增强鲁棒性。
收敛定理：在适当条件下（如近似矩阵一致正定、约束规范满足），SCP 产生的序列 $\{x_k\}$ 的任何极限点都是原问题的稳定点（即满足 KKT 条件）。证明思路：由于子问题凸，其解 $x_{k+1}$ 满足子问题的 KKT 条件；当 $x_{k+1} \to x_k$ 时，该条件逼近原问题的 KKT 条件。

6. 算法变体与扩展

信赖域型 SCP：在子问题中添加信赖域约束 $\|x - x_k\| \leq \Delta_k$，控制步长以保证近似精度，并根据实际下降量与预测下降量的比率调整 $\Delta_k$。
逐步凸近似（Successive Convex Approximation, SCA）：与 SCP 类似，但更常用于非凸约束的通信、信号处理问题，通常采用更简单的凸近似（如线性化非凸部分）。
处理非凸目标：若目标非凸，也可用类似方法线性化非凸部分并添加正则项，形成凸子问题。

总结：序列凸规划通过将非凸问题分解为一系列凸子问题，利用凸优化的高效算法求解，是处理非凸二次规划等结构化非凸问题的有力工具。关键是通过适当的凸近似保持局部一致性和可行性，从而确保收敛到局部最优点。

序列凸规划(Sequential Convex Programming, SCP)在非凸约束二次规划中的应用进阶题题目描述考虑一个非凸约束二次规划（Nonconvex Quadratically Constrained Program, NCQCP）问题。目标函数为二次型，但可能非凸（即Hessian矩阵非正定），同时包含非凸二次约束。具体问题形式如下： $$ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) = \frac{1}{2} x^T P x + q^T x \\ \text{s.t.} \quad & g_ i(x) = \frac{1}{2} x^T A_ i x + b_ i^T x + c_ i \leq 0, \quad i = 1, \dots, m, \\ & l \leq x \leq u, \end{aligned} $$ 其中，矩阵 $P, A_ i \in \mathbb{R}^{n \times n}$ 为对称矩阵，但不一定是半正定的（即可能存在负特征值，导致目标函数或约束非凸）。向量 $q, b_ i \in \mathbb{R}^n$，标量 $c_ i \in \mathbb{R}$，以及 $l, u \in \mathbb{R}^n$ 为变量上下界。假设函数 $f$ 和 $g_ i$ 是二次连续可微的。你的任务是：运用序列凸规划（SCP）的核心思想，通过构造一系列凸近似子问题来逐步逼近原问题的局部最优解。你需要设计具体的凸近似方法（如基于一阶泰勒展开的线性化，或基于凸上/下界函数的构造），确保每个子问题是凸规划（通常是凸二次规划或二阶锥规划），从而可以用内点法等高效求解。请详细推导算法步骤，并讨论算法收敛的关键条件。解题过程 1. 理解问题难点原问题是非凸的，因为目标函数 $f(x)$ 的 Hessian 矩阵 $P$ 可能不定，且约束 $g_ i(x)$ 的 Hessian 矩阵 $A_ i$ 也可能不定。直接求解这样的非凸问题通常是 NP-hard 的。SCP 的核心思想是：在每次迭代点 $x_ k$ 处，用一个“更容易求解”的凸优化子问题来近似原问题，求解该凸子问题得到下一步迭代点 $x_ {k+1}$，如此反复直至收敛。关键是如何构造凸近似，既保证子问题的凸性，又能使序列收敛到原问题的一个稳定点（通常是局部极小点）。 2. 构造凸近似子问题我们采用一种常见且有效的凸近似策略：在非凸二次函数中，将不定矩阵分解为半正定部分和负定部分，然后对负定部分进行线性化。具体来说，对任意对称矩阵 $M$，可以进行特征值分解，得到： $$ M = M_ + + M_ -, $$ 其中 $M_ + \succeq 0$（半正定部分），$M_ - \preceq 0$（负半定部分）。一种实用的分解是：令 $M_ + = M + \rho I$，$M_ - = -\rho I$，其中 $\rho \geq -\lambda_ {\min}(M)$ 确保 $M_ + \succeq 0$，但这需要特征值计算。更简便的做法是：利用矩阵 $M$ 的谱分解，但计算量大。另一种常用方法是：对非凸二次项进行一阶泰勒展开，并添加一个正则项（trust region 或 penalty）来控制逼近误差，从而得到一个凸的二次上界或下界。这里我们采用凸上界近似（适用于最小化问题，我们希望目标函数近似值是原目标的上界，以保证迭代下降）：对于目标函数 $f(x)$，在当前点 $x_ k$ 处，构造： $$ \tilde{f}(x; x_ k) = f(x_ k) + \nabla f(x_ k)^T (x - x_ k) + \frac{1}{2} (x - x_ k)^T Q_ k (x - x_ k), $$ 其中 $Q_ k \succeq 0$ 是一个凸近似矩阵，通常取 $Q_ k = \max(0, P)$（即将 $P$ 的负特征值置零）或 $Q_ k = P + \rho I$ 且选择 $\rho$ 使得 $Q_ k \succeq 0$。更鲁棒的做法是取 $Q_ k = \gamma I$，其中 $\gamma > 0$ 足够大，使得 $Q_ k$ 正定，这实际上就是梯度方法加二次正则。对于约束 $g_ i(x)$，我们同样构造凸上界（因为约束是 $\leq 0$，上界更严格）： $$ \tilde{g} i(x; x_ k) = g_ i(x_ k) + \nabla g_ i(x_ k)^T (x - x_ k) + \frac{1}{2} (x - x_ k)^T B {i,k} (x - x_ k) \leq 0, $$ 其中 $B_ {i,k} \succeq 0$ 是对 $A_ i$ 的凸近似，例如取 $B_ {i,k} = \max(0, A_ i)$（半正定部分）或 $B_ {i,k} = A_ i + \sigma_ i I$ 且选择 $\sigma_ i \geq -\lambda_ {\min}(A_ i)$。 3. 设计具体的凸子问题形式在每一步迭代 $k$，给定当前点 $x_ k$，我们求解如下凸优化子问题（通常是一个凸二次约束二次规划，若 $Q_ k, B_ {i,k}$ 为半正定矩阵，则该问题是凸的）： $$ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & \tilde{f}(x; x_ k) = f(x_ k) + \nabla f(x_ k)^T (x - x_ k) + \frac{1}{2} (x - x_ k)^T Q_ k (x - x_ k) \\ \text{s.t.} \quad & \tilde{g} i(x; x_ k) = g_ i(x_ k) + \nabla g_ i(x_ k)^T (x - x_ k) + \frac{1}{2} (x - x_ k)^T B {i,k} (x - x_ k) \leq 0, \\ & l \leq x \leq u. \end{aligned} \tag{1} $$ 其中梯度为： $$ \nabla f(x_ k) = P x_ k + q, \quad \nabla g_ i(x_ k) = A_ i x_ k + b_ i. $$ 矩阵 $Q_ k$ 和 $B_ {i,k}$ 的选择至关重要，必须保证子问题凸且可行，同时逼近原问题。常用选择： $Q_ k = \max(0, P)$（即 $P$ 的正特征值部分），但计算需要特征值分解。更简单实用的选择：取 $Q_ k = \lambda_ {\max}(P) I$（即最大特征值乘以单位阵），这能确保 $f(x) \leq \tilde{f}(x; x_ k)$（因为 $P \preceq \lambda_ {\max}(P) I$），从而子问题目标函数是原目标的上界，有利于保证下降性。类似地，对约束矩阵 $A_ i$，可取 $B_ {i,k} = \max(0, \lambda_ {\max}(A_ i)) I$ 或更保守的 $B_ {i,k} = \sigma_ i I$ 且 $\sigma_ i \geq \max(0, \lambda_ {\max}(A_ i))$。 4. 算法迭代步骤给定初始点 $x_ 0$（需满足原始约束，或至少子问题初始可行），容忍误差 $\epsilon > 0$，最大迭代次数 $K$。第1步：初始化设 $k = 0$，选择初始点 $x_ 0$（可通过求解一个凸松弛或可行性问题得到）。选择凸近似矩阵 $Q_ k, B_ {i,k}$ 的构造方式（例如使用特征值界或固定正定矩阵）。第2步：构造凸子问题在当前点 $x_ k$，计算梯度 $\nabla f(x_ k)$, $\nabla g_ i(x_ k)$，并确定 $Q_ k, B_ {i,k}$。简单策略：设 $Q_ k = \gamma I$，其中 $\gamma \geq \max(0, \lambda_ {\max}(P))$；设 $B_ {i,k} = \sigma_ i I$，其中 $\sigma_ i \geq \max(0, \lambda_ {\max}(A_ i))$。自适应策略：可根据迭代动态调整 $\gamma, \sigma_ i$ 以改善收敛速度。第3步：求解凸子问题求解凸规划问题 (1)。由于目标函数是凸二次，约束是凸二次不等式加框约束，该问题是一个凸二次约束二次规划（QCQP），可用内点法（如IPOPT、MOSEK）或序列二次规划（若转化为二阶锥形式）高效求解。得到解 $x_ {k+1}$。第4步：检查收敛计算连续迭代点的变化量 $\|x_ {k+1} - x_ k\|$ 和目标函数变化 $|f(x_ {k+1}) - f(x_ k)|$。若小于容忍误差 $\epsilon$，则停止，输出 $x_ {k+1}$ 作为近似局部最优解。否则，令 $k := k+1$，返回第2步。第5步：确保可行性（可行SCP）如果子问题 (1) 对某些 $k$ 不可行，则需要放松约束或调整凸近似。常见做法是：在约束中添加松弛变量 $s_ i \geq 0$，将约束改为 $\tilde{g}_ i(x; x_ k) \leq s_ i$，并在目标中加上惩罚项 $\mu \sum_ i s_ i$，其中 $\mu > 0$ 是惩罚参数。这样可保证子问题始终可行，并驱动 $s_ i \to 0$ 以恢复原约束。 5. 收敛性讨论 SCP 算法收敛的关键条件包括：凸近似的精确性：近似函数 $\tilde{f}, \tilde{g}_ i$ 应在 $x_ k$ 处与原函数有一阶一致性，即函数值和梯度匹配：$\tilde{f}(x_ k; x_ k) = f(x_ k)$，$\nabla \tilde{f}(x_ k; x_ k) = \nabla f(x_ k)$，对约束同理。这保证了子问题在 $x_ k$ 处与原问题局部等价。凸上界性质：若选择 $Q_ k, B_ {i,k}$ 使得 $\tilde{f}(x; x_ k) \geq f(x)$ 且 $\tilde{g}_ i(x; x_ k) \geq g_ i(x)$ 对所有 $x$ 成立，则子问题的最优值给出了原问题目标的一个上界，迭代可能单调下降。但实际中，我们更关注稳定点收敛。子问题可行性与稳定性：需保证子问题可行且解序列有界。通过添加松弛变量或控制信赖域半径可增强鲁棒性。收敛定理：在适当条件下（如近似矩阵一致正定、约束规范满足），SCP 产生的序列 $\{x_ k\}$ 的任何极限点都是原问题的稳定点（即满足 KKT 条件）。证明思路：由于子问题凸，其解 $x_ {k+1}$ 满足子问题的 KKT 条件；当 $x_ {k+1} \to x_ k$ 时，该条件逼近原问题的 KKT 条件。 6. 算法变体与扩展信赖域型 SCP ：在子问题中添加信赖域约束 $\|x - x_ k\| \leq \Delta_ k$，控制步长以保证近似精度，并根据实际下降量与预测下降量的比率调整 $\Delta_ k$。逐步凸近似（Successive Convex Approximation, SCA）：与 SCP 类似，但更常用于非凸约束的通信、信号处理问题，通常采用更简单的凸近似（如线性化非凸部分）。处理非凸目标：若目标非凸，也可用类似方法线性化非凸部分并添加正则项，形成凸子问题。总结：序列凸规划通过将非凸问题分解为一系列凸子问题，利用凸优化的高效算法求解，是处理非凸二次规划等结构化非凸问题的有力工具。关键是通过适当的凸近似保持局部一致性和可行性，从而确保收敛到局部最优点。