非线性规划中的序列凸近似（Sequential Convex Approximation, SCA）在带有逻辑约束的混合整数非线性规划（MINLP）中的应用进阶题

字数 6454 2025-12-14 00:25:37

非线性规划中的序列凸近似（Sequential Convex Approximation, SCA）在带有逻辑约束的混合整数非线性规划（MINLP）中的应用进阶题

题目描述

考虑一个带逻辑约束的混合整数非线性规划（MINLP）问题：

\[\begin{aligned} \min_{x, y} \quad & f(x, y) = x_1^2 + x_2^2 + 2y_1 + 3y_2 \\ \text{s.t.} \quad & g_1(x, y) = \exp(x_1 + x_2) - 5 \le 0, \\ & g_2(x, y) = \sin(x_1) + \cos(x_2) - 0.5 \le 0, \\ & h(x, y) = x_1^2 - x_2 + y_1 - 1 = 0, \\ & y_1, y_2 \in \{0, 1\}, \quad x_1, x_2 \in [-2, 2], \\ & \text{逻辑约束：} \quad (y_1 = 1) \implies (x_1 \ge 0.5), \\ & \text{逻辑约束：} \quad (y_2 = 0) \implies (x_2 \le -0.5). \end{aligned} \]

这是一个混合整数非线性规划问题，包含连续变量 \(x = (x_1, x_2)\) 和二元整数变量 \(y = (y_1, y_2)\)。逻辑约束是“如果 \(y_1 = 1\)，则 \(x_1 \ge 0.5\)”和“如果 \(y_2 = 0\)，则 \(x_2 \le -0.5\)”。这些逻辑约束使得问题非凸且难以直接求解。要求使用序列凸近似（SCA）方法，将原问题转化为一系列凸子问题进行迭代求解，并处理逻辑约束。

解题步骤详解

第1步：理解问题结构与难点

目标函数 \(f(x, y)\) 是二次函数（对 \(x\) 是凸二次，对 \(y\) 是线性），但整数变量 \(y\) 和逻辑约束引入了非凸性。
非线性约束 \(g_1, g_2\) 是非凸的：\(\exp(x_1+x_2)\) 是凸函数，但约束为 \(\le 0\) 形式，因此 \(g_1 \le 0\) 定义了一个非凸区域；\(g_2\) 由于正弦和余弦函数也是非凸的。
等式约束 \(h(x, y)\) 是二次的，但含有整数变量，整体非凸。
逻辑约束是离散的，通常需要引入辅助变量或大M法转化为线性约束。

关键：SCA 用于处理连续非凸约束，而整数变量和逻辑约束需要额外处理。思路是：在每次迭代中，固定整数变量，用SCA处理连续非凸部分；然后更新整数变量可能基于线性化或启发式策略。

第2步：转化逻辑约束为线性约束

逻辑约束可以通过引入大M法转化为线性不等式。定义一个大正数 \(M\)（例如 \(M = 10\)）。

对于 \((y_1 = 1) \implies (x_1 \ge 0.5)\)：
等价于：\(x_1 \ge 0.5 - M(1 - y_1)\)。
解释：如果 \(y_1 = 1\)，则不等式变为 \(x_1 \ge 0.5\)；如果 \(y_1 = 0\)，则变为 \(x_1 \ge 0.5 - M\)，由于 \(M\) 很大，这个约束自动满足（即不起作用）。
对于 \((y_2 = 0) \implies (x_2 \le -0.5)\)：
等价于：\(x_2 \le -0.5 + M y_2\)。
解释：如果 \(y_2 = 0\)，则不等式变为 \(x_2 \le -0.5\)；如果 \(y_2 = 1\)，则变为 \(x_2 \le -0.5 + M\)，自动满足。

这样，逻辑约束被转化为两个线性不等式，但引入了大M常数，可能造成松弛问题松紧程度影响求解效率。

第3步：构造序列凸近似（SCA）的子问题

SCA 的核心思想是：在每次迭代点 \((x^k, y^k)\) 处，对非凸函数进行凸近似，得到一个凸子问题，求解该子问题得到新的迭代点。

给定当前迭代点 \((x^k, y^k)\)，其中 \(y^k\) 是二元整数（固定或松弛），我们对非凸函数做一阶泰勒展开（线性化）或凸上/下近似。

对于 \(g_1(x, y) = \exp(x_1 + x_2) - 5\)：
由于 \(\exp(\cdot)\) 是凸函数，约束 \(g_1 \le 0\) 是非凸的。但我们可以利用凸函数的一阶下界性质：对于凸函数 \(\phi(z)\)，有 \(\phi(z) \ge \phi(z^k) + \nabla \phi(z^k)^T (z - z^k)\)。但我们需要 \(g_1 \le 0\)，即 \(\exp(x_1+x_2) \le 5\)。由于左边是凸函数，约束定义了一个非凸集（因为凸函数 ≤ 常数定义的是凸集，这里的确是凸集？检查：\(\exp(s)\) 是凸函数，集合 \(\{s : \exp(s) \le 5\} = \{s : s \le \ln 5\}\) 是凸集。但这里 \(s = x_1+x_2\)，线性函数，所以 \(g_1 \le 0\) 实际上是凸约束！因为 \(x_1+x_2 \le \ln 5\) 是线性约束。所以 \(g_1\) 是凸约束，无需近似。
对于 \(g_2(x, y) = \sin(x_1) + \cos(x_2) - 0.5 \le 0\)：
\(\sin\) 和 \(\cos\) 是非凸函数。在点 \(x^k\) 处，我们可以用一阶泰勒展开得到线性近似：

\[ \tilde{g}_2(x; x^k) = \sin(x_1^k) + \cos(x_2^k) + \cos(x_1^k)(x_1 - x_1^k) - \sin(x_2^k)(x_2 - x_2^k) - 0.5 \le 0. \]

这是线性约束，因此是凸的。但线性化可能使可行域缩小，为了保证 SCA 的收敛性，通常需要添加信赖域约束或惩罚项来控制近似误差。

对于等式约束 \(h(x, y) = x_1^2 - x_2 + y_1 - 1 = 0\)：
\(x_1^2\) 是凸函数，但等式约束整体是非凸的。我们可以将其松弛为两个不等式：\(h \le 0\) 和 \(h \ge 0\)，然后分别线性化。但更常见的是将等式保留，并在 SCA 子问题中线性化 \(x_1^2\) 项：

\[ x_1^2 \approx (x_1^k)^2 + 2x_1^k (x_1 - x_1^k) = 2x_1^k x_1 - (x_1^k)^2. \]

于是线性化后的等式约束为：

\[ 2x_1^k x_1 - (x_1^k)^2 - x_2 + y_1 - 1 = 0. \]

注意：线性化后等式约束是线性的，因此子问题是凸的（如果整数变量固定或松弛为连续）。

第4步：处理整数变量

在 SCA 框架中处理 MINLP 的常见策略：

外部分支定界或切割平面：将 MINLP 分解为连续非线性子问题（用 SCA 求解）和整数处理部分。
松弛与取整：在每次 SCA 迭代中，将 \(y\) 松弛为连续变量 \(y \in [0,1]\)，求解连续凸子问题，然后对 \(y\) 进行取整（如四舍五入到 0 或 1），再固定 \(y\) 求解连续变量 \(x\)。
交替优化：固定 \(y\)，用 SCA 求解 \(x\)；然后固定 \(x\)，求解 \(y\) 的整数线性规划（因为目标函数和约束在固定 \(x\) 后关于 \(y\) 是线性的）。

这里我们采用交替优化策略，因为 \(y\) 只出现在线性和逻辑约束中。

步骤：

给定当前 \((x^k, y^k)\)，先固定 \(y = y^k\)，构造关于 \(x\) 的 SCA 凸子问题（线性化 \(g_2\) 和 \(h\) 中的非线性项）。
求解该凸子问题得到 \(x^{k+1}\)。
固定 \(x = x^{k+1}\)，求解关于 \(y\) 的整数线性规划（目标函数为 \(2y_1+3y_2\)，约束为线性化后的逻辑约束和可能的其他线性约束），得到 \(y^{k+1}\)。
重复直到收敛。

第5步：构造第 k 次迭代的凸子问题

假设当前点为 \((x^k, y^k)\)，其中 \(y^k\) 是整数。

子问题（关于 \(x\)，固定 \(y = y^k\)）：

\[\begin{aligned} \min_{x} \quad & x_1^2 + x_2^2 + 2y_1^k + 3y_2^k \\ \text{s.t.} \quad & x_1 + x_2 \le \ln 5, \quad (\text{由 } g_1 \le 0 \text{ 等价得到}) \\ & \sin(x_1^k) + \cos(x_2^k) + \cos(x_1^k)(x_1 - x_1^k) - \sin(x_2^k)(x_2 - x_2^k) - 0.5 \le 0, \\ & 2x_1^k x_1 - (x_1^k)^2 - x_2 + y_1^k - 1 = 0, \\ & x_1 \ge 0.5 - M(1 - y_1^k), \\ & x_2 \le -0.5 + M y_2^k, \\ & x_1, x_2 \in [-2, 2]. \end{aligned} \]

这是一个凸二次规划（目标为凸二次，约束为线性），可用内点法或有效集法快速求解。

第6步：求解关于 \(y\) 的整数线性规划

固定 \(x = x^{k+1}\)，关于 \(y\) 的问题为：

\[\begin{aligned} \min_{y} \quad & 2y_1 + 3y_2 \\ \text{s.t.} \quad & x_1^{k+1} \ge 0.5 - M(1 - y_1), \\ & x_2^{k+1} \le -0.5 + M y_2, \\ & y_1, y_2 \in \{0, 1\}. \end{aligned} \]

这是一个简单的整数线性规划，由于只有两个0-1变量，可以枚举所有四种可能（\((0,0), (0,1), (1,0), (1,1)\)）并选择满足约束且目标最小的组合。

第7步：算法流程

初始化：选择初始点 \((x^0, y^0)\)，例如 \(x^0 = (0,0)\)，\(y^0 = (0,0)\)。设定容忍误差 \(\epsilon > 0\)，最大迭代次数 \(K\)。
对于 \(k = 0, 1, 2, \dots, K-1\) 执行：
a. 固定 \(y = y^k\)，求解上述凸子问题得到 \(x^{k+1}\)。
b. 固定 \(x = x^{k+1}\)，枚举 \(y\) 的四种可能取值，得到最优的 \(y^{k+1}\)。
c. 如果 \(\|x^{k+1} - x^k\| < \epsilon\) 且 \(y^{k+1} = y^k\)，则停止；否则继续。
输出最终解 \((x^*, y^*)\)。

第8步：收敛性说明

SCA 通常要求近似函数是原函数的凸上界或下界，并满足一定的保守性条件（如信赖域或惩罚项）。本例中对 \(g_2\) 的线性化是局部近似，没有全局保证，因此可能陷入局部最优。实际中可加入信赖域约束 \(\|x - x^k\|_\infty \le \Delta^k\) 来控制步长，并动态调整 \(\Delta^k\) 以保证收敛。
对于 MINLP，交替优化可能收敛到局部最优解，但逻辑约束被精确满足。

第9步：举例数值计算

假设 \(M = 10\)，初始点 \(x^0 = (0,0)\)，\(y^0 = (0,0)\)。

第一次迭代：

固定 \(y^0 = (0,0)\)，子问题变为：

\[ \begin{aligned} \min \quad & x_1^2 + x_2^2 \\ \text{s.t.} \quad & x_1 + x_2 \le \ln 5 \approx 1.609, \\ & \sin(0) + \cos(0) + \cos(0)(x_1-0) - \sin(0)(x_2-0) - 0.5 = 1 + x_1 - 0.5 = x_1 + 0.5 \le 0, \\ & 0 - 0 - x_2 + 0 - 1 = -x_2 - 1 = 0 \quad \Rightarrow \quad x_2 = -1, \\ & x_1 \ge 0.5 - 10(1-0) = -9.5, \\ & x_2 \le -0.5 + 10*0 = -0.5, \\ & x_1, x_2 \in [-2, 2]. \end{aligned} \]

由等式 \(x_2 = -1\)，代入第一个约束得 \(x_1 \le 2.609\)，由第二个约束得 \(x_1 \le -0.5\)，同时 \(x_2 = -1 \le -0.5\) 满足。所以子问题是凸二次规划，求解得最优解：目标函数是 \(x_1^2 + 1\)，在 \(x_1 \le -0.5\) 下，最小值在 \(x_1 = -0.5\) 处取到。所以 \(x^1 = (-0.5, -1)\)。

固定 \(x^1 = (-0.5, -1)\)，求解 \(y\) 的问题：
约束变为：

\[ -0.5 \ge 0.5 - 10(1 - y_1) \quad \Rightarrow \quad -0.5 \ge 0.5 - 10 + 10y_1 \quad \Rightarrow \quad 10y_1 \ge -0.5 - 0.5 + 10 = 9 \quad \Rightarrow \quad y_1 \ge 0.9. \]

\[ -1 \le -0.5 + 10 y_2 \quad \Rightarrow \quad -0.5 \le 10 y_2 \quad \Rightarrow \quad y_2 \ge -0.05. \]

由于 \(y_1, y_2 \in \{0,1\}\)，约束 \(y_1 \ge 0.9\) 意味着 \(y_1 = 1\)；约束 \(y_2 \ge -0.05\) 对 \(y_2 = 0\) 或 \(1\) 都成立。目标函数为 \(2y_1+3y_2\)，最小化时选 \(y_2 = 0\)。所以 \(y^1 = (1, 0)\)。

第二次迭代：

固定 \(y^1 = (1,0)\)，构造子问题（略），求解得到新的 \(x^2\)，然后更新 \(y^2\)。重复直到收敛。

实际计算中，通常几次迭代后就会稳定。最终解可能为 \(x^* \approx (0.5, -1)\)，\(y^* = (1,0)\)，满足逻辑约束。

总结

本题展示了序列凸近似（SCA）在带逻辑约束的 MINLP 中的应用。核心步骤包括：将逻辑约束转化为线性不等式，在迭代点对非凸函数线性化得到凸子问题，交替优化连续变量和整数变量。该方法能有效处理非凸约束和离散逻辑，但可能陷入局部最优，需结合信赖域或全局优化技巧改进。

非线性规划中的序列凸近似（Sequential Convex Approximation, SCA）在带有逻辑约束的混合整数非线性规划（MINLP）中的应用进阶题题目描述考虑一个带逻辑约束的混合整数非线性规划（MINLP）问题： \[ \begin{aligned} \min_ {x, y} \quad & f(x, y) = x_ 1^2 + x_ 2^2 + 2y_ 1 + 3y_ 2 \\ \text{s.t.} \quad & g_ 1(x, y) = \exp(x_ 1 + x_ 2) - 5 \le 0, \\ & g_ 2(x, y) = \sin(x_ 1) + \cos(x_ 2) - 0.5 \le 0, \\ & h(x, y) = x_ 1^2 - x_ 2 + y_ 1 - 1 = 0, \\ & y_ 1, y_ 2 \in \{0, 1\}, \quad x_ 1, x_ 2 \in [ -2, 2 ], \\ & \text{逻辑约束：} \quad (y_ 1 = 1) \implies (x_ 1 \ge 0.5), \\ & \text{逻辑约束：} \quad (y_ 2 = 0) \implies (x_ 2 \le -0.5). \end{aligned} \] 这是一个混合整数非线性规划问题，包含连续变量 \(x = (x_ 1, x_ 2)\) 和二元整数变量 \(y = (y_ 1, y_ 2)\)。逻辑约束是“如果 \(y_ 1 = 1\)，则 \(x_ 1 \ge 0.5\)”和“如果 \(y_ 2 = 0\)，则 \(x_ 2 \le -0.5\)”。这些逻辑约束使得问题非凸且难以直接求解。要求使用序列凸近似（SCA）方法，将原问题转化为一系列凸子问题进行迭代求解，并处理逻辑约束。解题步骤详解第1步：理解问题结构与难点目标函数 \(f(x, y)\) 是二次函数（对 \(x\) 是凸二次，对 \(y\) 是线性），但整数变量 \(y\) 和逻辑约束引入了非凸性。非线性约束 \(g_ 1, g_ 2\) 是非凸的：\(\exp(x_ 1+x_ 2)\) 是凸函数，但约束为 \(\le 0\) 形式，因此 \(g_ 1 \le 0\) 定义了一个非凸区域；\(g_ 2\) 由于正弦和余弦函数也是非凸的。等式约束 \(h(x, y)\) 是二次的，但含有整数变量，整体非凸。逻辑约束是离散的，通常需要引入辅助变量或大M法转化为线性约束。关键：SCA 用于处理连续非凸约束，而整数变量和逻辑约束需要额外处理。思路是：在每次迭代中，固定整数变量，用SCA处理连续非凸部分；然后更新整数变量可能基于线性化或启发式策略。第2步：转化逻辑约束为线性约束逻辑约束可以通过引入大M法转化为线性不等式。定义一个大正数 \(M\)（例如 \(M = 10\)）。对于 \((y_ 1 = 1) \implies (x_ 1 \ge 0.5)\)：等价于：\(x_ 1 \ge 0.5 - M(1 - y_ 1)\)。解释：如果 \(y_ 1 = 1\)，则不等式变为 \(x_ 1 \ge 0.5\)；如果 \(y_ 1 = 0\)，则变为 \(x_ 1 \ge 0.5 - M\)，由于 \(M\) 很大，这个约束自动满足（即不起作用）。对于 \((y_ 2 = 0) \implies (x_ 2 \le -0.5)\)：等价于：\(x_ 2 \le -0.5 + M y_ 2\)。解释：如果 \(y_ 2 = 0\)，则不等式变为 \(x_ 2 \le -0.5\)；如果 \(y_ 2 = 1\)，则变为 \(x_ 2 \le -0.5 + M\)，自动满足。这样，逻辑约束被转化为两个线性不等式，但引入了大M常数，可能造成松弛问题松紧程度影响求解效率。第3步：构造序列凸近似（SCA）的子问题 SCA 的核心思想是：在每次迭代点 \((x^k, y^k)\) 处，对非凸函数进行凸近似，得到一个凸子问题，求解该子问题得到新的迭代点。给定当前迭代点 \((x^k, y^k)\)，其中 \(y^k\) 是二元整数（固定或松弛），我们对非凸函数做一阶泰勒展开（线性化）或凸上/下近似。对于 \(g_ 1(x, y) = \exp(x_ 1 + x_ 2) - 5\)：由于 \(\exp(\cdot)\) 是凸函数，约束 \(g_ 1 \le 0\) 是非凸的。但我们可以利用凸函数的一阶下界性质：对于凸函数 \(\phi(z)\)，有 \(\phi(z) \ge \phi(z^k) + \nabla \phi(z^k)^T (z - z^k)\)。但我们需要 \(g_ 1 \le 0\)，即 \(\exp(x_ 1+x_ 2) \le 5\)。由于左边是凸函数，约束定义了一个非凸集（因为凸函数 ≤ 常数定义的是凸集，这里的确是凸集？检查：\(\exp(s)\) 是凸函数，集合 \(\{s : \exp(s) \le 5\} = \{s : s \le \ln 5\}\) 是凸集。但这里 \(s = x_ 1+x_ 2\)，线性函数，所以 \(g_ 1 \le 0\) 实际上是凸约束！因为 \(x_ 1+x_ 2 \le \ln 5\) 是线性约束。所以 \(g_ 1\) 是凸约束，无需近似。对于 \(g_ 2(x, y) = \sin(x_ 1) + \cos(x_ 2) - 0.5 \le 0\)： \(\sin\) 和 \(\cos\) 是非凸函数。在点 \(x^k\) 处，我们可以用一阶泰勒展开得到线性近似： \[ \tilde{g}_ 2(x; x^k) = \sin(x_ 1^k) + \cos(x_ 2^k) + \cos(x_ 1^k)(x_ 1 - x_ 1^k) - \sin(x_ 2^k)(x_ 2 - x_ 2^k) - 0.5 \le 0. \] 这是线性约束，因此是凸的。但线性化可能使可行域缩小，为了保证 SCA 的收敛性，通常需要添加信赖域约束或惩罚项来控制近似误差。对于等式约束 \(h(x, y) = x_ 1^2 - x_ 2 + y_ 1 - 1 = 0\)： \(x_ 1^2\) 是凸函数，但等式约束整体是非凸的。我们可以将其松弛为两个不等式：\(h \le 0\) 和 \(h \ge 0\)，然后分别线性化。但更常见的是将等式保留，并在 SCA 子问题中线性化 \(x_ 1^2\) 项： \[ x_ 1^2 \approx (x_ 1^k)^2 + 2x_ 1^k (x_ 1 - x_ 1^k) = 2x_ 1^k x_ 1 - (x_ 1^k)^2. \] 于是线性化后的等式约束为： \[ 2x_ 1^k x_ 1 - (x_ 1^k)^2 - x_ 2 + y_ 1 - 1 = 0. \] 注意：线性化后等式约束是线性的，因此子问题是凸的（如果整数变量固定或松弛为连续）。第4步：处理整数变量在 SCA 框架中处理 MINLP 的常见策略：外部分支定界或切割平面：将 MINLP 分解为连续非线性子问题（用 SCA 求解）和整数处理部分。松弛与取整：在每次 SCA 迭代中，将 \(y\) 松弛为连续变量 \(y \in [ 0,1 ]\)，求解连续凸子问题，然后对 \(y\) 进行取整（如四舍五入到 0 或 1），再固定 \(y\) 求解连续变量 \(x\)。交替优化：固定 \(y\)，用 SCA 求解 \(x\)；然后固定 \(x\)，求解 \(y\) 的整数线性规划（因为目标函数和约束在固定 \(x\) 后关于 \(y\) 是线性的）。这里我们采用交替优化策略，因为 \(y\) 只出现在线性和逻辑约束中。步骤：给定当前 \((x^k, y^k)\)，先固定 \(y = y^k\)，构造关于 \(x\) 的 SCA 凸子问题（线性化 \(g_ 2\) 和 \(h\) 中的非线性项）。求解该凸子问题得到 \(x^{k+1}\)。固定 \(x = x^{k+1}\)，求解关于 \(y\) 的整数线性规划（目标函数为 \(2y_ 1+3y_ 2\)，约束为线性化后的逻辑约束和可能的其他线性约束），得到 \(y^{k+1}\)。重复直到收敛。第5步：构造第 k 次迭代的凸子问题假设当前点为 \((x^k, y^k)\)，其中 \(y^k\) 是整数。子问题（关于 \(x\)，固定 \(y = y^k\)）： \[ \begin{aligned} \min_ {x} \quad & x_ 1^2 + x_ 2^2 + 2y_ 1^k + 3y_ 2^k \\ \text{s.t.} \quad & x_ 1 + x_ 2 \le \ln 5, \quad (\text{由 } g_ 1 \le 0 \text{ 等价得到}) \\ & \sin(x_ 1^k) + \cos(x_ 2^k) + \cos(x_ 1^k)(x_ 1 - x_ 1^k) - \sin(x_ 2^k)(x_ 2 - x_ 2^k) - 0.5 \le 0, \\ & 2x_ 1^k x_ 1 - (x_ 1^k)^2 - x_ 2 + y_ 1^k - 1 = 0, \\ & x_ 1 \ge 0.5 - M(1 - y_ 1^k), \\ & x_ 2 \le -0.5 + M y_ 2^k, \\ & x_ 1, x_ 2 \in [ -2, 2 ]. \end{aligned} \] 这是一个凸二次规划（目标为凸二次，约束为线性），可用内点法或有效集法快速求解。第6步：求解关于 \(y\) 的整数线性规划固定 \(x = x^{k+1}\)，关于 \(y\) 的问题为： \[ \begin{aligned} \min_ {y} \quad & 2y_ 1 + 3y_ 2 \\ \text{s.t.} \quad & x_ 1^{k+1} \ge 0.5 - M(1 - y_ 1), \\ & x_ 2^{k+1} \le -0.5 + M y_ 2, \\ & y_ 1, y_ 2 \in \{0, 1\}. \end{aligned} \] 这是一个简单的整数线性规划，由于只有两个0-1变量，可以枚举所有四种可能（\((0,0), (0,1), (1,0), (1,1)\)）并选择满足约束且目标最小的组合。第7步：算法流程初始化：选择初始点 \((x^0, y^0)\)，例如 \(x^0 = (0,0)\)，\(y^0 = (0,0)\)。设定容忍误差 \(\epsilon > 0\)，最大迭代次数 \(K\)。对于 \(k = 0, 1, 2, \dots, K-1\) 执行： a. 固定 \(y = y^k\)，求解上述凸子问题得到 \(x^{k+1}\)。 b. 固定 \(x = x^{k+1}\)，枚举 \(y\) 的四种可能取值，得到最优的 \(y^{k+1}\)。 c. 如果 \(\|x^{k+1} - x^k\| < \epsilon\) 且 \(y^{k+1} = y^k\)，则停止；否则继续。输出最终解 \((x^ , y^ )\)。第8步：收敛性说明 SCA 通常要求近似函数是原函数的凸上界或下界，并满足一定的保守性条件（如信赖域或惩罚项）。本例中对 \(g_ 2\) 的线性化是局部近似，没有全局保证，因此可能陷入局部最优。实际中可加入信赖域约束 \(\|x - x^k\|_ \infty \le \Delta^k\) 来控制步长，并动态调整 \(\Delta^k\) 以保证收敛。对于 MINLP，交替优化可能收敛到局部最优解，但逻辑约束被精确满足。第9步：举例数值计算假设 \(M = 10\)，初始点 \(x^0 = (0,0)\)，\(y^0 = (0,0)\)。第一次迭代：固定 \(y^0 = (0,0)\)，子问题变为： \[ \begin{aligned} \min \quad & x_ 1^2 + x_ 2^2 \\ \text{s.t.} \quad & x_ 1 + x_ 2 \le \ln 5 \approx 1.609, \\ & \sin(0) + \cos(0) + \cos(0)(x_ 1-0) - \sin(0)(x_ 2-0) - 0.5 = 1 + x_ 1 - 0.5 = x_ 1 + 0.5 \le 0, \\ & 0 - 0 - x_ 2 + 0 - 1 = -x_ 2 - 1 = 0 \quad \Rightarrow \quad x_ 2 = -1, \\ & x_ 1 \ge 0.5 - 10(1-0) = -9.5, \\ & x_ 2 \le -0.5 + 10* 0 = -0.5, \\ & x_ 1, x_ 2 \in [ -2, 2 ]. \end{aligned} \] 由等式 \(x_ 2 = -1\)，代入第一个约束得 \(x_ 1 \le 2.609\)，由第二个约束得 \(x_ 1 \le -0.5\)，同时 \(x_ 2 = -1 \le -0.5\) 满足。所以子问题是凸二次规划，求解得最优解：目标函数是 \(x_ 1^2 + 1\)，在 \(x_ 1 \le -0.5\) 下，最小值在 \(x_ 1 = -0.5\) 处取到。所以 \(x^1 = (-0.5, -1)\)。固定 \(x^1 = (-0.5, -1)\)，求解 \(y\) 的问题：约束变为： \[ -0.5 \ge 0.5 - 10(1 - y_ 1) \quad \Rightarrow \quad -0.5 \ge 0.5 - 10 + 10y_ 1 \quad \Rightarrow \quad 10y_ 1 \ge -0.5 - 0.5 + 10 = 9 \quad \Rightarrow \quad y_ 1 \ge 0.9. \] \[ -1 \le -0.5 + 10 y_ 2 \quad \Rightarrow \quad -0.5 \le 10 y_ 2 \quad \Rightarrow \quad y_ 2 \ge -0.05. \] 由于 \(y_ 1, y_ 2 \in \{0,1\}\)，约束 \(y_ 1 \ge 0.9\) 意味着 \(y_ 1 = 1\)；约束 \(y_ 2 \ge -0.05\) 对 \(y_ 2 = 0\) 或 \(1\) 都成立。目标函数为 \(2y_ 1+3y_ 2\)，最小化时选 \(y_ 2 = 0\)。所以 \(y^1 = (1, 0)\)。第二次迭代：固定 \(y^1 = (1,0)\)，构造子问题（略），求解得到新的 \(x^2\)，然后更新 \(y^2\)。重复直到收敛。实际计算中，通常几次迭代后就会稳定。最终解可能为 \(x^* \approx (0.5, -1)\)，\(y^* = (1,0)\)，满足逻辑约束。总结本题展示了序列凸近似（SCA）在带逻辑约束的 MINLP 中的应用。核心步骤包括：将逻辑约束转化为线性不等式，在迭代点对非凸函数线性化得到凸子问题，交替优化连续变量和整数变量。该方法能有效处理非凸约束和离散逻辑，但可能陷入局部最优，需结合信赖域或全局优化技巧改进。