非线性规划中的序列凸规划（SCP）在非凸约束优化中的应用基础题
字数 3415 2025-12-13 00:46:18

非线性规划中的序列凸规划（SCP）在非凸约束优化中的应用基础题

题目描述

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

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

其中，目标函数 \(f(x)\) 和约束函数 \(g_i(x)\)、\(h_j(x)\) 均为光滑函数，但问题整体可能是非凸的，导致常规的凸优化方法无法直接应用。序列凸规划（Sequential Convex Programming, SCP）是一种迭代方法，通过在每一步构造并求解一个凸近似子问题来逐步逼近原问题的解。

本题要求：

  1. 详细说明SCP方法在非凸约束优化中的基本思路。
  2. 针对一个具体非凸优化问题，演示如何构造每一步的凸近似子问题。
  3. 给出SCP算法的完整步骤，并解释其收敛性条件。
  4. 通过一个简单数值例子（如二维非凸优化）演示SCP的迭代过程。

解题过程

1. 序列凸规划（SCP）的核心思想

SCP是一种局部近似方法，适用于目标函数和约束函数可微但非凸的问题。其核心思想是：

  • 在当前迭代点 \(x_k\) 处，对目标函数和约束函数进行一阶泰勒展开（或利用其他凸近似技巧），得到一个凸优化子问题。
  • 求解这个凸子问题，得到下一个迭代点 \(x_{k+1}\)。
  • 重复以上过程，直到满足收敛条件。

这种方法本质上是序列凸逼近，每一步求解的都是凸问题（如线性规划、二次规划、凸规划），计算效率较高。

2. 凸近似子问题的构造

假设在第 \(k\) 步，当前点为 \(x_k\)。我们需要构造一个凸函数来近似原非凸函数。常用方法如下：

  • 目标函数 \(f(x)\)：
    对 \(f(x)\) 在 \(x_k\) 处进行一阶泰勒展开：

\[ f(x) \approx f(x_k) + \nabla f(x_k)^T (x - x_k). \]

如果 \(f(x)\) 本身是凸函数，可直接用原函数；如果非凸，线性化后得到的是线性函数（凸）。

  • 不等式约束 \(g_i(x)\)：
    同样进行一阶线性化：

\[ g_i(x) \approx g_i(x_k) + \nabla g_i(x_k)^T (x - x_k) \leq 0. \]

线性函数是凸的，所以线性化后的约束是凸的。

  • 等式约束 \(h_j(x)\)：
    线性化：

\[ h_j(x) \approx h_j(x_k) + \nabla h_j(x_k)^T (x - x_k) = 0. \]

注意：直接线性化可能导致逼近不准确，尤其是当迭代点变化较大时。因此，SCP通常会添加一个信赖域约束或移动限界，限制每一步的变化范围：

\[\| x - x_k \|_\infty \leq \Delta_k, \]

其中 \(\Delta_k > 0\) 是信赖域半径，在迭代中可自适应调整。

于是，第 \(k\) 步的凸近似子问题为：

\[\begin{aligned} \min_{x} \quad & f(x_k) + \nabla f(x_k)^T (x - x_k) \\ \text{s.t.} \quad & g_i(x_k) + \nabla g_i(x_k)^T (x - x_k) \leq 0, \quad i=1,\dots,m, \\ & h_j(x_k) + \nabla h_j(x_k)^T (x - x_k) = 0, \quad j=1,\dots,p, \\ & \| x - x_k \|_\infty \leq \Delta_k. \end{aligned} \]

这是一个线性规划（LP）问题（如果目标函数是线性）或可转化为凸二次规划（如果添加二次正则项）。

3. SCP算法步骤

算法：序列凸规划（基础版）

  1. 初始化：选择初始点 \(x_0\)，初始信赖域半径 \(\Delta_0 > 0\)，容忍误差 \(\epsilon > 0\)，设置 \(k = 0\)。
  2. 构造凸子问题：在当前点 \(x_k\) 处线性化目标函数和约束，并添加信赖域约束 \(\| x - x_k \|_\infty \leq \Delta_k\)。
  3. 求解子问题：求解上述凸优化问题，得到解 \(x_{k+1}^*\)。
  4. 接受性检验：计算实际下降与预测下降的比值：

\[ \rho_k = \frac{\text{实际目标下降}}{\text{预测目标下降}} = \frac{f(x_k) - f(x_{k+1}^*)}{-\nabla f(x_k)^T (x_{k+1}^* - x_k)}. \]

  • 如果 \(\rho_k\) 较大（例如 \(\rho_k > \eta_1 = 0.1\)），则认为近似较好，接受新点：\(x_{k+1} = x_{k+1}^*\)。
  • 否则，拒绝新点，缩小信赖域半径 \(\Delta_{k+1} = \gamma \Delta_k\)（例如 \(\gamma = 0.5\)），返回步骤2重新求解。
  1. 更新信赖域半径：
    • 如果 \(\rho_k > \eta_2\)（例如 \(\eta_2 = 0.75\)），说明近似很好，可扩大信赖域：\(\Delta_{k+1} = \min(2\Delta_k, \Delta_{\max})\)。
    • 如果 \(\eta_1 \leq \rho_k \leq \eta_2\)，保持半径不变。
  2. 收敛判断：如果 \(\| x_{k+1} - x_k \| < \epsilon\) 且约束违反度足够小，则停止；否则令 \(k = k+1\)，返回步骤2。

收敛性条件：

  • 要求原问题满足一定的约束规范性（如MFCQ）。
  • 序列 \(\{x_k\}\) 的极限点通常是原问题的KKT点。
  • 信赖域机制保证算法在非凸区域也能稳定逼近。

4. 数值例子演示

考虑一个简单二维非凸问题：

\[\begin{aligned} \min_{x_1, x_2} \quad & f(x) = x_1^2 + x_2^2 - 0.5 \cos(4\pi x_1) - 0.5 \cos(4\pi x_2) \\ \text{s.t.} \quad & g(x) = x_1^2 + 2x_2^2 - 2 \leq 0, \\ & -1 \leq x_1, x_2 \leq 1. \end{aligned} \]

（注：目标函数是非凸的Rastrigin-like函数，约束是凸椭圆区域。）

迭代过程（简要）：

  1. 初始点 \(x_0 = (0.5, 0.5)\)，\(\Delta_0 = 0.3\)。
  2. 在 \(x_0\) 处线性化：
    • \(f(x) \approx f(x_0) + (2x_1 + 2\pi \sin(4\pi x_1)) (x_1-0.5) + (2x_2 + 2\pi \sin(4\pi x_2)) (x_2-0.5)\)。
    • 约束已凸，直接保留。
      求解线性规划子问题（带信赖域约束），得新点 \(x_1^*\)。
  3. 计算接受比率 \(\rho_0\)，若接受则更新点，调整信赖域半径。
  4. 重复直到收敛。通常经过10~20步迭代可接近局部最优解 \(x^* \approx (0,0)\)。

关键点总结

  • SCP通过序列凸逼近处理非凸问题，每一步是凸优化，计算高效。
  • 需要信赖域或移动限界控制近似误差，保证收敛。
  • 算法适用于目标/约束光滑但非凸的优化问题，是工程中常用的局部优化方法。
非线性规划中的序列凸规划（SCP）在非凸约束优化中的应用基础题 题目描述 考虑如下形式的非线性规划问题： \[ \begin{aligned} \min_ {x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_ i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_ j(x) = 0, \quad j = 1, \dots, p, \end{aligned} \] 其中，目标函数 \( f(x) \) 和约束函数 \( g_ i(x) \)、\( h_ j(x) \) 均为光滑函数，但问题整体可能是 非凸 的，导致常规的凸优化方法无法直接应用。序列凸规划（Sequential Convex Programming, SCP）是一种迭代方法，通过在每一步构造并求解一个凸近似子问题来逐步逼近原问题的解。 本题要求： 详细说明SCP方法在非凸约束优化中的基本思路。 针对一个具体非凸优化问题，演示如何构造每一步的凸近似子问题。 给出SCP算法的完整步骤，并解释其收敛性条件。 通过一个简单数值例子（如二维非凸优化）演示SCP的迭代过程。 解题过程 1. 序列凸规划（SCP）的核心思想 SCP是一种 局部近似方法 ，适用于目标函数和约束函数可微但非凸的问题。其核心思想是： 在当前迭代点 \( x_ k \) 处，对目标函数和约束函数进行 一阶泰勒展开 （或利用其他凸近似技巧），得到一个凸优化子问题。 求解这个凸子问题，得到下一个迭代点 \( x_ {k+1} \)。 重复以上过程，直到满足收敛条件。 这种方法本质上是 序列凸逼近 ，每一步求解的都是凸问题（如线性规划、二次规划、凸规划），计算效率较高。 2. 凸近似子问题的构造 假设在第 \( k \) 步，当前点为 \( x_ k \)。我们需要构造一个凸函数来近似原非凸函数。常用方法如下： 目标函数 \( f(x) \) ： 对 \( f(x) \) 在 \( x_ k \) 处进行一阶泰勒展开： \[ f(x) \approx f(x_ k) + \nabla f(x_ k)^T (x - x_ k). \] 如果 \( f(x) \) 本身是凸函数，可直接用原函数；如果非凸，线性化后得到的是线性函数（凸）。 不等式约束 \( g_ i(x) \) ： 同样进行一阶线性化： \[ g_ i(x) \approx g_ i(x_ k) + \nabla g_ i(x_ k)^T (x - x_ k) \leq 0. \] 线性函数是凸的，所以线性化后的约束是凸的。 等式约束 \( h_ j(x) \) ： 线性化： \[ h_ j(x) \approx h_ j(x_ k) + \nabla h_ j(x_ k)^T (x - x_ k) = 0. \] 注意 ：直接线性化可能导致逼近不准确，尤其是当迭代点变化较大时。因此，SCP通常会添加一个 信赖域约束 或 移动限界 ，限制每一步的变化范围： \[ \| x - x_ k \|_ \infty \leq \Delta_ k, \] 其中 \( \Delta_ k > 0 \) 是信赖域半径，在迭代中可自适应调整。 于是，第 \( k \) 步的凸近似子问题为： \[ \begin{aligned} \min_ {x} \quad & f(x_ k) + \nabla f(x_ k)^T (x - x_ k) \\ \text{s.t.} \quad & g_ i(x_ k) + \nabla g_ i(x_ k)^T (x - x_ k) \leq 0, \quad i=1,\dots,m, \\ & h_ j(x_ k) + \nabla h_ j(x_ k)^T (x - x_ k) = 0, \quad j=1,\dots,p, \\ & \| x - x_ k \|_ \infty \leq \Delta_ k. \end{aligned} \] 这是一个 线性规划 （LP）问题（如果目标函数是线性）或可转化为凸二次规划（如果添加二次正则项）。 3. SCP算法步骤 算法：序列凸规划（基础版） 初始化 ：选择初始点 \( x_ 0 \)，初始信赖域半径 \( \Delta_ 0 > 0 \)，容忍误差 \( \epsilon > 0 \)，设置 \( k = 0 \)。 构造凸子问题 ：在当前点 \( x_ k \) 处线性化目标函数和约束，并添加信赖域约束 \( \| x - x_ k \|_ \infty \leq \Delta_ k \)。 求解子问题 ：求解上述凸优化问题，得到解 \( x_ {k+1}^* \)。 接受性检验 ：计算实际下降与预测下降的比值： \[ \rho_ k = \frac{\text{实际目标下降}}{\text{预测目标下降}} = \frac{f(x_ k) - f(x_ {k+1}^ )}{-\nabla f(x_ k)^T (x_ {k+1}^ - x_ k)}. \] 如果 \( \rho_ k \) 较大（例如 \( \rho_ k > \eta_ 1 = 0.1 \)），则认为近似较好，接受新点：\( x_ {k+1} = x_ {k+1}^* \)。 否则，拒绝新点，缩小信赖域半径 \( \Delta_ {k+1} = \gamma \Delta_ k \)（例如 \( \gamma = 0.5 \)），返回步骤2重新求解。 更新信赖域半径 ： 如果 \( \rho_ k > \eta_ 2 \)（例如 \( \eta_ 2 = 0.75 \)），说明近似很好，可扩大信赖域：\( \Delta_ {k+1} = \min(2\Delta_ k, \Delta_ {\max}) \)。 如果 \( \eta_ 1 \leq \rho_ k \leq \eta_ 2 \)，保持半径不变。 收敛判断 ：如果 \( \| x_ {k+1} - x_ k \| < \epsilon \) 且约束违反度足够小，则停止；否则令 \( k = k+1 \)，返回步骤2。 收敛性条件 ： 要求原问题满足一定的约束规范性（如MFCQ）。 序列 \(\{x_ k\}\) 的极限点通常是原问题的 KKT点 。 信赖域机制保证算法在非凸区域也能稳定逼近。 4. 数值例子演示 考虑一个简单二维非凸问题： \[ \begin{aligned} \min_ {x_ 1, x_ 2} \quad & f(x) = x_ 1^2 + x_ 2^2 - 0.5 \cos(4\pi x_ 1) - 0.5 \cos(4\pi x_ 2) \\ \text{s.t.} \quad & g(x) = x_ 1^2 + 2x_ 2^2 - 2 \leq 0, \\ & -1 \leq x_ 1, x_ 2 \leq 1. \end{aligned} \] （注：目标函数是非凸的Rastrigin-like函数，约束是凸椭圆区域。） 迭代过程 （简要）： 初始点 \( x_ 0 = (0.5, 0.5) \)，\( \Delta_ 0 = 0.3 \)。 在 \( x_ 0 \) 处线性化： \( f(x) \approx f(x_ 0) + (2x_ 1 + 2\pi \sin(4\pi x_ 1)) (x_ 1-0.5) + (2x_ 2 + 2\pi \sin(4\pi x_ 2)) (x_ 2-0.5) \)。 约束已凸，直接保留。 求解线性规划子问题（带信赖域约束），得新点 \( x_ 1^* \)。 计算接受比率 \( \rho_ 0 \)，若接受则更新点，调整信赖域半径。 重复直到收敛。通常经过10~20步迭代可接近局部最优解 \( x^* \approx (0,0) \)。 关键点总结 SCP通过 序列凸逼近 处理非凸问题，每一步是凸优化，计算高效。 需要 信赖域 或 移动限界 控制近似误差，保证收敛。 算法适用于目标/约束光滑但非凸的优化问题，是工程中常用的局部优化方法。