BILBO：BILevel 贝叶斯优化

BILBO: BILevel Bayesian Optimization

BILBO：BILevel 贝叶斯优化

https://arxiv.org/pdf/2502.02121

摘要

双层优化具有两层优化结构的特征，其中上层问题受到下层最优解的约束，这类结构在现实问题中十分普遍。由下层最优解带来的约束带来了显著挑战，尤其是在存在噪声、带有约束以及无导数的情况下，因为重复进行下层优化效率低下，且预测的下层解可能并非最优。我们提出了双层贝叶斯优化（BILevel Bayesian Optimization, BILBO），这是一种用于具有黑箱函数的一般双层优化问题的新型贝叶斯优化算法。BILBO能够同时优化上层和下层问题，无需像现有方法那样重复执行下层优化。BILBO通过对基于置信区间边界的可信集进行采样，从而限制下层解的次优性。此外，BILBO在每次迭代中仅选择一次函数查询，其查询选择策略结合了对下层估计解的不确定性，并包含一种条件重分配机制，以促进对下层目标函数的探索。BILBO的性能在理论上得到了保证，对于常用的核函数具有次线性遗憾界，并在多个合成问题和实际问题上进行了实验验证。

1. 引言

许多现实世界的问题涉及具有两层优化结构的分层决策过程。上层所做出的决策会影响下层的优化，而下层的最优解又反过来约束上层的决策。双层优化能够有效建模此类分层结构，从而分析这些相互依赖的问题。图1展示了一个简单的双层优化示例。双层优化的应用范围广泛，从机器学习（例如超参数优化、元学习）到经济学问题（例如定价策略、收费设置）（Beck & Schmidt, 2021）。在能源管理中，电力供应商制定最优电价策略（上层），而消费者则根据电价优化自身的用电需求（下层）。类似地，在投资领域，经纪商设定不同资产类别的费用以最大化自身收入（上层），而投资者则优化其投资组合以实现预期收益和风险平衡（下层）。在这两类问题中均已应用了双层优化方法（Shu et al., 2018; Leal et al., 2020），通常采用嵌套框架，并在下层使用线性求解器。这种方法可能限制实际效果，但这是由于双层优化本身固有的复杂性所致。即使仅包含线性约束和目标函数，可行解的集合仍可能是非凸且不连续的（Kleinert et al., 2021）。对于非线性约束而言，下层的 ε-可行解也可能导致最终解与真正的双层最优解相差甚远（Beck et al., 2023）。

经典方法（Bard & Falk, 1982; Bard & Moore, 1990）依赖于简化假设，如线性或凸性。近年来，元建模方法（meta-modeling methods）采用代理模型，例如 BLEAQ（Sinha et al., 2013），使用二次近似将上层点映射到下层解。我们关注元建模方法而非基于梯度的方法，以应对可能包含噪声观测、双层均为无导数函数、约束条件以及离散变量的一般性双层问题。

贝叶斯优化（Bayesian Optimization, BO）是一种流行的元建模方法，已被应用于双层优化的嵌套框架中（Kieffer et al., 2017）。该嵌套框架通过贝叶斯优化来优化上层问题，同时在每个上层查询点处单独优化下层问题。然而，这种重复的下层优化效率低下，且通常假设存在梯度信息。

贡献。我们提出双层贝叶斯优化（BILevel Bayesian Optimization, BILBO），这是一种针对具有黑箱函数和约束的一般性双层问题的新型贝叶斯优化算法。与现有嵌套式双层BO框架不同，BILBO同时优化上下两层。这种设计引入了新的挑战，例如查询点可能对应次优的下层解，以及对下层解估计的不确定性。为应对这些挑战，我们引入了BILBO的关键组件：

• 基于置信区间边界的可信集，用于在理论保证下缩小搜索空间。具体而言，通过对可信集内的下层解进行采样，可限制下层目标函数的遗憾（regret），从而有效控制下层次优性对上层优化的影响。

• 函数查询策略，该策略纳入了对下层估计解的不确定性，并引入查询点的条件重分配机制，以更有效地评估下层目标函数。该策略在利用已有下层解估计和探索以改进估计之间实现平衡。我们证明该策略可带来查询点的瞬时遗憾界。

我们进一步证明，BILBO对于常用核函数具有次线性的累积遗憾和简单遗憾界，并在多个合成问题和真实世界问题上通过实验验证了其有效性。代码已公开于 https://github.com/chewwt/bilbo/，符号表见附录A。

2. 相关工作

双层贝叶斯优化。如引言中所述，大多数现有的双层贝叶斯优化方法仅将贝叶斯优化（BO）应用于上层问题，并依赖在每个上层查询点处重复执行下层优化（Kieffer et al., 2017；Islam et al., 2018；Wang et al., 2021）。Dogan & Prestwich（2023）提出了一种采集函数，在上层优化过程中以下层解为条件，以实现上下两层之间的信息传递。然而，这些嵌套式方法需要梯度信息来估计或优化下层解，因此不适用于无导数的双层问题。Fu 等人（2024）为一种嵌套双层框架提供了理论保证，该框架在下层使用随机梯度下降，上层使用贝叶斯优化。但由于依赖下层梯度，其理论分析无法推广到一般的无导数双层问题。相比之下，我们提出的方法能够处理黑箱、无导数的双层问题，且我们的理论分析适用于此类场景。

对嵌套框架的一个例外是最近Ekmekcioglu等人（2024）在arXiv上发表的并行工作。然而，该方法缺乏理论保证，且无法处理约束条件，而我们提出的算法则能够处理这些情况。

约束贝叶斯优化。已有多种约束贝叶斯优化算法被提出（Gardner et al., 2014；Gelbart et al., 2014；Hernández-Lobato et al., 2016；Eriksson & Poloczek, 2021；Takeno et al., 2022）。特别是，Xu 等人（2023）和Nguyen 等人（2023）均引入了基于置信区间的可行集乐观估计方法，前者提出了不可行性声明机制，后者则设计了适用于解耦场景的函数查询策略。这些对可行集的估计有助于引导采样朝向可能可行的点，从而提升采样效率。与约束优化相比，双层优化面临更多挑战，因为它需要优化一个独立的下层问题，而该问题的最优解是未知的，且通常只能被次优地估计。

与其他优化问题的比较。尽管一些优化问题，例如鲁棒优化（Bogunovic et al., 2018；Kirschner et al., 2020）和复合目标优化（Astudillo & Frazier, 2019；Li & Scarlett, 2024），分别涉及额外的随机变量或复合目标函数，但它们仍属于单层优化问题。相比之下，双层优化具有两层分层结构，其中上层问题受下层最优解的约束，因此在本质上与上述其他问题设置存在根本差异。

3. 预备知识

4. 双层贝叶斯优化
我们的方法，称为双层贝叶斯优化（BILevel Bayesian Optimization，BILBO），通过从信任集中采样和条件重新分配来探索下层目标，同时优化上层和下层。我们避免了大多数现有双层贝叶斯优化文献中重复的下层优化，因为我们信任集中的点已经足够好，可以直接用于上层优化。从理论上讲，我们证明了信任集中的点在约束和下层目标上的即时遗憾是上界有界的。我们还引入了一种基于估计遗憾的函数查询策略，其中我们结合了估计下层解的不确定性以及下层目标的条件重新分配，以应对由最优下层解约束带来的挑战。这导致查询点的即时遗憾界限，并为常用核函数带来了次线性的累积遗憾和简单遗憾界限。关键组件如图2所示，伪代码在算法1中。

信任集在定义4.3和4.5中定义，引理4.4和4.6提供了信任集中点的即时遗憾界限。定义4.7定义了函数查询选择，引理4.8提出了查询的即时遗憾界限。累积遗憾界限在定理4.9中，简单遗憾界限在引理4.10中。
首先，我们定义用于构建信任集的置信界限。根据推论4.2，函数以高概率被置信界限所限制。
定义4.1（置信界限）。对于由高斯过程（GP）建模的函数h∈F，∀x∈X，z∈Z，以及t≥1，设h(x,z)的上置信界限和下置信界限分别表示为：

接下来，我们通过使用上置信界来近似未知的可行区域，引入一个可行解的可信集，并证明该可信集中的点具有约束遗憾界。

注意，可信可行集将Xu等人（2023）和Nguyen等人（2023）在约束贝叶斯优化方法中针对查询点的约束遗憾界，扩展到了可信集中的所有点，从而便于与最优下层解的可信集相结合，以处理带约束的双层优化问题。

4.1 最优下层解的可信集

我们定义另一个可信集，用于逼近未知的最优下层解集合，该集合基于置信区间和对最优下层解的估计。该可信集中的点具有下层目标函数的遗憾界，使我们能够量化可能存在的下层次优性。

定义4.5（最优下层解的可信集）。令最优下层解的可信集为：

4.2 查询点选择

4.3. 函数查询

4.4. 遗憾界限

算法1的累积遗憾界限在定理4.9中展示，并在附录C.4中使用引理4.8证明。

该遗憾界与函数集 F 中所有函数的最大信息增益相关。与 Nguyen 等人（2023）中约束贝叶斯优化的遗憾界相比，我们的遗憾界具有更大的常数，这是因为下层目标函数的遗憾上界大于约束遗憾的上界。这突显了双层优化问题的更大难度：次优的下层解可能阻碍上层优化，使得双层优化比标准的约束优化更具挑战性。

5. 实验

我们在4个合成问题和2个真实世界问题上评估了BILBO的性能。我们引入了两个基线方法进行比较：“TrustedRand”和“Nested”。TrustedRand从可信集中随机采样查询点，以评估可信集对BILBO整体性能的贡献。“Nested”方法将上层和下层问题分别优化，作为嵌套贝叶斯优化方法（如Kieffer等人（2017）所提出）的基线，其通过近似下层梯度进行优化。关于TrustedRand和Nested的更多细节见附录D.1。需要注意的是，Nested方法无法处理约束，因此在包含约束的实验（SMD12和Chemical）中未作比较。由于Ekmekcioglu等人（2024）最新的并行工作未提供代码，因此也未纳入比较。

5.1 合成问题

合成问题被选用来涵盖多种场景，包括相互冲突的交互、凸函数或多模态函数，以及活跃约束。BraninHoo+GoldsteinPrice 将Branin-Hoo函数作为上层目标函数 F，将Goldstein-Price函数作为下层目标函数 f（Picheny等人，2013）。这两个函数均为非凸且多模态的。维度 dX和 dZ均为1，这便于模型和查询的可视化。两个维度均被离散化为100个点。Branin-Hoo函数有3个最优解，但在受到下层Goldstein-Price最优解约束时，仅存在1个双层最优解。

如图4a所示，BILBO在其他两种方法中表现出显著优势，其在150次查询内收敛到双层最优解。Nested和TrustedRand的收敛速度相当缓慢。对于Nested而言，预测的下层解可能次优，因为下层求解器无法有效处理多模态函数和噪声观测。对于TrustedRand，随机查询可能导致采样到无信息的点。函数的挑战性多模态特性意味着对信息丰富区域的采样对该问题至关重要，而BILBO成功地实现了这一点。

图3a和图3b分别展示了上层和下层的目标函数，其中黄色点表示最优下层解，图3c至图3f展示了BILBO的内部工作原理。BILBO收敛到了最优解，代理模型有效地捕捉了两个函数的整体景观（见图3c和图3d），其中预测的下层解（黄色叉号）接近最优下层解，特别是在上层目标值较高的区域。从上层和下层目标函数中选择的查询点分别显示在图3e和图3f中，颜色越深表示来自更早迭代的样本，它们大多集中在两个可能的最优解附近。BILBO在左上角区域采样目标函数，直到确认该区域不存在最优解，并最终收敛到实际的最优解，这证明了其有效性。

SMD2、SMD6 和 SMD12 是从双层优化测试问题套件SMD（Sinha等人，2014）改编而来。实现细节见附录D.3。测试问题的输入维度设置为5，其中 dX=2且 dZ=3。难度依次递增：SMD2、SMD6、SMD12。

• SMD2

  包含凸函数和相互冲突的交互，即提高下层估计会恶化上层目标值。这要求算法准确预测下层最优解以获得双层最优解。

• SMD6

  也包含凸函数和相互冲突的交互，但每个上层点处存在多个下层最优解（即一个凸谷）。算法必须同时估计多个下层最优解，并识别出能够优化上层目标的点。

• SMD12

  是SMD套件中最具有挑战性的问题，上下两层各有3个活跃约束，最优解位于约束边界上。此外，下层还存在多个最优解。

SMD实验的结果如图4b至图4d所示。

• 对于SMD2，BILBO明显优于TrustedRand和Nested。虽然TrustedRand的遗憾在初始阶段迅速下降，但其下降速率随时间逐渐减弱，可能是因为随机查询最初是有信息量的，但随着过程继续变得不那么有效。

• 对于SMD6，BILBO在大约250步后展现出最小的遗憾。Nested无法处理多个下层最优解，因为它只为每个上层点预测一个下层解。相比之下，BILBO和TrustedRand的可信集允许对多个下层最优解进行估计。

• 对于SMD12，BILBO比TrustedRand收敛得更快。由于SMD12问题中有8个函数，解耦设置对采样效率变得更加关键。BILBO更快的收敛速度证明了我们的函数查询策略在选择更具信息量的函数进行查询方面的有效性。活跃约束的存在似乎也没有对BILBO造成任何困难。

能源问题。我们模拟了一个双层能源市场问题，其中能源供应商在上层决策中竞标电力供应量，以在三个时间段内最大化利润。在下层，他们优化自身运营，综合考虑成本、需求对价格的响应以及满足变化需求的能力。该问题包含2个上层变量：电价和竞标电量；以及2个下层变量：一座发电厂的爬坡速率限制，以及另一座发电厂在各时段的最大输出功率。下层变量影响电力的总体最优调度，而三家发电厂的调度过程使用PyPSA（Brown等，2018）进行模拟。我们将下层目标函数定义为模拟输出的函数，旨在寻求最低的发电成本，同时引入惩罚项以减少设备磨损或其他辅助性问题。更多细节见附录D.4。

化工问题。制药、石化和食品生产等行业中的化学过程通常涉及多个阶段，每个阶段都需要参数优化。双层优化通过将整个流程划分为更小、更易管理的子问题来简化这一过程，同时仍能考虑不同阶段之间的相互作用。我们使用COCO模拟器模拟了二甲醚（DME）羰基化生成乙酸甲酯的过程，该流程图改编自ChemSep提供的流程。上层问题聚焦于通过一个蒸馏塔最大化纯度为99.9%的乙酸甲酯产率，该蒸馏塔的进料为包含乙酸甲酯、未反应的DME及副产物的反应混合物，这些是下层优化的输出。下层问题涉及在反应器中通过DME的羰基化反应生成乙酸甲酯。此外，上层还包含一个约束条件，以确保化学品处于正确物态所需的合适温度范围。该问题有1个上层变量：蒸馏塔的塔板数；以及3个下层变量：反应器温度、加热管数量和加热管直径。更多细节见附录D.5。结果如图5f所示，BILBO优于TrustedRand，突显了BILBO在优化复杂工业操作中的潜在高效性与有效性。

关于BILBO计算复杂度和时间效率的进一步讨论见附录E。

6 未来工作

7.结论

我们提出了BILBO——一种新颖的双层贝叶斯优化算法，能够同时优化上层和下层问题。BILBO通过对基于置信区间的可信集进行采样，以限制下层次优性；并通过查询点的条件重分配机制鼓励对下层目标的探索，从而取代现有方法所必需的重复下层优化。我们从理论上证明了BILBO具有次线性遗憾界，实验结果也表明，BILBO在多个基准方法中表现更优，尤其在包含多个非凸函数的问题中优势明显。BILBO是迈向通用双层求解器的重要一步，将有助于将双层优化方法应用于涉及黑箱函数的复杂现实世界问题

原文链接：https://arxiv.org/pdf/2502.02121