Global Optimization via Optimal Decision Trees

摘要

全局优化文献普遍重视将难以处理的优化问题转换为更易处理的形式。 为了达到这一目标的目的，在现有方法中通常仅考虑显式约束和目标函数基于有限的数学表达能力。 这些方法在遇到更广泛且复杂的显式与隐式约束时会遇到局限性。 利用混合整数优化 (MIO) 的显著优势以及最新的机器学习研究成果，我们提出了一种新型的方法：通过构建基于超平面的最佳决策树（OCT-Hs），能够有效学习并解决全局优化问题下的MIO兼容近似模型。 这种新的约束学习方法只需一个有界变量域即可，并且能够处理显性和非显式的约束条件。 我们成功地解决了MIO近似问题，并找到了接近最优且可行的解决方案。 通过一系列投影梯度下降迭代步骤进一步提高了解决方案的质量。 我们在文献中的几个数值基准案例以及一些现实世界的设计问题上进行了测试与验证，并展示了该方法在有效寻优方面展现出良好的前景。

1 引言

全局优化旨在解决以下问题
(1)
其中 f 、 g 和 h 分别是目标函数、不等式约束和等式约束，x 是决策变量的向量。 目标函数和约束与线性或凸优化问题不同，可能符合也可能不符合任何特定的数学结构，并且变量可以是连续的或整数的。
现有的全局优化器将问题 (1) 近似为与有效优化兼容的形式。 这些优化器使用三种主要方法，即基于梯度的方法、外近似和混合整数优化 (MIO) 方法。
CONOPT 和 IPOPT 等流行的非线性求解器使用基于梯度的方法。 这些求解器使用通过有效启发式方法找到的可行解来初始化其求解过程。 然后，他们解决了一系列梯度下降迭代，通过满足 Karush-Kuhn-Tucker (KKT) 条件来确认最优性。 正如 Drud (1994) 所详述的，CONOPT 依赖于一种广义的缩减梯度算法，将约束线性化并求解一系列线性搜索梯度步骤，从而在每个步骤中保持对容差的可行性。 Wächter 和 Biegler (2006) 描述了 IPOPT 的原始双屏障方法。 它使用对数障碍函数将受约束的全局优化问题放松为无约束的优化问题，然后使用阻尼牛顿法将最优性差距缩小到所需的容差。 这些基于梯度的优化器在存在稀疏非线性约束的情况下是高效且有效的，能够在几分钟内解决 1000 个变量数量级的问题和对普通个人计算机的约束，达到局部最优。
另一种方法是外近似方法，由 Horst 等人描述。 （1989 年）。
这种方法通过线性和非线性切割来近似约束来简化全局优化问题，这些切割保留了决策变量 x 上的原始可行集。 这种方法对于具有特定数学结构的约束是有效的（例如，Duran 和 Grossmann（1986）考虑的整数变量的线性和非线性函数的凸性，或者 Bergamini 等人考虑的约束的凹性或双线性。
(2008))，其中存在数学上有效的外部逼近器。 虽然这些方法是有效的，但由于其问题的具体性质，它们发现的商业成功较少。
最后一种方法，一种自然地与整数变量优化相结合的方法，将 MIO 与外部近似耦合。 Ryoo 和 Sahinidis (1996) 提出了一种有效的方法，称为分支和归约方法，它依赖于在决策变量上递归地划分每个约束和目标的域，并通过检查它们的数学原语来限制它们在每个子域中的值。 这种递归分区创建了一个分支定界树，其解决方案具有全局保证 通过分支定界解决 MIO 问题所固有的边界和修剪过程来实现最优性。 这种方法在流行的商业全局优化器 BARON [Sahinidis (2017)] 中取得了成功。
虽然上述方法在解决某些类别的全局优化问题方面是有效的，但这些方法中的每一个都有弱点。 通常，基于梯度的方法依赖于良好的初始可行解，并且在存在整数决策变量时无效。 外部近似方法无法推广到具有一般非线性的全局优化问题。 虽然比外部近似方法更通用，但现有的 MIO 方法由于其组合性质而不能很好地扩展。
也许更重要的是，为了追求数学效率，许多全局优化器对约束的形式施加了额外的约束，要求约束使用可能的数学原语的一小部分。 例如，BARON“可以处理涉及 exp(x)、ln(x)、x α 用于实数 α 和 β x 用于实数 β 的函数”[Sahinidis (2017)]。 来自现实世界的约束并不总是遵循这些形式，并且经常涉及其他类别的函数，例如三角函数、符号和分段不连续函数。 通常不可能将这些函数转换为与现有全局优化器兼容的形式。 这些优化器在处理黑盒的目标和约束时面临更大的挑战。 黑盒约束是不明确的，这意味着它们没有分析表示，例如当约束是模拟的结果时。
在本文中，我们提出了一种使用机器学习 (ML) 将全局优化问题重新表述为 MIO 问题的新方法，利用 Bertsimas 和 Dunn (2017, 2019) 在具有超平面 (OCT-H) 的最优分类树和最优分类树上的工作 具有超平面的回归树（ORT-H）。 该方法解决了具有任意显式和非显式约束的全局优化。 所提出方法的唯一要求是存在于非线性约束中的决策变量 x 子集的有界可行域。
在我们提出的方法中，我们使用 OCT-H 来近似每个超出有效数学优化范围的约束。 更具体地说，每个非线性约束 g i (x) ≥ 0 由在数据 {(x̃ k , I(g i (x̃ k ) ≥ 0)), k ∈ [n]} 上训练的 OCT-H T i 近似，其中 x̃ k 是决策变量的结果，I 是指示函数，g i (x̃ k )是在 x̃ k 处评估的约束的左侧。 因此，树 T i 近似于约束 g i (x) ≥ 0 的可行空间，预测（有一些错误）决策变量的结果是否满足约束。 该方法还扩展到逼近每个非线性等式 h j (x) = 0，并通过 ORT-Hs 逼近非线性目标函数。
近似树允许对底层约束进行自然的 MIO 近似。 OCT-H 的每个可行叶都通过定义半空间交集的决策路径（即多面体）到达。 因此，可以使用析取约束将约束近似为近似 OCT-H 的可行多面体的并集。 我们解决了原始问题的这种高效 MIO 逼近，以获得接近可行和接近最优的解决方案，然后使用基于梯度的方法将解决方案修复为可行和局部最优。
相对于其他全局优化方法，所提出的方法具有几个优势。 它与问题中的约束形式无关； 只要我们可以查询一个样本 x̃ 对一个约束是否可行，我们就可以将约束嵌入到 MIO 近似中。 一旦使用决策树学习了约束，与解决原始全局优化问题相比，得到的 MIO 近似的求解时间很短。 所提出的方法还可用于从可能不来自任何已知函数、模拟或分布的数据生成约束。 这使我们能够同时学习复杂现象的物理学，例如但不限于社会动力学模型或偏微分方程的解，并将它们嵌入到优化问题中。
在这项工作中，我们展示了我们的全局优化方法，该方法在我们的优化器 OCT-H 中实现，用于全局优化 (OCT-HaGOn)，发音为“八边形”。 我们通过考虑具有显式非线性约束的全局优化问题来证明它的前景。 这使我们能够使用可用的基准来量化我们的方法相对于现有全局优化器的性能。 此外，我们对基准中的所有非线性约束进行了近似，而不管它们的有效优化可表示性如何。 所提出的方法扩展到混合整数凸方法，我们将有效优化的非线性约束（例如，二次、二阶圆锥、对数和指数约束）直接嵌入到 MIO 公式中，只要这些约束得到底层求解器的支持 .
1.1 机器学习在优化中的作用
优化在训练 ML 模型中的作用是众所周知和研究的。 最近的文献综述 [Gambella 等人。 （2021），孙等人。 (2020)] 调查了用于各种 ML 应用的数学优化和启发式方法的前景。
但是，我们感兴趣的是上述的反面，特别是如何将 ML 用于优化目的，特别是解决不能自然地被视为有效优化问题的问题。
使用 ML 方法来提高计算效率是有先例的。 一个突出的例子是使用 ML 来加速非线性系统的模拟，例如计算流体动力学中的那些 [Kochkov 等人。 (2021)]，分子动力学 [Gastegger 等人。 (2017)] 和量子力学 [Morawietz 和 Artrith (2021)]。 之前有一些使用 ML 来加速优化的工作，例如 使用贝叶斯优化 [Frazier (2018)] 或神经网络 [Tagliarini et al. （1991）]。 虽然这些表明 ML 驱动的优化在理论上是可行的，但所提出的方法在计算上是昂贵的，并且对于现实世界的问题是不可扩展的。 ML 在优化中的一个有趣的并行用途是解释最优解，其中 ML 用于理解由不同参数下的优化问题产生的最优策略（即决策变量的全部或子集的结果）[Bertsimas and Stellato (2021) )]。
在这项工作中，我们使用 ML 来找到全局优化问题的最佳解决方案，这些问题涉及具有任意数学原语的显式约束和不显式的黑盒函数。 为此，ML 用于两种能力范围内的约束学习。
第一个能力是加速对已知模型的优化。 当模型和/或约束已知但它们的使用被禁止时，例如 在显式但非线性和非凸约束的情况下，学习器用于创建更有效地用于优化的代理。 二是在建模方面。 当数据可用但模型和/或约束是黑匣子时，学习者充当数据的插值者，并允许将数据中的模式嵌入到优化中。
在这两种能力中使用 ML 进行优化需要近似的 ML 模型是可优化表示的。 虽然许多类型的 ML 模型可以有效地查询和准确，例如许多类型的神经网络和高斯过程，但它们不能明确地嵌入到结构化优化中。 之前的工作已经认可使用约束学习方法优化数据驱动约束的潜力。 比格斯等人。 (2017) 和 Mišić (2020) 使用树集合的预测作为优化问题的目标函数，因为树特征的子集是决策变量。 马拉尼奥等人。 （2021 年）更进一步，提出了一种更通用的数据驱动优化方法，该方法利用决策树以及其他与 MIO 兼容的 ML 模型，例如支持向量机和神经网络。
上述决策树在优化中的应用范围有限。
比格斯等人。 （2017 年）和 Mišić（2020 年）将他们的应用限制在数据驱动目标函数的优化上，其中决策树用于回归连续感兴趣的数量。 而 Maragno 等人。 （2021）对数据驱动的约束使用约束学习，我们也使用约束学习来近似难以处理的显式和非显式约束，我们有能力对潜在约束进行采样以生成数据。 因此，我们提出了一个全局优化框架，可以适应任意显式、隐式和数据驱动的约束，在回归和分类设置中利用决策树。
虽然可以使用其他与 MIO 兼容的 ML 模型进行全局优化中的约束学习，如 Maragno 等人提出的。 （2021 年），我们选择依赖 ORT-H 和 OCT-H，因为它们是可调的、准确的和可解释的 [Bertsimas and Dunn (2019)]。
在以下部分中，我们展示了一种利用最优决策树的全局优化方法在使用 ML 加速优化和建模方面取得了重大进展，使用树的自然和直观的 MIO 表示。

1.2 回顾决策树
决策树是一种流行的预测 ML 方法，它根据数据的特征对数据进行分层分区。 根据落入节点的数据的最常见标签，将有限可能标签集中的类标签分配给树的每个叶节点。
在已知数据 (x, y) 上生成决策树 T ∈ T 的优化问题如下：
()
其中cp是一个复杂性惩罚参数，它试图在测试数据的误分类误差和树的复杂性（深度和广度）之间取得平衡。
一旦经过训练，就会查询决策树以预测具有已知特征但类别未知的测试点的类别。
决策树由 Breiman 等人开创。 （1984）随着分类和回归树（CART）的出现。 但是，CART 是一种自上而下的贪婪方法来生成决策树。 每个拆分只是局部最优的，因为拆分是从根节点开始在每个新拆分的子节点上递归进行的。 Bertsimas 和 Dunn (2017) 在最优分类树 (OCT) 上的工作提高了决策树探索特征空间的能力。 OCT 利用 MIO 和局部搜索启发法来减少相对于 CART 的错误分类错误，而不会过度拟合。 此外，OCT 更易于解释，因为它们可以实现与 CART 生成的树类似的错误分类错误，但复杂性要低得多。
OCT-Hs 通过允许超平面拆分来概括 OCT，即一次拆分多个特征。 与 OCT [Bertsimas and Dunn (2019)] 相比，OCT-H 可以以更高的精度和更低的复杂度解决分类问题，并且由于非线性约束中决策变量的耦合，在优化设置中更具表现力。 因此，我们的方法专门利用 OCT-H 来近似约束。
ORT-Hs 将 OCT-Hs 扩展到回归问题，其中感兴趣的预测是连续的，即 ỹ ∈ R。ORT-H 的每个叶子都包含一个连续预测 ỹ 作为线性回归 x 在叶子的域中。
在逼近非线性目标函数时，ORT-Hs 特别有用。
我们依靠 Interpretable AI (IAI) 公司的软件以 OCT-Hs 和 ORT-Hs [Interpretable AI, LLC (2022)] 的形式构建、训练和存储问题数据。

2 贡献

在本文中，我们提出了一种全局优化方法，该方法可以推广到有界 dom(x) 上的显式和非显式约束和目标函数。 我们的具体贡献如下： 1. 为了约束学习的目的，我们引入了一组有效地采样约束的方法。 我们利用现有实验设计 (DoE) 技术的协同作用，但还设计了一种新的基于 k-最近邻 (kNN) 的采样技术，用于对显式和隐式约束的近可行点进行采样。
2.我们使用OCT-Hs和ORT-Hs学习非线性目标、不等式和等式的可行空间。
3. 我们使用决策树的析取表示对全局优化问题进行 MIO 近似，并使用 MIO 求解器解决它们。
4. 我们设计了一种投影梯度下降法来检查和修复来自 MIO 近似的接近可行和接近最优的解决方案。
5. 我们将我们的方法应用于一组基准问题和现实问题，并展示其在寻找全局最优值方面的性能。
2.1 论文结构
在第 3 节中，我们详细介绍了我们的方法，然后在第 4 节中给出了一个演示示例。在第 5 节中，我们在文献中的一些基准问题上测试了我们的方法，并将我们的结果与最先进的全局优化进行了比较 BARON、IPOPT 和 CONOPT 等工具。 在第 6 节中，我们使用我们的方法优化两个航空航天系统，其中一个无法通过现有的优化工具解决。 在第 7 节中，我们讨论了未来研究的结果和途径。 我们在第 8 节总结我们的发现和贡献。

3 方法

任务：将下面的文本进行同义改写以降低重复率。

输入文本

输出内容

4 示范例子

基于 Duran 和 Grossmann (1986) 的修正模型构建了该混合整数非线性规划问题。 为了演示目的,我们将原始非线性目标函数替代为线性形式,同时确保变量 y 与 x 的关联关系得以保持一致性。

5 计算实验benchmark

我们采用 OCT-HaGOn 方法应用于文献中的部分优化问题，并与现有全局优化器进行对比实验。 OCT-HaGOn 软件包可通过附录 A.1 提供的链接获取详细说明。 请参阅附录 A.2 以获取所使用优化器及其功能的完整信息。 在本节中提出警告：由于该方法具有近似性质，在不同随机重启过程中可能会产生不同的最优解结果。 实践中发现，在大多数情况下该方法能够稳定地达到相同最优值，并且随机重启过程有效缓解了因局部最优而产生的问题。

随后我们将该方法应用于 MINLPLib 中的五个基准测试案例（由Bussieck等人在2003年提出）。 为了便于比较分析，默认将结果与商业求解器BARON（Sahinidis, 1996）的输出进行对比研究。 基准测试中的约束类型及数量具体数据可见于表3所示表格形式，并已由表4总结了实验结果表现情况。

实验表明,OCT-HaGOn 方法能够成功解决所有五个基准测试案例并获得全局最优解,其结果与BARON求解方案完全一致。 然而,OCT-HaGOn 方法在求解时间上明显慢于BARON,这一现象并不令人意外,因为这些小规模测试案例仅包含少量特殊的数学原语约束条件,而无需考虑复杂的整数规划变量组合等问题因素影响下的复杂性提升

为更全面地评估该方法的有效性,我们进一步选择了MINLPLib中的六个中等规模基准测试案例（具体参数见表5）。 此外,为了提高求解效率,还将三个商用求解器IPOPT、CONOPT及BARON纳入对比范围分析研究

经过系统运行后发现,OCT-HaGOn 方法对于这六个较大规模测试案例中共成功解决了其中四个实例并找到了全局最优解（具体数据参考表6所示表格形式）。

表5 和 表6 分别展示了详细的数据对比结果

6 真实算例

除了基准之外，我们还在两个复杂程度不同的航空航天问题上测试了我们的方法。 我们首先从工程文献中解决了一个基准，以表明该方法可以解决实际问题。 然后，我们将 OCT-HaGOn 应用于无法使用其他全局优化器解决的卫星在轨服务问题。
6.1 减速器问题
减速器问题是 Golinski (1970) 提出的非线性优化问题。
该问题旨在为飞机发动机设计一个齿轮箱，除了 x ∈ R 7 上的可变边界外，还要遵守 11 种规格、几何形状、结构和可制造性约束。 我们将我们的方法应用于标准形式的附录 A.3 中所写的问题。
table 7
在表 7 中，我们比较了减速器问题的不同解决方案。 OCTHAGON 和 IPOPT 都击败了 Lin 和 Tsai（2012 年）最知名的最优值。 此外，如附录 A.3.1 所示，OCT-HaGOn 允许我们在 PGD 算法的 4 次迭代后实现所有误差为零的约束，而其他两种方法的误差容限很小但非零。
IPOPT 能够在 4.2 秒内解决这个特定的非线性程序 (NLP)，明显快于需要 32.6 秒的 OCT-HaGOn。 然而，这需要放宽 x 3 的完整性。 对于这个特殊问题，这并不重要，因为 x 3 的下限是其最佳值 17。但是，IPOPT 通常不能用于解决 MINLP。
在实际操作中，我们想注意潜在非线性约束的 OCT-H 近似中不同级别的复杂性。 一些约束虽然看起来很复杂，但具有低复杂度的树逼近器。 考虑以下约束 g 5 (x) ≥ 0 及其相关的 OCT-H 逼近器。
OCT-H 模型具有单个超平面，能够在 613 个样本上以完美的精度逼近相关 dom(x) 中的函数，如图 6 所示。在有界 dom(x) 内，非线性约束因此被简化 为线性约束。
然而，并不是所有的约束都可以直接通过多面体的并集来表示。
考虑目标函数，它是一个 5 阶多项式 (20)。 在这种特殊情况下，目标由具有 19 个叶子的 ORT-H 表示，每个叶子都定义了 x 上的唯一可行多面体。 图 7 显示了树的截断版本，有四个叶子可见。在 532 个样本上，近似值的 1 - R 2 误差为 1.4 × 10 -5。
6.2 卫星在轨服务 (OOS) 调度优化问题
我们在先前未解决的卫星在轨服务 (OOS) 调度优化问题上测试我们的方法。 卫星 OOS 是一项未来技术，旨在通过允许自主服务航天器在轨道上进行维修或加油来提高现有和下一代卫星的寿命 [Luu and Hastings (2020)]。 OOS是一个作用于高度非线性动态系统的困难调度问题。 通过我们的方法解决这个问题是一个很好的问题，因为在其完整的 MINLP 形式中，该问题是具有非线性等式约束的非凸组合优化问题。 此外，由于决策变量的范围存在 11 个数量级的差异，因此在数值上具有挑战性。 在本文之前，它仅通过枚举来解决 [Luu and Hastings (2020)]。 请参阅附录 A.4 了解有关完整约束列表的更多详细信息； 下面是对该问题的简要总结。
动力学问题是在同一轨道平面上的客户卫星之间移动服务卫星的轨道力学。 轨道转移涉及使用机载推进器
figure 6
figure 7
使服务商进入与客户卫星不同的轨道高度，称为相位轨道，以减少服务商和客户之间的真实异常（以弧度为单位的角度相位差）。 然后，服务商将自己推回客户的轨道，在正确的时间和空间位置与客户卫星相遇，同时遵守能量、动量和质量守恒。 调度问题包括选择服务每个客户卫星的最佳顺序（离散决策），以及选择最佳相位轨道（连续决策）。
在本节中，我们考虑一个简单的 OOS 示例。 我们安排一颗服务卫星为轨道上的 7 颗客户卫星加油，使用机载推进器在客户之间飞行。
每个客户需要不同数量的燃料，我们限制服务商在 0.35 年内完成任务，目标是最小化服务商的湿质量（干质量和燃料）。 问题参数见表 8。
table 8
图 8 中显示的燃料需求是随机生成的，反映了客户卫星的燃料需求可能分布，这些卫星是同一星座的一部分，并在前一个时间点同时发射。
在解决 OOS 问题时，我们做出以下现实的简化假设，尽管我们的方法确实扩展到更一般的情况。 服务卫星通过外部火箭交付给第一个客户端，并使用自己的推进器在后续客户端卫星之间使用霍曼传输。 相对于机动步骤而言，推进和加油步骤所花费的时间可以忽略不计。 所有客户卫星都在同一轨道平面上，在同一高度，并且在轨道周围均匀分布。
figure 8
服务 n s = 7 个客户端的初始问题有 141 个变量，其中 n 2 s = 49 个二进制变量表示服务顺序。 非线性约束中的连续决策变量从上到下都有界，以与第 3.1 节中定义的 OCT-HaGOn 兼容。 模型中有 41 个线性约束，代表系统动力学的一个子集。 在线性约束之上，我们有 10(n s − 1) = 60 个非线性约束，它们都是等式的。 约束在附录 A.4 中有详细介绍。
我们通过两种方式解决问题。 首先我们通过 OCT-HaGOn 解决它。 由于我们明确知道这个问题的约束，我们使用第 3.4.3 节中描述的 ORT-H 近似方法，将非线性与约束的仿射分量分离以提高准确性，并为每组循环约束训练一棵树。 由此产生的 MIO 问题有 999 个连续变量和 349 个二元变量，以及 3650 个线性不等式和 286 个线性等式。
其他全局优化器，如 CONOPT、IPOPT 和 BARON 不能用作 OCT-HaGOn 在这个特定问题上的基准。 由于 OOS 是一个混合整数问题，因此基于梯度的优化器（例如 CONOPT 或 IPOPT）变得无效，并且 BARON 不支持轨道动力学中存在的非线性。 相反，我们通过将可能的转移轨道限制在 1 km 的区间内，成功地离散了约束中的非线性子集。 这将 OOS 问题的复杂性降低为 MI-双线性问题，我们可以通过 Gurobi 的 MI-双线性优化器 [Gurobi Optimization, LLC (2021)] 解决该问题。 MI-双线性表示有 394 个变量，其中 289 个变量是二进制的。 60 个非线性约束中的 36 个转化为双线性等式，而其余的则转化为线性约束。 离散化问题的解决方案是全局最优的，但肯定比完整 MINLP 公式的全局最优更差，因为轨道高度的离散集比连续集更具限制性。 但是，该解决方案足够细化，可以作为 OCT-HaGOn 的良好基准。
table 9
结果如表 9 所示，并在图 9 中以图形方式显示。首先，我们寻找两个重要的影响，MI-双线性解决方案很好地证明了这一点，并且在图 9 中很容易看到。第一个是最好用 最大的燃料需求首先，因为较轻的服务商在后续客户之间转移所需的燃料较少。 第二是在任务开始时花费更多的时间转移比在结束时花费更多的时间更好，因为当服务人员较轻时转移花费的燃料更少。 MI-双线性解决方案中机动时间和燃料成本的总体下降趋势表明了这一点。
虽然 OCT-HaGOn 正确捕获了最佳卫星时间表，但它无法找到最佳相位轨道集。 通过观察图 9a 中 OCT-HaGOn 解决方案中的机动时间的平坦曲线很容易看出这一点，这与图 9b 中离散化解决方案中看到的递减曲线相比是次优的（总燃料 < 0.1%）。 此外，由于存在许多非线性等式，PGD方法无法减少不可行性和最优性差距，陷入局部最优。 在最大树深度为 6 的情况下，该解在所有非线性约束上具有 3.5 × 10 -3 的最大相对误差和 2.5 × 10 -4 的平均相对误差。 虽然这对于概念设计目的来说足够准确，但需要更高的准确度和更稳健的修复程序。
在求解时间方面，OCT-HaGOn 使用 8 核 Intel i7 处理器的个人计算机求解时需要 14.2 秒。 这包括所有采样、评估、训练和优化步骤。 相比之下，MI-双线性解决方案仅用于优化步骤需要 17.7 秒。 这是在一位经验丰富的工程师花费两天时间的基础上，重新制定问题以与现有的有效优化公式兼容。
尽管 OCT-HaGOn 对 OOS 问题的解决方案不是最优的，但我们认为它有力地证明了该方法的能力和前景，特别是考虑到问题的复杂性。 值得注意的是，OCT-HaGOn 成功地找到了最佳卫星服务时间表，这可以说是该问题中最重要的决定。
尽管问题是病态的，决策变量值有 11 个数量级的差异，并且有 60 个非线性等式约束耦合了大多数决策变量。 此外，这种复杂的全局优化问题的离散化重新表述一般可能不存在。 即使他们这样做了，由于这种重新制定的组合性质，它们也可能难以处理。 据我们所知，这使得 OCT-HaGOn 成为文献中唯一可以直接解决此问题的全局优化工具。
figure 9

7 讨论

在本节中，我们将讨论结果和局限性，并提出未来工作的领域。
7.1 局限
所提出的方法在解决各种全局优化问题方面显示出希望，但它是一项正在进行的工作。 在这里，我们详细介绍了本文中实现的方法的一些限制； 在作者看来，我们按照从最重要到最不重要的顺序列出这些内容。
虽然 OOS 示例表明该方法可以解决决策变量之间高度非线性耦合的问题，但涉及大量活动变量的单个非线性约束将在 OCT-H 训练时间以及准确性方面带来挑战。 树的近似值。 树的准确性直接影响近似最优值的质量。 如第 3.4 节所述，可分离性可以部分缓解此问题，方法是允许将许多非线性约束分解为线性分量并通过一系列 ORT-H 更好地逼近。
此外，我们还没有严格测试求解时间和质量如何随着变量和非线性约束的数量以及非线性约束的稀疏性而变化。
鉴于 OCT-HaGOn 的性能取决于配方，通过预先考虑需要在何处使用 OCT-H 近似值并明智地使用它们的配方，在求解时间和质量方面都有很多收获。 我们希望当优化问题中的大多数约束是线性或凸的并因此是有效的时，OCTHaGOn 特别有效，并且约束学习方法是在其他难以处理的约束上实施的，具有相当严格的决策变量界限。
如第 5 节所述，所提出的方法不能保证全局最优性，因为它是近似的。 因此，该方法的不同迭代会生成局部最优的高性能解决方案，但不能保证全局最优，例如 BARON 提供的那些。 此外，虽然该方法不知道约束是显式的还是隐式的，但到目前为止，该方法仅在显式约束上进行了测试。
这是因为黑盒函数的数值基准不可用，因为它们与其他现有的全局优化器不兼容。
该方法的一个隐含假设是难以评估的约束可以快速评估； 如果此假设不成立，则可能需要更改实现以适应计算要求。 此外，PGD 方法要求约束函数是自可微分的。 虽然这是一个适度的假设，但约束评估可能不允许 AD。 这可以通过近似地找到梯度来克服，例如 通过有限差分，但目前尚未实现。
概述了这些限制后，我们继续提出改进该方法的未来工作。
7.2 决策树训练
OCT-HaGOn 的大部分求解时间由树训练步骤占用。 虽然训练的计算成本与约束的数量呈线性关系，但第 5 节中的基准测试结果表明，训练时间可能会根据底层约束的复杂性而发生巨大变化。 在本节中，我们将讨论几种管理计算时间的方法。
训练时间减少的第一个潜在来源来自调整表 1 中描述并在 IAI 中实现的基本树参数。 为此，我们可以通过减少最大深度和增加 minbucket 参数来降低树的复杂性。 否则我们可以修改树训练中随机重启的次数。 由于用于生成 OCT-H 和 ORT-H 的局部搜索方法是局部最优的，我们可以通过改变候选树的随机重启次数以及随机超平面重启的次数来减少训练时间。 然而，这两种方法在 OCT-H 近似的准确性方面都有明显的负面权衡。 一般来说，我们发现使用 10 次随机树重新启动和 5 次超平面重新启动，如表 1 中的基本树参数所述，我们能够生成足够准确的决策树，同时又足够高效以用于实际情况。 时间优化设置。
减少训练时间的一个潜在的大来源是识别问题中常见的约束形式。 如果非线性约束 g(u i ) ≥ 0 使用不同的变量 u i ⊂ x, i ∈ [k] 重复 k 次，则可以联合逼近这些约束。 具体来说，我们可以训练单个 OCT-H 来近似域 ∪ ki=1 dom(u i ) 上的约束。
然后，我们将 k 个约束表示为具有不同变量 u i 的树的析取表示的 k 个重复。 在本文中，第 5 节中的许多基准测试都证明了这一点一种重复行为，但我们将约束视为黑匣子，不利用潜在的加速。 然而，对于 OOS 问题，我们使用我们对约束的知识来联合训练树。
在显式约束下利用数据的无噪声特性来加速训练过程也有潜力。 目前，训练时间在数据特征数量（即每个约束中的变量数量）中呈指数级增长，使得 x 中密集的约束的树近似变慢。 人们可以通过尝试一种贪婪的方法来加速训练过程，以类似于 CART 的局部最优方式构建具有超平面的树 [Breiman 等人。 (1984)]，而不是通过局部搜索启发式的全局最优方式 [Bertsimas and Dunn (2019)]。 另一种方法可以设计特定的局部搜索启发式，以动态方式采样约束和训练树，以加快训练并减少近似误差。
考虑到计算架构，还可以进行一些改进。
由于单独的约束是单独学习的，训练过程可以并行完成，充分利用可用的计算资源。 这些树一旦训练就可以有效地存储，允许在相同优化问题的不同实例中使用相同的树。 这避免了重新训练树的需要，也避免了必须存储训练树所需的样本，从而节省内存。 我们为开发目的开发了此类方法。
7.3 混合整数优化近似的复杂性
如前所述，求解全局优化问题的 MIO 近似的复杂性是适中的，因为与 Gurobi 或 CPLEX 等商业求解器的能力相比，MIO 的规模很小。 然而，重要的是要注意 MIO 的复杂性如何根据非线性约束的数量和近似树的深度进行扩展。
我们首先考虑构成 MIO 近似所需的辅助变量的数量。 用于逼近非线性约束的变量数量是描述 x 的可行空间的析取多面体数量以及约束中决策变量数量的线性函数。 更明确地说，总人数逼近问题所需的二元变量与决策树中的叶子数呈线性关系，相当于
（）
其中 L f 、 L i,1 和 L j 分别是目标逼近树、不等式逼近树和等式逼近树中的可行叶集。 此外，我们引入了一些连续的辅助变量。 辅助变量的数量相当于：
（）
其中 p i 是第 i 个约束中的变量数。 一棵树的最大叶子数为 2 d ，所以在最坏的情况下，问题中辅助二元变量的数量为 O(2 d (1 + |I| + |J|))，辅助二元变量的数量为 连续变量为 O(2 d (1 + |I| + |J|)dim(x))，相当于由 x 的维数增加的二元变量的数量。 然而，在实践中，并没有看到这种最坏的情况，因为在训练过程中对树进行了修剪，并且近似的难以处理的约束在 x 中是稀疏的。
析取约束的数量更复杂，因为不能保证树的深度是一致的，而且我们不知道分类树的先验叶子的比例。 然而，如果我们假设每棵树都有一个深度 d i ，我们会得到以下最坏情况下的析取约束数量，不包括连续辅助变量的单变量边界约束：
（）
以上意味着 MIO 中的析取约束的数量为 O(2 d d(1 + |I| + |J|))，其中 d 是所有近似树的最大深度。 这显示了树深度对 MIO 复杂性的超指数影响，其中对更高准确性的需求可能会导致大量计算成本。 但是，对于我们在本文中考虑的中小型实例，这是一个可以接受的折衷方案。
此外，变量的数量随着约束的数量线性增长，这可能导致 OCT-HaGOn 的求解时间在最坏的情况下呈指数增长。
与线性或凸优化问题不同，平均求解时间可能与约束数量呈次线性关系，OCT-HaGOn 预计平均具有 由于近似值的组合性质，相对于约束数量的超线性求解时间。 我们还没有观察到表现出这种指数时间行为的问题，这可能是因为近似约束的稀疏性，也可能是由于公式的局部理想性。 然而，当 OCT-H 近似应用于大规模问题时，需要研究树的复杂性。
7.4 凸混合整数方程的扩展
OCT-HaGOn 方法允许我们生成无法有效优化的非线性约束的有效 MIO 表示，即不是线性的或凸的。 它开辟了将这些近似包含在更一般的 MI-凸公式中的可能性，其中通过直接插入或通过外部近似来保留有效的凸非线性约束，而通过 OCT-Hs 来近似难以处理的约束。 这将显着提高我们方法的速度和准确性。
7.5 对比big-M Free 和 big-M Disjunctive
虽然 OCT-HaGOn 实现了 3.4 节中描述的决策树的局部理想、大 M 自由析取表示，但由于添加了大量辅助变量，大 M 表示可能通过商业求解器更快地求解 在大 M 自由方法中。 解决由 big-M free 方法产生的局部理想但更大的 MILO 是否更有效，或者由 big-M 方法产生的更小但非理想的 MILO 是否更有效，还有待测试 .
虽然我们没有明确的证据证明这两种方法的相对性能，但作者的直觉会指向基于问题大小的权衡； 当解决具有更多非线性约束的更大全局优化问题时，大 M 方法可能会优于无大 M 方法。

7.6 改进的随机重启。
如前所述，由于约束学习方法是近似的，因此可能需要随机重新启动来获得对局部最优解的质量的信心。 目前，OCT-HaGOn 的随机重启涉及在所有非线性约束上重新训练树，并同时替换它们。 更好的方法是训练一组每个约束上的树，并置换树的近似值以生成问题的一组 MI 近似值。 每个排列的解决方案将为新的 PGD 序列提供接近最优的种子。 这将减少随机重新启动的计算负担，并产生更高性能的解决方案群体，从而增加对该方法的信心。
7.7 数据驱动约束的优化
存在全局优化上下文，其中约束由数据通知，而无需访问底层模型。 一些例子是工程系统设计中的模拟数据、过去实验的结果或人为数据，如临床数据和消费者偏好。 理论上，OCT-HaGOn 能够从任意数据中学习约束，并将这些模型集成到优化设置中。 然而，我们还没有进行实验来确认 OCT-HaGOn 在使用数据驱动约束的实际决策中的有效性。 这种通过约束学习将数据嵌入到优化中对医疗保健和运筹学等多个领域具有重要意义。
7.8 其他与 MIO 兼容的 ML 模型的集成。
虽然本文侧重于使用 OCT-Hs 和 ORT-Hs 进行约束学习，但还有其他具有优化兼容表示的 ML 模型。 马拉尼奥等人。
(2021) 探索使用线性模型、决策树及其变体以及多层感知器从数据中学习约束和目标的可能性。 OCT-HaGOn 可以轻松扩展以适应其他 MIO 可表示的 ML 模型。

8 结论

在本文中, 我们开发出一种基于可解释 ML 和高效 MIO 的直观新方法来解决全局优化问题. 该方法通过决策树实现了自然析取表示, 并分别使用 OCT-Hs 和 ORT-Hs 逼近显式与隐式非线性约束. 我们通过理论分析与实验验证表明, 在现有求解器技术下实现解析 MIO 近似能有效解决问题, 并提供接近最优且可行的结果. 随后采用梯度优化方法对我们的解决方案进行了改进以获得可行性和高性能的结果. 通过实验对比分析表明, 在多个基准测试用例与实际应用场景中 OCT-HaGOn 的性能表现优于当前最先进的全局优化算法.
该系统不仅提供了一个创新性的工具, 而且展示了其独特的优势: 基于树的结构能够处理显式约束以及从任意数据中学习隐式约束. 据了解, 它是当前文献中最通用的全局优化方法之一, 因为它无需对约束或变量施加严格的数学形式化要求. 只需要定义有界决策变量域上的非线性约束即可应用本方法. 这一特点使得它特别适合那些虽然缺乏有效的数学建模工具但又渴望通过优化提升效率的应用领域.