非线性规划中的自适应松弛-序列凸近似(Adaptive Relaxation - Sequential Convex Approximation)算法基础题

字数 4134 2025-12-16 02:45:19

非线性规划中的自适应松弛-序列凸近似(Adaptive Relaxation - Sequential Convex Approximation)算法基础题

一、问题描述
考虑一个带有非线性不等式约束的非凸优化问题：

\[\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. \end{aligned} \]

其中目标函数 $f(x)$ 和约束函数 $g_i(x)$ 均为光滑但非凸。我们要求设计一种算法，在每次迭代中通过凸近似将原问题转化为一个凸子问题，并引入一种自适应的松弛策略，以确保子问题的可行性和算法的收敛性。具体地，假设在当前迭代点 $x_k$ 附近，我们可以构造凸的代理函数 $\tilde{f}_k(x)$ 和 $\tilde{g}_{i,k}(x)$ 来分别近似 $f(x)$ 和 $g_i(x)$，使得在 $x_k$ 处函数值和梯度值与原函数匹配（即一阶近似）。为了避免由于近似误差导致子问题不可行，我们在每个约束上引入一个松弛变量 $s_i \geq 0$，并通过对松弛变量施加一个自适应惩罚项来逐步收紧可行域，最终逼近原问题的解。

二、循序渐进讲解

步骤1：问题难点与核心思路

难点：直接求解非凸问题通常很困难。序列凸近似（SCA）通过一系列凸子问题逼近原问题，但近似可能破坏可行性，即基于当前点构造的凸近似可能使得原可行域的一部分被排除，导致子问题无解。
核心思路：在每次迭代求解的凸子问题中，对每个约束引入松弛变量 $s_i$，将约束放松为 $\tilde{g}_{i,k}(x) \leq s_i$。同时，在目标函数中加入对松弛变量的惩罚项 $\rho_k \sum_i s_i$，其中 $\rho_k > 0$ 是逐步增大的惩罚参数。这样，即使近似不够准确，子问题也有可行解（例如取足够大的 $s_i$）。随着迭代进行，我们增大 $\rho_k$，迫使 $s_i$ 趋近于0，从而逐渐恢复原约束。

步骤2：构造凸近似
在第 $k$ 次迭代，当前点为 $x_k$。

对目标函数，构造凸代理函数 $\tilde{f}_k(x)$，使其满足：

\[ \tilde{f}_k(x_k) = f(x_k), \quad \nabla \tilde{f}_k(x_k) = \nabla f(x_k) \]

一种常见选择是采用一阶泰勒展开加上一个正定的二次正则项（以保证凸性）：

\[ \tilde{f}_k(x) = f(x_k) + \nabla f(x_k)^\top (x - x_k) + \frac{\tau}{2} \|x - x_k\|^2 \]

其中 $\tau > 0$ 是足够大的常数以确保 $\tilde{f}_k$ 强凸。

对每个约束 $g_i(x)$，类似地构造凸近似 $\tilde{g}_{i,k}(x)$，使其满足：

\[ \tilde{g}_{i,k}(x_k) = g_i(x_k), \quad \nabla \tilde{g}_{i,k}(x_k) = \nabla g_i(x_k) \]

例如：

\[ \tilde{g}_{i,k}(x) = g_i(x_k) + \nabla g_i(x_k)^\top (x - x_k) + \frac{\sigma_i}{2} \|x - x_k\|^2 \]

其中 $\sigma_i \geq 0$ 可选取以保证 $\tilde{g}_{i,k}$ 为凸（若 $g_i$ 本身是凸函数，则可取 $\sigma_i = 0$；若非凸，则需取足够大的 $\sigma_i$ 使其在局部为凸）。

步骤3：构建带自适应松弛的凸子问题
在第 $k$ 次迭代，我们求解如下凸优化问题（通常为二次规划或凸规划）：

\[\begin{aligned} \min_{x, s \geq 0} \quad & \tilde{f}_k(x) + \rho_k \sum_{i=1}^m s_i \\ \text{s.t.} \quad & \tilde{g}_{i,k}(x) \leq s_i, \quad i = 1, \dots, m. \end{aligned} \]

这里 $s = [s_1, \dots, s_m]^\top$ 是松弛变量向量。注意：

当 $s_i = 0$ 时，约束恢复为原近似约束 $\tilde{g}_{i,k}(x) \leq 0$。
惩罚参数 $\rho_k$ 控制对松弛的厌恶程度：$\rho_k$ 越大，越倾向于让 $s_i$ 变小，从而收紧约束。
这个子问题总是可行的，因为对于任意 $x$，我们可以取 $s_i = \max(0, \tilde{g}_{i,k}(x))$ 使其满足约束。

步骤4：自适应更新惩罚参数
为了逐步逼近原问题的可行域，我们需要随着迭代增大 $\rho_k$。一个简单的自适应更新规则为：

初始化 $\rho_0 > 0$（例如 $\rho_0 = 1$）。
在第 $k$ 次迭代，求解子问题得到解 $(x_{k+1}, s_k)$。
检查松弛程度：若 $\|s_k\|_\infty$（最大松弛量）小于某个阈值 $\epsilon_s$（例如 $10^{-3}$），则认为近似可行域已足够紧，保持 $\rho_{k+1} = \rho_k$；否则，将惩罚参数增大，例如 $\rho_{k+1} = \beta \rho_k$，其中 $\beta > 1$（例如 $\beta = 2$）。
这种自适应策略可以在早期允许较大松弛以确保子问题可解，后期则强制约束满足。

步骤5：算法流程

初始化：选择初始点 $x_0$，初始惩罚参数 $\rho_0 > 0$，增长因子 $\beta > 1$，容忍度 $\epsilon > 0$，正则化参数 $\tau, \sigma_i$。令 $k = 0$。
循环直到收敛（例如 $\|x_{k+1} - x_k\| < \epsilon$ 且 $\|s_k\|_\infty < \epsilon$）：
a. 在当前点 $x_k$ 计算 $f(x_k), g_i(x_k)$ 及其梯度。
b. 构造凸近似函数 $\tilde{f}_k(x)$ 和 $\tilde{g}_{i,k}(x)$。
c. 求解带松弛的子问题，得到 $(x_{k+1}, s_k)$。
d. 根据松弛量 $\|s_k\|_\infty$ 更新惩罚参数：若 $\|s_k\|_\infty > \epsilon_s$，则 $\rho_{k+1} = \beta \rho_k$；否则 $\rho_{k+1} = \rho_k$。
e. $k \leftarrow k + 1$。
输出 $x_k$ 作为近似最优解。

步骤6：收敛性简要分析

由于每次子问题都是凸的，且可行域非空，因此可高效求解。
通过逐步增大 $\rho_k$，算法迫使松弛变量趋近于0。若近似函数构造合理（如一阶匹配且凸），则当 $s_k \to 0$ 时，子问题的解 $x_{k+1}$ 将满足原约束的近似，且目标值逐渐改善。
在适当条件下（如近似函数一致强凸、梯度 Lipschitz 连续等），可以证明算法生成的序列 $\{x_k\}$ 的任何极限点都是原问题的一个驻点（KKT点）。

步骤7：简单例子演示
考虑一个简单问题：

\[\min_{x \in \mathbb{R}} \quad x^4 - 4x^2 \quad \text{s.t.} \quad \sin(x) \leq 0. \]

在 $x_k$ 处，构造凸近似：

$\tilde{f}_k(x) = x_k^4 - 4x_k^2 + (4x_k^3 - 8x_k)(x - x_k) + \tau (x - x_k)^2$（取 $\tau$ 足够大，例如 $\tau = 10$）。
$\tilde{g}_k(x) = \sin(x_k) + \cos(x_k)(x - x_k)$（注意 $\sin(x)$ 非凸，但其一阶泰勒展开是线性的，故为凸）。
求解带松弛的子问题：

\[\min_{x, s \geq 0} \tilde{f}_k(x) + \rho_k s \quad \text{s.t.} \quad \tilde{g}_k(x) \leq s. \]

通过逐步增大 $\rho_k$，算法会驱使 $s \to 0$，最终收敛到满足 $\sin(x) \leq 0$ 且目标较小的点（例如 $x \approx -1.5$ 附近）。

这种自适应松弛-序列凸近似方法结合了凸近似的可解性和松弛策略的鲁棒性，适用于具有非凸约束的工程优化问题。

非线性规划中的自适应松弛-序列凸近似(Adaptive Relaxation - Sequential Convex Approximation)算法基础题一、问题描述考虑一个带有非线性不等式约束的非凸优化问题： $$ \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. \end{aligned} $$ 其中目标函数 $ f(x) $ 和约束函数 $ g_ i(x) $ 均为光滑但非凸。我们要求设计一种算法，在每次迭代中通过凸近似将原问题转化为一个凸子问题，并引入一种自适应的松弛策略，以确保子问题的可行性和算法的收敛性。具体地，假设在当前迭代点 $ x_ k $ 附近，我们可以构造凸的代理函数 $ \tilde{f} k(x) $ 和 $ \tilde{g} {i,k}(x) $ 来分别近似 $ f(x) $ 和 $ g_ i(x) $，使得在 $ x_ k $ 处函数值和梯度值与原函数匹配（即一阶近似）。为了避免由于近似误差导致子问题不可行，我们在每个约束上引入一个松弛变量 $ s_ i \geq 0 $，并通过对松弛变量施加一个自适应惩罚项来逐步收紧可行域，最终逼近原问题的解。二、循序渐进讲解步骤1：问题难点与核心思路难点：直接求解非凸问题通常很困难。序列凸近似（SCA）通过一系列凸子问题逼近原问题，但近似可能破坏可行性，即基于当前点构造的凸近似可能使得原可行域的一部分被排除，导致子问题无解。核心思路：在每次迭代求解的凸子问题中，对每个约束引入松弛变量 $ s_ i $，将约束放松为 $ \tilde{g}_ {i,k}(x) \leq s_ i $。同时，在目标函数中加入对松弛变量的惩罚项 $ \rho_ k \sum_ i s_ i $，其中 $ \rho_ k > 0 $ 是逐步增大的惩罚参数。这样，即使近似不够准确，子问题也有可行解（例如取足够大的 $ s_ i $）。随着迭代进行，我们增大 $ \rho_ k $，迫使 $ s_ i $ 趋近于0，从而逐渐恢复原约束。步骤2：构造凸近似在第 $ k $ 次迭代，当前点为 $ x_ k $。对目标函数，构造凸代理函数 $ \tilde{f}_ k(x) $，使其满足： \[ \tilde{f}_ k(x_ k) = f(x_ k), \quad \nabla \tilde{f}_ k(x_ k) = \nabla f(x_ k) \] 一种常见选择是采用一阶泰勒展开加上一个正定的二次正则项（以保证凸性）： \[ \tilde{f}_ k(x) = f(x_ k) + \nabla f(x_ k)^\top (x - x_ k) + \frac{\tau}{2} \|x - x_ k\|^2 \] 其中 $ \tau > 0 $ 是足够大的常数以确保 $ \tilde{f}_ k $ 强凸。对每个约束 $ g_ i(x) $，类似地构造凸近似 $ \tilde{g} {i,k}(x) $，使其满足： \[ \tilde{g} {i,k}(x_ k) = g_ i(x_ k), \quad \nabla \tilde{g} {i,k}(x_ k) = \nabla g_ i(x_ k) \] 例如： \[ \tilde{g} {i,k}(x) = g_ i(x_ k) + \nabla g_ i(x_ k)^\top (x - x_ k) + \frac{\sigma_ i}{2} \|x - x_ k\|^2 \] 其中 $ \sigma_ i \geq 0 $ 可选取以保证 $ \tilde{g}_ {i,k} $ 为凸（若 $ g_ i $ 本身是凸函数，则可取 $ \sigma_ i = 0 $；若非凸，则需取足够大的 $ \sigma_ i $ 使其在局部为凸）。步骤3：构建带自适应松弛的凸子问题在第 $ k $ 次迭代，我们求解如下凸优化问题（通常为二次规划或凸规划）： $$ \begin{aligned} \min_ {x, s \geq 0} \quad & \tilde{f} k(x) + \rho_ k \sum {i=1}^m s_ i \\ \text{s.t.} \quad & \tilde{g}_ {i,k}(x) \leq s_ i, \quad i = 1, \dots, m. \end{aligned} $$ 这里 $ s = [ s_ 1, \dots, s_ m ]^\top $ 是松弛变量向量。注意：当 $ s_ i = 0 $ 时，约束恢复为原近似约束 $ \tilde{g}_ {i,k}(x) \leq 0 $。惩罚参数 $ \rho_ k $ 控制对松弛的厌恶程度：$ \rho_ k $ 越大，越倾向于让 $ s_ i $ 变小，从而收紧约束。这个子问题总是可行的，因为对于任意 $ x $，我们可以取 $ s_ i = \max(0, \tilde{g}_ {i,k}(x)) $ 使其满足约束。步骤4：自适应更新惩罚参数为了逐步逼近原问题的可行域，我们需要随着迭代增大 $ \rho_ k $。一个简单的自适应更新规则为：初始化 $ \rho_ 0 > 0 $（例如 $ \rho_ 0 = 1 $）。在第 $ k $ 次迭代，求解子问题得到解 $ (x_ {k+1}, s_ k) $。检查松弛程度：若 $ \|s_ k\| \infty $（最大松弛量）小于某个阈值 $ \epsilon_ s $（例如 $ 10^{-3} $），则认为近似可行域已足够紧，保持 $ \rho {k+1} = \rho_ k $；否则，将惩罚参数增大，例如 $ \rho_ {k+1} = \beta \rho_ k $，其中 $ \beta > 1 $（例如 $ \beta = 2 $）。这种自适应策略可以在早期允许较大松弛以确保子问题可解，后期则强制约束满足。步骤5：算法流程初始化：选择初始点 $ x_ 0 $，初始惩罚参数 $ \rho_ 0 > 0 $，增长因子 $ \beta > 1 $，容忍度 $ \epsilon > 0 $，正则化参数 $ \tau, \sigma_ i $。令 $ k = 0 $。循环直到收敛（例如 $ \|x_ {k+1} - x_ k\| < \epsilon $ 且 $ \|s_ k\| \infty < \epsilon $）： a. 在当前点 $ x_ k $ 计算 $ f(x_ k), g_ i(x_ k) $ 及其梯度。 b. 构造凸近似函数 $ \tilde{f} k(x) $ 和 $ \tilde{g} {i,k}(x) $。 c. 求解带松弛的子问题，得到 $ (x {k+1}, s_ k) $。 d. 根据松弛量 $ \|s_ k\| \infty $ 更新惩罚参数：若 $ \|s_ k\| \infty > \epsilon_ s $，则 $ \rho_ {k+1} = \beta \rho_ k $；否则 $ \rho_ {k+1} = \rho_ k $。 e. $ k \leftarrow k + 1 $。输出 $ x_ k $ 作为近似最优解。步骤6：收敛性简要分析由于每次子问题都是凸的，且可行域非空，因此可高效求解。通过逐步增大 $ \rho_ k $，算法迫使松弛变量趋近于0。若近似函数构造合理（如一阶匹配且凸），则当 $ s_ k \to 0 $ 时，子问题的解 $ x_ {k+1} $ 将满足原约束的近似，且目标值逐渐改善。在适当条件下（如近似函数一致强凸、梯度 Lipschitz 连续等），可以证明算法生成的序列 $ \{x_ k\} $ 的任何极限点都是原问题的一个驻点（KKT点）。步骤7：简单例子演示考虑一个简单问题： $$ \min_ {x \in \mathbb{R}} \quad x^4 - 4x^2 \quad \text{s.t.} \quad \sin(x) \leq 0. $$ 在 $ x_ k $ 处，构造凸近似： $ \tilde{f}_ k(x) = x_ k^4 - 4x_ k^2 + (4x_ k^3 - 8x_ k)(x - x_ k) + \tau (x - x_ k)^2 $（取 $ \tau $ 足够大，例如 $ \tau = 10 $）。 $ \tilde{g} k(x) = \sin(x_ k) + \cos(x_ k)(x - x_ k) $（注意 $ \sin(x) $ 非凸，但其一阶泰勒展开是线性的，故为凸）。求解带松弛的子问题： $$ \min {x, s \geq 0} \tilde{f}_ k(x) + \rho_ k s \quad \text{s.t.} \quad \tilde{g}_ k(x) \leq s. $$ 通过逐步增大 $ \rho_ k $，算法会驱使 $ s \to 0 $，最终收敛到满足 $ \sin(x) \leq 0 $ 且目标较小的点（例如 $ x \approx -1.5 $ 附近）。这种自适应松弛-序列凸近似方法结合了凸近似的可解性和松弛策略的鲁棒性，适用于具有非凸约束的工程优化问题。