序列凸规划（SCP）算法基础题
字数 2740 2025-12-15 13:12:20

序列凸规划（SCP）算法基础题

题目描述

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

\[\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \ldots, m \\ & Ax = b \end{aligned} \]

其中，目标函数 \(f(x)\) 和约束函数 \(g_i(x)\) 是光滑的，但可能是非凸的。\(A\) 是一个矩阵，\(b\) 是向量，描述线性等式约束。序列凸规划（Sequential Convex Programming, SCP）是一种迭代算法，其核心思想是：在每个迭代点，用一系列更容易处理的近似函数（通常是凸函数）来替代原问题中的非凸函数，构建一个近似子问题，求解这个凸子问题，并将其解作为下一个迭代点，逐步逼近原问题的最优解。

本题要求你实现一个基本的序列凸规划算法来解决一个特定的非凸优化问题，并理解其迭代收敛过程。

解题过程

我们将SCP算法的过程分解为几个清晰的步骤。为了具体，我们假设目标函数 \(f(x)\) 是二次非凸的，约束 \(g_i(x)\) 是凸的。但在SCP框架下，即使约束非凸，我们也可以构造凸近似。关键在于构造凸的近似子问题。

步骤1：问题简化与凸近似构造

  1. 问题原型：考虑一个简单但典型的非凸问题：

\[ \begin{aligned} \min_{x, y} \quad & f(x, y) = x^4 + y^4 - 10x^2 - 5y^2 + xy + 10 \\ \text{s.t.} \quad & g_1(x, y) = x^2 + y^2 - 25 \le 0 \\ & g_2(x, y) = (x-3)^2 + (y-2)^2 - 7 \le 0 \end{aligned} \]

这里 $f(x, y)$ 是四次函数，具有非凸的Hessian矩阵。约束是凸的二次不等式（因为Hessian矩阵正定或半正定）。
  1. 凸近似的关键：对于非凸目标 \(f(x)\)，我们在当前迭代点 \(x_k\) 附近构造一个凸的替代函数 \(\hat f_k(x)\)。一种常见且稳健的方法是在 \(x_k\) 处进行一阶泰勒展开，然后添加一个保持凸性的正则项：

\[ \hat f_k(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T P_k (x - x_k) \]

这里的矩阵 $P_k$ 需要是对称正定矩阵，以保证 $\hat f_k(x)$ 是凸的。最简单的选择是取 $P_k = \rho I$，其中 $\rho > 0$ 是一个足够大的常数，使得 $\hat f_k(x)$ 的Hessian $P_k$ 正定。这种方法也叫**凸保守近似**。更高级的方法可以根据 $f(x)$ 在 $x_k$ 处的Hessian矩阵 $\nabla^2 f(x_k)$ 进行修正，使其正定。
  1. 约束的处理：如果约束 \(g_i(x)\) 是非凸的，同样需要构造凸近似。本题中约束已经是凸的，所以我们可以直接用原约束 \(g_i(x) \le 0\) 作为子问题的约束。如果约束非凸，也需类似地用一阶展开加正定项进行凸化。

步骤2：构建并求解凸子问题

在第 \(k\) 次迭代，给定当前点 \(x_k\)，我们构建如下凸优化子问题：

\[\begin{aligned} \min_{x} \quad & \hat f_k(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} \rho \|x - x_k\|_2^2 \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \ldots, m \end{aligned} \]

注意：

  • \(\rho\) 是信赖域半径或正则化参数。它控制着 \(x\) 偏离 \(x_k\) 的程度，保证了近似只在 \(x_k\) 附近有效，同时也保证了子问题的严格凸性。
  • 这个子问题是一个带凸约束的凸二次规划（QP） 或二阶锥规划（SOCP）（如果约束是二阶锥形式）。对于凸QP，存在高效、可靠的求解器（如内点法、有效集法）。

我们需要求解这个凸子问题，得到其最优解，记作 \(x_{k+1}^*\)。

步骤3：接受迭代与更新

  1. 接受新点：在基础的SCP中，我们通常直接接受子问题的解作为下一个迭代点，即 \(x_{k+1} = x_{k+1}^*\)。
  2. 收敛性检查：计算连续两次迭代点的变化量 \(\|x_{k+1} - x_k\|\) 和/或目标函数值的变化 \(|f(x_{k+1}) - f(x_k)|\)。如果它们小于预设的容差（例如 \(10^{-6}\)），则认为算法已收敛，\(x_{k+1}\) 即为近似局部最优解。
  3. 参数调整（可选但重要）：参数 \(\rho\) 可以固定，也可以自适应调整。一种简单的自适应策略是：
    • 如果当前迭代目标函数下降量显著（例如 \(f(x_{k+1}) < f(x_k) - \epsilon\)），可以适当减小 \(\rho\)，允许下一步探索更大的范围。
    • 如果下降不理想甚至目标值上升，可以增大 \(\rho\)，使下一步的近似更加“保守”，搜索范围更靠近当前点。
    • 这类似于信赖域方法中信赖域半径的调整。

步骤4：算法流程总结

输入：初始点 x0，正则化参数 ρ > 0，容差 tol > 0
输出：近似最优解 x*
步骤：
1. 设置 k = 0。
2. 循环执行以下步骤直至收敛：
   a. 在当前点 x_k 处，计算梯度 ∇f(x_k)。
   b. 构造凸近似子问题（如上所示）。
   c. 使用凸优化求解器求解该子问题，得到解 x_{k+1}。
   d. 计算变化量 Δx = ||x_{k+1} - x_k||。
   e. 如果 Δx < tol，则跳出循环，令 x* = x_{k+1}。
   f. 否则，令 k = k + 1，准备下一次迭代。
3. 返回 x*。

核心思想与要点

  • 序列：通过一系列迭代逐步逼近。
  • 凸：每次迭代求解的子问题是一个凸优化问题，这保证了子问题可高效求解到全局最优。
  • 局部近似：由于使用了一阶泰勒展开，凸近似只在当前点 \(x_k\) 附近有效。正则化项 \(\frac{1}{2} \rho \|x - x_k\|_2^2\) 控制了“附近”的范围，保证了迭代的稳定性。
  • 与SQP的区别：序列二次规划（SQP）是构造二次目标+线性化约束的子问题。而SCP强调子问题的凸性，对目标函数和可能的非凸约束都进行凸化，而SQP的子问题不一定是凸的（如果原问题非凸，其拉格朗日函数的Hessian可能不定）。
  • 应用：SCP在机器人轨迹优化、控制、非凸几何规划等领域有广泛应用，因为它能将复杂的非凸问题转化为一系列可可靠求解的凸问题。

通过以上步骤，你就掌握了序列凸规划的基本原理和实现流程。对于更复杂的问题（如非凸约束），核心挑战在于如何设计出既能保持凸性，又能较好近似原函数的替代函数。

序列凸规划（SCP）算法基础题 题目描述 我们考虑如下形式的非线性规划问题： $$ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_ i(x) \le 0, \quad i = 1, \ldots, m \\ & Ax = b \end{aligned} $$ 其中，目标函数 $f(x)$ 和约束函数 $g_ i(x)$ 是光滑的，但可能是 非凸的 。$A$ 是一个矩阵，$b$ 是向量，描述线性等式约束。序列凸规划（Sequential Convex Programming, SCP）是一种迭代算法，其核心思想是：在每个迭代点，用一系列更容易处理的近似函数（通常是凸函数）来替代原问题中的非凸函数，构建一个近似子问题，求解这个凸子问题，并将其解作为下一个迭代点，逐步逼近原问题的最优解。 本题要求你实现一个基本的序列凸规划算法来解决一个特定的非凸优化问题，并理解其迭代收敛过程。 解题过程 我们将SCP算法的过程分解为几个清晰的步骤。为了具体，我们假设目标函数 $f(x)$ 是二次非凸的，约束 $g_ i(x)$ 是凸的。但在SCP框架下，即使约束非凸，我们也可以构造凸近似。关键在于构造 凸的近似子问题 。 步骤1：问题简化与凸近似构造 问题原型 ：考虑一个简单但典型的非凸问题： $$ \begin{aligned} \min_ {x, y} \quad & f(x, y) = x^4 + y^4 - 10x^2 - 5y^2 + xy + 10 \\ \text{s.t.} \quad & g_ 1(x, y) = x^2 + y^2 - 25 \le 0 \\ & g_ 2(x, y) = (x-3)^2 + (y-2)^2 - 7 \le 0 \end{aligned} $$ 这里 $f(x, y)$ 是四次函数，具有非凸的Hessian矩阵。约束是凸的二次不等式（因为Hessian矩阵正定或半正定）。 凸近似的关键 ：对于非凸目标 $f(x)$，我们在当前迭代点 $x_ k$ 附近构造一个凸的替代函数 $\hat f_ k(x)$。一种常见且稳健的方法是 在 $x_ k$ 处进行一阶泰勒展开，然后添加一个保持凸性的正则项 ： $$ \hat f_ k(x) = f(x_ k) + \nabla f(x_ k)^T (x - x_ k) + \frac{1}{2} (x - x_ k)^T P_ k (x - x_ k) $$ 这里的矩阵 $P_ k$ 需要是对称正定矩阵，以保证 $\hat f_ k(x)$ 是凸的。最简单的选择是取 $P_ k = \rho I$，其中 $\rho > 0$ 是一个足够大的常数，使得 $\hat f_ k(x)$ 的Hessian $P_ k$ 正定。这种方法也叫 凸保守近似 。更高级的方法可以根据 $f(x)$ 在 $x_ k$ 处的Hessian矩阵 $\nabla^2 f(x_ k)$ 进行修正，使其正定。 约束的处理 ：如果约束 $g_ i(x)$ 是非凸的，同样需要构造凸近似。本题中约束已经是凸的，所以我们可以直接用原约束 $g_ i(x) \le 0$ 作为子问题的约束。如果约束非凸，也需类似地用一阶展开加正定项进行凸化。 步骤2：构建并求解凸子问题 在第 $k$ 次迭代，给定当前点 $x_ k$，我们构建如下凸优化子问题： $$ \begin{aligned} \min_ {x} \quad & \hat f_ k(x) = f(x_ k) + \nabla f(x_ k)^T (x - x_ k) + \frac{1}{2} \rho \|x - x_ k\|_ 2^2 \\ \text{s.t.} \quad & g_ i(x) \le 0, \quad i = 1, \ldots, m \end{aligned} $$ 注意： $\rho$ 是 信赖域半径 或 正则化参数 。它控制着 $x$ 偏离 $x_ k$ 的程度，保证了近似只在 $x_ k$ 附近有效，同时也保证了子问题的严格凸性。 这个子问题是一个 带凸约束的凸二次规划（QP） 或 二阶锥规划（SOCP） （如果约束是二阶锥形式）。对于凸QP，存在高效、可靠的求解器（如内点法、有效集法）。 我们需要求解这个凸子问题，得到其最优解，记作 $x_ {k+1}^* $。 步骤3：接受迭代与更新 接受新点 ：在基础的SCP中，我们通常直接接受子问题的解作为下一个迭代点，即 $x_ {k+1} = x_ {k+1}^* $。 收敛性检查 ：计算连续两次迭代点的变化量 $\|x_ {k+1} - x_ k\|$ 和/或目标函数值的变化 $|f(x_ {k+1}) - f(x_ k)|$。如果它们小于预设的容差（例如 $10^{-6}$），则认为算法已收敛，$x_ {k+1}$ 即为近似局部最优解。 参数调整（可选但重要） ：参数 $\rho$ 可以固定，也可以自适应调整。一种简单的自适应策略是： 如果当前迭代目标函数下降量显著（例如 $f(x_ {k+1}) < f(x_ k) - \epsilon$），可以适当减小 $\rho$，允许下一步探索更大的范围。 如果下降不理想甚至目标值上升，可以增大 $\rho$，使下一步的近似更加“保守”，搜索范围更靠近当前点。 这类似于信赖域方法中信赖域半径的调整。 步骤4：算法流程总结 核心思想与要点 序列 ：通过一系列迭代逐步逼近。 凸 ：每次迭代求解的子问题是一个凸优化问题，这保证了子问题可高效求解到全局最优。 局部近似 ：由于使用了一阶泰勒展开，凸近似只在当前点 $x_ k$ 附近有效。正则化项 $\frac{1}{2} \rho \|x - x_ k\|_ 2^2$ 控制了“附近”的范围，保证了迭代的稳定性。 与SQP的区别 ：序列二次规划（SQP）是构造二次目标+线性化约束的子问题。而SCP强调 子问题的凸性 ，对目标函数和可能的非凸约束都进行凸化，而SQP的子问题不一定是凸的（如果原问题非凸，其拉格朗日函数的Hessian可能不定）。 应用 ：SCP在机器人轨迹优化、控制、非凸几何规划等领域有广泛应用，因为它能将复杂的非凸问题转化为一系列可可靠求解的凸问题。 通过以上步骤，你就掌握了序列凸规划的基本原理和实现流程。对于更复杂的问题（如非凸约束），核心挑战在于如何设计出既能保持凸性，又能较好近似原函数的替代函数。