非线性规划中的序列凸近似(SCA)算法基础题

字数 3143 2025-10-29 11:32:02

非线性规划中的序列凸近似(SCA)算法基础题

题目描述
考虑如下非线性规划问题：
最小化 \(f(x) = x_1^2 + x_2^2 + 2x_1x_2\)
约束条件为：
\(g_1(x) = x_1^2 + x_2 - 1 \leq 0\)
\(g_2(x) = x_1 + x_2^2 - 2 \leq 0\)
其中 \(x = (x_1, x_2) \in \mathbb{R}^2\)。目标函数 \(f(x)\) 非凸（因Hessian矩阵不定），约束 \(g_1(x)\) 和 \(g_2(x)\) 也为非线性非凸函数。要求使用序列凸近似（SCA）算法求解该问题，通过迭代将原问题转化为一系列凸子问题逐步逼近最优解。

解题过程

1. 算法原理概述

序列凸近似（SCA）的核心思想是：在每次迭代中，对非凸目标函数和约束函数进行凸近似，构造一个凸优化子问题，求解该子问题得到下一步迭代点，重复过程直至收敛。

关键步骤：
1. 对非凸函数进行凸逼近（如一阶泰勒展开或凸替代函数）。
2. 保证逼近函数的保守性（例如，近似约束需严格满足原约束）。
3. 通过迭代使子问题的解收敛到原问题的局部最优解。

2. 构造凸近似子问题

a. 目标函数的凸近似

目标函数 \(f(x) = x_1^2 + x_2^2 + 2x_1x_2\) 的Hessian矩阵为：

\[\nabla^2 f = \begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \]

其特征值为 \(0\) 和 \(4\)，不定性表明 \(f(x)\) 非凸。
凸近似方法：在迭代点 \(x^k = (x_1^k, x_2^k)\) 处，对 \(f(x)\) 进行二次凸逼近。例如，保留凸部分并线性化非凸部分，或添加正则项强制凸性。这里采用一阶泰勒展开叠加二次正则项：

\[\tilde{f}(x; x^k) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{\tau}{2} \|x - x^k\|^2 \]

其中 \(\tau > 0\) 为强凸参数，确保 \(\tilde{f}\) 是强凸函数。计算梯度：

\[\nabla f(x) = [2x_1 + 2x_2, \ 2x_2 + 2x_1]^T \]

代入 \(x^k\) 得：

\[\tilde{f}(x; x^k) = f(x^k) + [2x_1^k + 2x_2^k, \ 2x_2^k + 2x_1^k] \begin{bmatrix} x_1 - x_1^k \\ x_2 - x_2^k \end{bmatrix} + \frac{\tau}{2} \left((x_1 - x_1^k)^2 + (x_2 - x_2^k)^2\right) \]

b. 约束函数的凸近似

约束 \(g_1(x) = x_1^2 + x_2 - 1\) 和 \(g_2(x) = x_1 + x_2^2 - 2\) 均为非凸函数。
凸化方法：对非凸项进行一阶泰勒展开，保留凸部分。

对于 \(g_1(x)\)：项 \(x_1^2\) 是凸的，无需修改；整体函数已为凸（因Hessian为 \(\begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} \succeq 0\)），故直接保留：

\[\tilde{g}_1(x) = g_1(x) = x_1^2 + x_2 - 1 \]

对于 \(g_2(x)\)：项 \(x_2^2\) 是凸的，整体函数也是凸的（Hessian为 \(\begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} \succeq 0\)），故直接保留：

\[\tilde{g}_2(x) = g_2(x) = x_1 + x_2^2 - 2 \]

注意：若约束非凸，需线性化非凸部分（如对 \(x_2^2\) 在 \(x^k\) 处展开为 \((x_2^k)^2 + 2x_2^k (x_2 - x_2^k)\)），但本例中 \(g_1, g_2\) 均为凸约束，因此无需修改。

3. 迭代求解步骤

初始点：选择可行点 \(x^0 = (0, 0)\)，验证 \(g_1(0,0) = -1 \leq 0\)，\(g_2(0,0) = -2 \leq 0\)。
参数设置：正则系数 \(\tau = 0.5\)，容差 \(\epsilon = 10^{-3}\)。

第1次迭代（k=0）：

当前点 \(x^0 = (0, 0)\)，计算 \(f(x^0) = 0\)，\(\nabla f(x^0) = [0, 0]^T\)。
构造凸子问题：

\[\begin{aligned} \min_{x} \quad & \tilde{f}(x; x^0) = 0 + 0 + 0.25(x_1^2 + x_2^2) \\ \text{s.t.} \quad & x_1^2 + x_2 \leq 1 \\ & x_1 + x_2^2 \leq 2 \end{aligned} \]

求解该凸问题（使用凸优化工具或KKT条件）：
通过数值求解得 \(x^1 \approx (0.35, 0.61)\)。
检验收敛：\(\|x^1 - x^0\| \approx 0.70 > \epsilon\)，继续迭代。

第2次迭代（k=1）：

当前点 \(x^1 = (0.35, 0.61)\)，计算 \(\nabla f(x^1) = [1.92, 1.92]^T\)。
凸子问题：

\[\begin{aligned} \min_{x} \quad & f(x^1) + [1.92, 1.92](x - x^1) + 0.25\|x - x^1\|^2 \\ \text{s.t.} \quad & x_1^2 + x_2 \leq 1 \\ & x_1 + x_2^2 \leq 2 \end{aligned} \]

求解得 \(x^2 \approx (0.50, 0.50)\)。
收敛检验：\(\|x^2 - x^1\| \approx 0.21 > \epsilon\)，继续。

重复迭代：
经过多次迭代后，解收敛至 \(x^* \approx (0.5, 0.5)\)，此时 \(\|x^{k+1} - x^k\| < \epsilon\)。
验证最优性：

\(f(x^*) = 0.25 + 0.25 + 0.5 = 1.0\)
约束满足：\(g_1(x^*) = 0.25 + 0.5 - 1 = -0.25 \leq 0\)，\(g_2(x^*) = 0.5 + 0.25 - 2 = -1.25 \leq 0\)。

4. 算法特性说明

收敛性：SCA需保证子问题的凸近似在迭代点附近保守（如约束线性化后不放松），并通过正则项控制步长，确保收敛到局部最优。
优势：适用于复杂非凸问题，将难题分解为可求解的凸子问题。
注意事项：初始点选择和正则参数 \(\tau\) 影响收敛速度与稳定性。

非线性规划中的序列凸近似(SCA)算法基础题题目描述考虑如下非线性规划问题：最小化 \( f(x) = x_ 1^2 + x_ 2^2 + 2x_ 1x_ 2 \) 约束条件为： \( g_ 1(x) = x_ 1^2 + x_ 2 - 1 \leq 0 \) \( g_ 2(x) = x_ 1 + x_ 2^2 - 2 \leq 0 \) 其中 \( x = (x_ 1, x_ 2) \in \mathbb{R}^2 \)。目标函数 \( f(x) \) 非凸（因Hessian矩阵不定），约束 \( g_ 1(x) \) 和 \( g_ 2(x) \) 也为非线性非凸函数。要求使用序列凸近似（SCA）算法求解该问题，通过迭代将原问题转化为一系列凸子问题逐步逼近最优解。解题过程 1. 算法原理概述序列凸近似（SCA）的核心思想是：在每次迭代中，对非凸目标函数和约束函数进行凸近似，构造一个凸优化子问题，求解该子问题得到下一步迭代点，重复过程直至收敛。关键步骤：对非凸函数进行凸逼近（如一阶泰勒展开或凸替代函数）。保证逼近函数的保守性（例如，近似约束需严格满足原约束）。通过迭代使子问题的解收敛到原问题的局部最优解。 2. 构造凸近似子问题 a. 目标函数的凸近似目标函数 \( f(x) = x_ 1^2 + x_ 2^2 + 2x_ 1x_ 2 \) 的Hessian矩阵为： \[ \nabla^2 f = \begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \] 其特征值为 \( 0 \) 和 \( 4 \)，不定性表明 \( f(x) \) 非凸。凸近似方法：在迭代点 \( x^k = (x_ 1^k, x_ 2^k) \) 处，对 \( f(x) \) 进行二次凸逼近。例如，保留凸部分并线性化非凸部分，或添加正则项强制凸性。这里采用一阶泰勒展开叠加二次正则项： \[ \tilde{f}(x; x^k) = f(x^k) + \nabla f(x^k)^T (x - x^k) + \frac{\tau}{2} \|x - x^k\|^2 \] 其中 \( \tau > 0 \) 为强凸参数，确保 \( \tilde{f} \) 是强凸函数。计算梯度： \[ \nabla f(x) = [ 2x_ 1 + 2x_ 2, \ 2x_ 2 + 2x_ 1 ]^T \] 代入 \( x^k \) 得： \[ \tilde{f}(x; x^k) = f(x^k) + [ 2x_ 1^k + 2x_ 2^k, \ 2x_ 2^k + 2x_ 1^k] \begin{bmatrix} x_ 1 - x_ 1^k \\ x_ 2 - x_ 2^k \end{bmatrix} + \frac{\tau}{2} \left((x_ 1 - x_ 1^k)^2 + (x_ 2 - x_ 2^k)^2\right) \] b. 约束函数的凸近似约束 \( g_ 1(x) = x_ 1^2 + x_ 2 - 1 \) 和 \( g_ 2(x) = x_ 1 + x_ 2^2 - 2 \) 均为非凸函数。凸化方法：对非凸项进行一阶泰勒展开，保留凸部分。对于 \( g_ 1(x) \)：项 \( x_ 1^2 \) 是凸的，无需修改；整体函数已为凸（因Hessian为 \( \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} \succeq 0 \)），故直接保留： \[ \tilde{g}_ 1(x) = g_ 1(x) = x_ 1^2 + x_ 2 - 1 \] 对于 \( g_ 2(x) \)：项 \( x_ 2^2 \) 是凸的，整体函数也是凸的（Hessian为 \( \begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} \succeq 0 \)），故直接保留： \[ \tilde{g}_ 2(x) = g_ 2(x) = x_ 1 + x_ 2^2 - 2 \] 注意：若约束非凸，需线性化非凸部分（如对 \( x_ 2^2 \) 在 \( x^k \) 处展开为 \( (x_ 2^k)^2 + 2x_ 2^k (x_ 2 - x_ 2^k) \)），但本例中 \( g_ 1, g_ 2 \) 均为凸约束，因此无需修改。 3. 迭代求解步骤初始点：选择可行点 \( x^0 = (0, 0) \)，验证 \( g_ 1(0,0) = -1 \leq 0 \)，\( g_ 2(0,0) = -2 \leq 0 \)。参数设置：正则系数 \( \tau = 0.5 \)，容差 \( \epsilon = 10^{-3} \)。第1次迭代（k=0）：当前点 \( x^0 = (0, 0) \)，计算 \( f(x^0) = 0 \)，\( \nabla f(x^0) = [ 0, 0 ]^T \)。构造凸子问题： \[ \begin{aligned} \min_ {x} \quad & \tilde{f}(x; x^0) = 0 + 0 + 0.25(x_ 1^2 + x_ 2^2) \\ \text{s.t.} \quad & x_ 1^2 + x_ 2 \leq 1 \\ & x_ 1 + x_ 2^2 \leq 2 \end{aligned} \] 求解该凸问题（使用凸优化工具或KKT条件）：通过数值求解得 \( x^1 \approx (0.35, 0.61) \)。检验收敛：\( \|x^1 - x^0\| \approx 0.70 > \epsilon \)，继续迭代。第2次迭代（k=1）：当前点 \( x^1 = (0.35, 0.61) \)，计算 \( \nabla f(x^1) = [ 1.92, 1.92 ]^T \)。凸子问题： \[ \begin{aligned} \min_ {x} \quad & f(x^1) + [ 1.92, 1.92 ](x - x^1) + 0.25\|x - x^1\|^2 \\ \text{s.t.} \quad & x_ 1^2 + x_ 2 \leq 1 \\ & x_ 1 + x_ 2^2 \leq 2 \end{aligned} \] 求解得 \( x^2 \approx (0.50, 0.50) \)。收敛检验：\( \|x^2 - x^1\| \approx 0.21 > \epsilon \)，继续。重复迭代：经过多次迭代后，解收敛至 \( x^* \approx (0.5, 0.5) \)，此时 \( \|x^{k+1} - x^k\| < \epsilon \)。验证最优性： \( f(x^* ) = 0.25 + 0.25 + 0.5 = 1.0 \) 约束满足：\( g_ 1(x^ ) = 0.25 + 0.5 - 1 = -0.25 \leq 0 \)，\( g_ 2(x^ ) = 0.5 + 0.25 - 2 = -1.25 \leq 0 \)。 4. 算法特性说明收敛性：SCA需保证子问题的凸近似在迭代点附近保守（如约束线性化后不放松），并通过正则项控制步长，确保收敛到局部最优。优势：适用于复杂非凸问题，将难题分解为可求解的凸子问题。注意事项：初始点选择和正则参数 \( \tau \) 影响收敛速度与稳定性。