非线性规划中的分支定界-序列凸近似-混合整数非线性规划（Branch and Bound with Sequential Convex Approximation for MINLP）进阶题
字数 4439 2025-12-09 18:01:23

非线性规划中的分支定界-序列凸近似-混合整数非线性规划（Branch and Bound with Sequential Convex Approximation for MINLP）进阶题

题目描述：
考虑如下混合整数非线性规划（MINLP）问题：

\[\begin{aligned} \min_{\mathbf{x}, \mathbf{y}} \quad & f(\mathbf{x}, \mathbf{y}) = x_1^2 + 2x_2^2 + y_1^2 + 3y_2 \\ \text{s.t.} \quad & g_1(\mathbf{x}, \mathbf{y}) = x_1 + 2x_2 + y_1 - 5 \le 0, \\ & g_2(\mathbf{x}, \mathbf{y}) = x_1^2 + x_2^2 - 2y_2 \le 0, \\ & 0 \le x_1, x_2 \le 3, \\ & y_1, y_2 \in \{0, 1\}. \end{aligned} \]

其中，\(\mathbf{x} = (x_1, x_2)^T\) 是连续变量，\(\mathbf{y} = (y_1, y_2)^T\) 是二元整数变量。目标函数 \(f\) 是凸二次函数，但约束 \(g_2\) 是非凸的（因为 \(x_1^2 + x_2^2\) 是凸的，但 \(-2y_2\) 是线性的，整体非凸）。要求使用分支定界（Branch and Bound, B&B）框架，并结合序列凸近似（Sequential Convex Approximation, SCA） 求解该 MINLP 问题。请详细解释如何将 SCA 嵌入 B&B 中，并说明求解过程的关键步骤。

解题过程循序渐进讲解：

1. 问题分析与算法框架

混合整数非线性规划（MINLP） 包含连续变量和整数变量，且目标或约束非线性。直接求解通常困难，常见方法是：

  • 分支定界（B&B）：将原问题分解为若干子问题（通过固定整数变量或添加整数约束），构造搜索树，通过上下界剪枝。
  • 序列凸近似（SCA）：用于处理非凸子问题。每次迭代将非凸函数局部凸化，求解凸近似子问题，逐步逼近原非凸问题的解。

结合思路：在 B&B 的每个节点（对应整数变量部分固定或范围受限的子问题），使用 SCA 求解连续松弛问题（即整数变量视为连续），得到该节点的下界（对最小化问题）。通过上下界比较剪枝，最终找到全局最优解。

2. 分支定界框架的初始化

  • 根节点：对应原问题，整数变量 \(y_1, y_2 \in [0, 1]\) 松弛为连续变量。
  • 上界（UB）：初始设为 \(+\infty\)，表示当前找到的可行解的目标值。
  • 下界（LB）：根节点通过 SCA 求解连续松弛问题得到，作为全局下界。
  • 节点列表：初始只包含根节点。

3. 序列凸近似（SCA）在节点求解中的应用

对于节点 \(k\)，其整数变量约束为 \(y_i \in [0,1]\)（连续松弛）或已固定为 0/1。记当前迭代点为 \((\mathbf{x}^{(t)}, \mathbf{y}^{(t)})\)，SCA 的步骤如下：

3.1 凸近似构造

原约束 \(g_2(\mathbf{x}, \mathbf{y}) = x_1^2 + x_2^2 - 2y_2 \le 0\) 中，\(x_1^2 + x_2^2\) 已是凸函数，但整个约束关于 \((\mathbf{x}, \mathbf{y})\) 联合非凸（因为整数变量导致非凸性）。在连续松弛下，可将 \(y_2\) 视为连续变量，此时 \(g_2\) 是凸的（凸函数减去线性函数仍是凸的）。因此，在节点连续松弛问题中，所有约束都是凸的，无需额外凸近似。但 SCA 通常用于更一般的非凸情形，此处为演示，我们考虑对 \(g_2\) 的凸上近似（若 \(g_2\) 非凸）：

  • 若 \(g_2\) 非凸，可在当前点做一阶泰勒展开，得到线性近似（凸函数）。但本例中连续松弛下 \(g_2\) 已凸，故直接使用原约束。

一般 SCA 步骤（针对非凸 \(g(\mathbf{z}) \le 0\)）：

  1. 在点 \(\mathbf{z}^{(t)}\) 处构造凸替代函数 \(\tilde{g}(\mathbf{z}; \mathbf{z}^{(t)})\)，满足：
    • \(\tilde{g}\) 是凸函数。
    • \(\tilde{g}(\mathbf{z}^{(t)}; \mathbf{z}^{(t)}) = g(\mathbf{z}^{(t)})\)。
    • \(\tilde{g}(\mathbf{z}; \mathbf{z}^{(t)}) \ge g(\mathbf{z})\) 对所有 \(\mathbf{z}\) 成立（即上近似，保证可行域收缩）。
  2. 用 \(\tilde{g} \le 0\) 替代原约束，得到凸近似子问题。

本例中，由于连续松弛下问题已凸，SCA 退化为求解一个凸优化问题。但为展示完整流程，我们仍保留 SCA 的迭代结构。

3.2 凸近似子问题

在节点 \(k\) 的第 \(t\) 次 SCA 迭代中，求解如下凸问题（其中整数变量已连续化）：

\[\begin{aligned} \min_{\mathbf{x}, \mathbf{y}} \quad & f(\mathbf{x}, \mathbf{y}) \\ \text{s.t.} \quad & g_1(\mathbf{x}, \mathbf{y}) \le 0, \\ & \tilde{g}_2(\mathbf{x}, \mathbf{y}; \mathbf{x}^{(t)}, \mathbf{y}^{(t)}) \le 0, \\ & 0 \le x_1, x_2 \le 3, \quad 0 \le y_1, y_2 \le 1. \end{aligned} \]

这里 \(\tilde{g}_2 = g_2\)（因为已凸）。若 \(g_2\) 非凸，常用一阶泰勒展开：\(\tilde{g}_2 = g_2(\mathbf{z}^{(t)}) + \nabla g_2(\mathbf{z}^{(t)})^T (\mathbf{z} - \mathbf{z}^{(t)})\)，其中 \(\mathbf{z} = (\mathbf{x}, \mathbf{y})\)。

3.3 SCA 迭代流程

  1. 初始化：选择初始点 \((\mathbf{x}^{(0)}, \mathbf{y}^{(0)})\)，可设为可行点或任意点。
  2. 对于 \(t = 0, 1, 2, \dots\)：
    a. 构造凸近似子问题（如上）。
    b. 求解该凸问题，得新解 \((\mathbf{x}^{(t+1)}, \mathbf{y}^{(t+1)})\)。
    c. 若 \(\|(\mathbf{x}^{(t+1)}, \mathbf{y}^{(t+1)}) - (\mathbf{x}^{(t)}, \mathbf{y}^{(t)})\| < \epsilon\)（容差），则停止，返回解及目标值 \(f^{(t+1)}\)。
  3. 输出最终解作为节点连续松弛问题的最优解。

注意：由于连续松弛问题本身凸，SCA 会在一次迭代收敛（因为近似等于原问题）。实际中，若约束非凸，SCA 需多次迭代。

4. 分支定界步骤

  1. 节点选择：从节点列表中选择下界最小的节点（最可能包含最优解）。
  2. 节点求解：对该节点，用 SCA 求解连续松弛问题，得到最优值 \(L\)（下界）和解 \((\mathbf{x}^*, \mathbf{y}^*)\)。
  3. 剪枝判断：
    • 若 \(L \ge\) 当前上界 UB，则该节点不可能有更好解，剪枝。
    • 若解中所有整数变量 \(y_i\) 恰好为 0 或 1（即整数可行），则更新上界：UB = min(UB, \(L\))，并记录该可行解。
    • 否则，进入分支。
  4. 分支：选择一个分数整数变量 \(y_j\)（值不在 {0,1}），创建两个子节点：
    • 左子节点：添加约束 \(y_j = 0\)。
    • 右子节点：添加约束 \(y_j = 1\)。
      将子节点加入节点列表。
  5. 终止条件：节点列表为空，或全局下界（所有节点下界的最小值）与 UB 的差小于容忍度。

5. 应用本题的具体计算示例

假设在根节点，连续松弛问题为：

\[\begin{aligned} \min \quad & x_1^2 + 2x_2^2 + y_1^2 + 3y_2 \\ \text{s.t.} \quad & x_1 + 2x_2 + y_1 \le 5, \\ & x_1^2 + x_2^2 - 2y_2 \le 0, \\ & 0 \le x_1, x_2 \le 3, \quad 0 \le y_1, y_2 \le 1. \end{aligned} \]

这是一个凸问题（目标凸，约束凸），可直接用凸优化求解（如内点法）。解得：

  • 最优解：\(x_1^* \approx 0, x_2^* \approx 0, y_1^* \approx 0, y_2^* = 0\)（例如，通过观察：为使目标最小，应令 \(y_2=0\)，则 \(x_1=x_2=0\)，\(y_1=0\) 可行）。
  • 目标值 \(L = 0\)。

由于 \(y_1^*, y_2^*\) 已是整数，该解整数可行，故直接得到可行解，更新上界 UB = 0。此时全局下界也为 0，算法终止，最优解即为 \((0,0,0,0)\)，目标值为 0。

若解非整数：假设解得 \(y_2^* = 0.6\)，则需分支：创建节点 \(y_2=0\) 和 \(y_2=1\)，分别求解连续松弛问题，并重复上述过程。

6. 关键点总结

  1. SCA 的作用：在 B&B 每个节点求解连续松弛的非凸问题时，将非凸约束局部凸化，使子问题可高效求解。
  2. 上下界更新：节点连续松弛解提供下界；整数可行解提供上界。
  3. 分支策略：通常选分数值最接近 0.5 的变量分支，以快速收紧界。
  4. 收敛性：B&B 确保全局最优（因枚举所有整数组合，但通过剪枝减少计算），SCA 保证连续子问题收敛到局部最优（凸时全局最优）。

扩展：对于高度非凸问题，SCA 可能陷入局部解，可结合多起点或全局搜索改进。该方法在工程设计、资源分配等混合整数非线性问题中广泛应用。

非线性规划中的分支定界-序列凸近似-混合整数非线性规划（Branch and Bound with Sequential Convex Approximation for MINLP）进阶题 题目描述 ： 考虑如下混合整数非线性规划（MINLP）问题： \[ \begin{aligned} \min_ {\mathbf{x}, \mathbf{y}} \quad & f(\mathbf{x}, \mathbf{y}) = x_ 1^2 + 2x_ 2^2 + y_ 1^2 + 3y_ 2 \\ \text{s.t.} \quad & g_ 1(\mathbf{x}, \mathbf{y}) = x_ 1 + 2x_ 2 + y_ 1 - 5 \le 0, \\ & g_ 2(\mathbf{x}, \mathbf{y}) = x_ 1^2 + x_ 2^2 - 2y_ 2 \le 0, \\ & 0 \le x_ 1, x_ 2 \le 3, \\ & y_ 1, y_ 2 \in \{0, 1\}. \end{aligned} \] 其中，\(\mathbf{x} = (x_ 1, x_ 2)^T\) 是连续变量，\(\mathbf{y} = (y_ 1, y_ 2)^T\) 是二元整数变量。目标函数 \(f\) 是凸二次函数，但约束 \(g_ 2\) 是非凸的（因为 \(x_ 1^2 + x_ 2^2\) 是凸的，但 \(-2y_ 2\) 是线性的，整体非凸）。要求使用 分支定界（Branch and Bound, B&B）框架 ，并结合 序列凸近似（Sequential Convex Approximation, SCA） 求解该 MINLP 问题。请详细解释如何将 SCA 嵌入 B&B 中，并说明求解过程的关键步骤。 解题过程循序渐进讲解 ： 1. 问题分析与算法框架 混合整数非线性规划（MINLP） 包含连续变量和整数变量，且目标或约束非线性。直接求解通常困难，常见方法是： 分支定界（B&B） ：将原问题分解为若干子问题（通过固定整数变量或添加整数约束），构造搜索树，通过上下界剪枝。 序列凸近似（SCA） ：用于处理非凸子问题。每次迭代将非凸函数局部凸化，求解凸近似子问题，逐步逼近原非凸问题的解。 结合思路 ：在 B&B 的每个节点（对应整数变量部分固定或范围受限的子问题），使用 SCA 求解连续松弛问题（即整数变量视为连续），得到该节点的 下界 （对最小化问题）。通过上下界比较剪枝，最终找到全局最优解。 2. 分支定界框架的初始化 根节点 ：对应原问题，整数变量 \(y_ 1, y_ 2 \in [ 0, 1 ]\) 松弛为连续变量。 上界（UB） ：初始设为 \(+\infty\)，表示当前找到的可行解的目标值。 下界（LB） ：根节点通过 SCA 求解连续松弛问题得到，作为全局下界。 节点列表 ：初始只包含根节点。 3. 序列凸近似（SCA）在节点求解中的应用 对于节点 \(k\)，其整数变量约束为 \(y_ i \in [ 0,1 ]\)（连续松弛）或已固定为 0/1。记当前迭代点为 \((\mathbf{x}^{(t)}, \mathbf{y}^{(t)})\)，SCA 的步骤如下： 3.1 凸近似构造 原约束 \(g_ 2(\mathbf{x}, \mathbf{y}) = x_ 1^2 + x_ 2^2 - 2y_ 2 \le 0\) 中，\(x_ 1^2 + x_ 2^2\) 已是凸函数，但整个约束关于 \((\mathbf{x}, \mathbf{y})\) 联合非凸（因为整数变量导致非凸性）。在连续松弛下，可将 \(y_ 2\) 视为连续变量，此时 \(g_ 2\) 是凸的（凸函数减去线性函数仍是凸的）。因此，在节点连续松弛问题中， 所有约束都是凸的 ，无需额外凸近似。但 SCA 通常用于更一般的非凸情形，此处为演示，我们考虑对 \(g_ 2\) 的 凸上近似 （若 \(g_ 2\) 非凸）： 若 \(g_ 2\) 非凸，可在当前点做一阶泰勒展开，得到线性近似（凸函数）。但本例中连续松弛下 \(g_ 2\) 已凸，故直接使用原约束。 一般 SCA 步骤 （针对非凸 \(g(\mathbf{z}) \le 0\)）： 在点 \(\mathbf{z}^{(t)}\) 处构造凸替代函数 \(\tilde{g}(\mathbf{z}; \mathbf{z}^{(t)})\)，满足： \(\tilde{g}\) 是凸函数。 \(\tilde{g}(\mathbf{z}^{(t)}; \mathbf{z}^{(t)}) = g(\mathbf{z}^{(t)})\)。 \(\tilde{g}(\mathbf{z}; \mathbf{z}^{(t)}) \ge g(\mathbf{z})\) 对所有 \(\mathbf{z}\) 成立（即上近似，保证可行域收缩）。 用 \(\tilde{g} \le 0\) 替代原约束，得到凸近似子问题。 本例中，由于连续松弛下问题已凸，SCA 退化为 求解一个凸优化问题 。但为展示完整流程，我们仍保留 SCA 的迭代结构。 3.2 凸近似子问题 在节点 \(k\) 的第 \(t\) 次 SCA 迭代中，求解如下凸问题（其中整数变量已连续化）： \[ \begin{aligned} \min_ {\mathbf{x}, \mathbf{y}} \quad & f(\mathbf{x}, \mathbf{y}) \\ \text{s.t.} \quad & g_ 1(\mathbf{x}, \mathbf{y}) \le 0, \\ & \tilde{g}_ 2(\mathbf{x}, \mathbf{y}; \mathbf{x}^{(t)}, \mathbf{y}^{(t)}) \le 0, \\ & 0 \le x_ 1, x_ 2 \le 3, \quad 0 \le y_ 1, y_ 2 \le 1. \end{aligned} \] 这里 \(\tilde{g}_ 2 = g_ 2\)（因为已凸）。若 \(g_ 2\) 非凸，常用一阶泰勒展开：\(\tilde{g}_ 2 = g_ 2(\mathbf{z}^{(t)}) + \nabla g_ 2(\mathbf{z}^{(t)})^T (\mathbf{z} - \mathbf{z}^{(t)})\)，其中 \(\mathbf{z} = (\mathbf{x}, \mathbf{y})\)。 3.3 SCA 迭代流程 初始化：选择初始点 \((\mathbf{x}^{(0)}, \mathbf{y}^{(0)})\)，可设为可行点或任意点。 对于 \(t = 0, 1, 2, \dots\)： a. 构造凸近似子问题（如上）。 b. 求解该凸问题，得新解 \((\mathbf{x}^{(t+1)}, \mathbf{y}^{(t+1)})\)。 c. 若 \(\|(\mathbf{x}^{(t+1)}, \mathbf{y}^{(t+1)}) - (\mathbf{x}^{(t)}, \mathbf{y}^{(t)})\| < \epsilon\)（容差），则停止，返回解及目标值 \(f^{(t+1)}\)。 输出最终解作为节点连续松弛问题的最优解。 注意 ：由于连续松弛问题本身凸，SCA 会在一次迭代收敛（因为近似等于原问题）。实际中，若约束非凸，SCA 需多次迭代。 4. 分支定界步骤 节点选择 ：从节点列表中选择下界最小的节点（最可能包含最优解）。 节点求解 ：对该节点，用 SCA 求解连续松弛问题，得到最优值 \(L\)（下界）和解 \((\mathbf{x}^ , \mathbf{y}^ )\)。 剪枝判断 ： 若 \(L \ge\) 当前上界 UB，则该节点不可能有更好解，剪枝。 若解中所有整数变量 \(y_ i\) 恰好为 0 或 1（即整数可行），则更新上界：UB = min(UB, \(L\))，并记录该可行解。 否则，进入分支。 分支 ：选择一个分数整数变量 \(y_ j\)（值不在 {0,1}），创建两个子节点： 左子节点：添加约束 \(y_ j = 0\)。 右子节点：添加约束 \(y_ j = 1\)。 将子节点加入节点列表。 终止条件 ：节点列表为空，或全局下界（所有节点下界的最小值）与 UB 的差小于容忍度。 5. 应用本题的具体计算示例 假设在根节点，连续松弛问题为： \[ \begin{aligned} \min \quad & x_ 1^2 + 2x_ 2^2 + y_ 1^2 + 3y_ 2 \\ \text{s.t.} \quad & x_ 1 + 2x_ 2 + y_ 1 \le 5, \\ & x_ 1^2 + x_ 2^2 - 2y_ 2 \le 0, \\ & 0 \le x_ 1, x_ 2 \le 3, \quad 0 \le y_ 1, y_ 2 \le 1. \end{aligned} \] 这是一个凸问题（目标凸，约束凸），可直接用凸优化求解（如内点法）。解得： 最优解：\(x_ 1^* \approx 0, x_ 2^* \approx 0, y_ 1^* \approx 0, y_ 2^* = 0\)（例如，通过观察：为使目标最小，应令 \(y_ 2=0\)，则 \(x_ 1=x_ 2=0\)，\(y_ 1=0\) 可行）。 目标值 \(L = 0\)。 由于 \(y_ 1^ , y_ 2^ \) 已是整数，该解整数可行，故直接得到可行解，更新上界 UB = 0。此时全局下界也为 0，算法终止，最优解即为 \((0,0,0,0)\)，目标值为 0。 若解非整数 ：假设解得 \(y_ 2^* = 0.6\)，则需分支：创建节点 \(y_ 2=0\) 和 \(y_ 2=1\)，分别求解连续松弛问题，并重复上述过程。 6. 关键点总结 SCA 的作用 ：在 B&B 每个节点求解连续松弛的非凸问题时，将非凸约束局部凸化，使子问题可高效求解。 上下界更新 ：节点连续松弛解提供下界；整数可行解提供上界。 分支策略 ：通常选分数值最接近 0.5 的变量分支，以快速收紧界。 收敛性 ：B&B 确保全局最优（因枚举所有整数组合，但通过剪枝减少计算），SCA 保证连续子问题收敛到局部最优（凸时全局最优）。 扩展 ：对于高度非凸问题，SCA 可能陷入局部解，可结合多起点或全局搜索改进。该方法在工程设计、资源分配等混合整数非线性问题中广泛应用。