GLENS：通过扩散模型从求解器迭代中学习进行全局搜索

# GLENS：通过从求解器迭代中学习进行全局搜索（基于扩散模型）
来源：https://arxiv.org/html/2606.00366 \[1\]\\fnm安健\\sur李 \[1\]\\orgdiv电气与计算机工程系，\\orgname普林斯顿大学，\\orgaddress\\城市普林斯顿，\\邮政编码08544，\\州新泽西，\\国家美国 2\]\\orgdiv运筹学与金融工程系，\\orgname普林斯顿大学，\\orgaddress\\城市普林斯顿，\\邮政编码08544，\\州新泽西，\\国家美国 3\]\\orgdiv机械与航空航天工程系，\\orgname普林斯顿大学，\\orgaddress\\城市普林斯顿，\\邮政编码08544，\\州新泽西，\\国家美国 ###### 摘要 本文考虑为多模态非凸连续优化问题的局部极小值生成大量初始猜测的问题。目标是使这些初始猜测既高质量（即，数值求解器能快速收敛）又多样化（即，代表许多不同的局部极小值）。识别多个局部最优解可以实现灵活的下游决策，但通常需要昂贵的全局搜索。现有的数据驱动方法仅使用离线求解器运行中最终收敛的最优解来预测初始猜测，这丢弃了关于解局部邻域的信息并限制了可用训练数据。我们提出GLENS（通过从求解器迭代中学习进行全局搜索），一种数据高效的全局搜索方法，利用中间求解器迭代作为免费数据增强。GLENS包含两个组件：一个邻域结构模型，使用扩散模型学习以问题参数为条件的局部几何结构；一个求解器行为模型，学习精化方向，以便在扩散采样过程中进一步引导样本趋向附近的局部最优解。在修改后的非凸基准问题和双机器人避障导航问题上的实验表明，GLENS能够生成高质量的初始猜测，同时保留多样化局部最优解的多模态分布。生成的初始猜测在不同问题设置和求解器下均能加速求解器收敛。我们还分析了关键超参数选择对性能的影响。 ###### 关键词: 全局搜索, 数据驱动优化, 非凸优化, 扩散模型, 求解器迭代 ## 1 引言 现实应用中出现的非凸连续优化问题通常表现出多个局部最优解。除了寻找单一全局最优解外，识别一组多样化的局部最优解通常更为可取，从而能够在不同目标和需求之间进行权衡。理想情况下，这组多样化的解也应是高质量的，即它们的目标函数值合理接近全局最优（后者很可能未知）。例如，在自主机器人导航中，多条可行轨迹可能在安全性、时间效率或舒适性方面有所不同\[1 (https://arxiv.org/html/2606.00366#bib.bib1)\]; 在航天器轨迹设计中，性质不同的轨迹可能在飞行时间、燃料消耗或飞越序列上存在差异\[2 (https://arxiv.org/html/2606.00366#bib.bib2)\]。获得这样多样化的候选解可以为下游决策提供更大的灵活性。然而，为非凸问题找到一组多样化的高质量局部最优解通常需要昂贵的全局搜索。一种广泛使用的方法是混合方法，例如多起点\[3 (https://arxiv.org/html/2606.00366#bib.bib3)\]或单调盆地跳跃（MBH）\[4 (https://arxiv.org/html/2606.00366#bib.bib4)\]，它将全局采样与局部搜索相结合。从解空间上的启发式分布中采样多个初始猜测，然后基于梯度的数值求解器通过一系列迭代将每个初始猜测精化到附近的局部最优解\[3 (https://arxiv.org/html/2606.00366#bib.bib3)\]。对于高维且高度非凸的问题，为数值求解器确定合适的初始猜测变得越来越困难，全局搜索很快变得计算昂贵。

另一种范式是摊销优化\[5 (https://arxiv.org/html/2606.00366#bib.bib5)\]，它离线解决参数化优化问题的多个实例，并学习解\[6 (https://arxiv.org/html/2606.00366#bib.bib6)\]或求解策略\[7 (https://arxiv.org/html/2606.00366#bib.bib7),8 (https://arxiv.org/html/2606.00366#bib.bib8)\]如何随问题参数变化，从而在测试时能够为新实例高效预测高质量解。在这种数据驱动设置下，多层感知器（MLP）已被用于预测凸问题的最优解\[9 (https://arxiv.org/html/2606.00366#bib.bib9)\]。对于具有多个局部最优解的问题，生成模型如扩散模型\[10 (https://arxiv.org/html/2606.00366#bib.bib10),11 (https://arxiv.org/html/2606.00366#bib.bib11)\]被用于采样解分布，应用于混合整数规划\[12 (https://arxiv.org/html/2606.00366#bib.bib12)\]和非凸轨迹优化\[13 (https://arxiv.org/html/2606.00366#bib.bib13),14 (https://arxiv.org/html/2606.00366#bib.bib14)\]。尽管前景广阔，但基于学习的非凸优化方法面临一个重大挑战：数据稀缺。生成模型需要大量多样化、高质量的训练数据来学习问题参数与解分布之间的关系\[15 (https://arxiv.org/html/2606.00366#bib.bib15)\]。整理这样的数据集需要跨许多问题实例运行昂贵的全局搜索，引入了显著的计算瓶颈。此外，现有的基于学习的摊销优化方法通常只收集数值求解器产生的最终收敛解\[6 (https://arxiv.org/html/2606.00366#bib.bib6),9 (https://arxiv.org/html/2606.00366#bib.bib9),13 (https://arxiv.org/html/2606.00366#bib.bib13)\]，而丢弃求解过程中生成的中间迭代。尽管这种做法保持了解的质量（包括可行性和局部最优性），但它忽略了关于最优解周围邻域结构的有价值信息。例如，先前工作表明，在轨迹优化中，局部最优解可能非常接近不可行区域\[16 (https://arxiv.org/html/2606.00366#bib.bib16),17 (https://arxiv.org/html/2606.00366#bib.bib17)\]。如果不访问解的邻域结构信息，数据驱动模型可能难以稳健地泛化到约束条件或其他问题参数的变化。

受这些局限性的启发，我们的关键洞察是利用数值求解器产生的中间迭代作为基于学习的摊销优化的训练数据。尽管这些迭代是次优的，但它们编码了关于最优解局部邻域的丰富信息。重要的是，求解器生成的迭代提供了免费的数据增强，不需要超出原始优化运行之外的额外计算成本。然而，由于中间迭代是次优的，如果不进行适当建模就直接使用，可能会降低性能。

参见图注
图1：GLENS中邻域结构模型（左）和求解器行为模型（右）的图示。邻域结构模型使用扩散模型学习局部最优解的局部几何结构，以标量半径 r 为条件，该半径度量每个中间迭代到其收敛迭代的距离。求解器行为模型学习来自求解器的精化方向 −∇_x E，并在逆向扩散过程中引导邻域结构模型的样本趋向最优解。

在本文中，我们提出GLENS（通过从求解器迭代中学习进行全局搜索），这是一种数据驱动的方法，利用中间迭代实现稳健且数据高效的非凸连续优化全局搜索。该方法包含两个基于学习的组件。邻域结构模型是一个条件扩散模型，在收敛前的最后几次迭代上训练，学习最优解的局部几何结构以及它如何随问题参数和相对距离变化。求解器行为模型是一个神经网络，从中间求解器迭代预测求解器精化方向，模仿求解器的精化行为，并具有在运行时快进求解器的潜力。它提供额外的引导，将扩散样本导向高质量的初始猜测；即，那些接近局部最优解且因此需要更少求解器迭代才能达到收敛的样本。我们通过一系列复杂度递增的问题来说明所提出的框架。我们从由梯度下降求解的软约束二次规划（QP）开始。这个单模态示例提供了一个受控设置，用于检查GLENS是否准确捕获局部邻域结构及其随问题参数的变化。选择这个例子的动机是观察到，在许多非凸问题中，局部最优解的邻域可以很好地由约束二次问题近似。然后我们考虑几个多模态非凸基准问题，包括修改后的Himmelblau、Rosenbrock和Levy函数，使用L-BFGS-B求解器\[18 (https://arxiv.org/html/2606.00366#bib.bib18)\]。这些例子评估GLENS学习和采样多样化局部最优解的能力。我们还分析关键超参数选择。最后，我们将GLENS应用于一个双机器人导航问题，该问题具有非线性动力学和多障碍环境，使用SNOPT\[19 (https://arxiv.org/html/2606.00366#bib.bib19)\]。本文组织结构如下。在第2节 (https://arxiv.org/html/2606.00366#S2)，我们介绍参数化优化问题和摊销全局搜索（AmorGS）框架。我们还介绍扩散建模设置。在第3节 (https://arxiv.org/html/2606.00366#S3)，我们介绍k-邻域数据集定义，并介绍GLENS中的双组件学习架构。它包含一个基于条件扩散模型的邻域结构模型和一个具有U-Net架构的求解器行为模型。在第4节 (https://arxiv.org/html/2606.00366#S4)，我们在几个数值例子中评估所提出的方法：一个软约束QP和几个非凸基准函数，包括修改后的Himmelblau、Rosenbrock和Levy函数。在第5节 (https://arxiv.org/html/2606.00366#S5)，我们分析不同超参数选择如何影响性能。在第6节 (https://arxiv.org/html/2606.00366#S6)，我们展示GLENS在双机器人导航问题上的有效性。最后，第7节 (https://arxiv.org/html/2606.00366#S7)总结贡献并讨论未来方向。

### 1.1 相关工作

**全局搜索。** 对于现实应用中出现的非凸优化问题，通常需要全局搜索来揭示一组多样化、高质量的局部最优解。进化算法，包括遗传算法\[20 (https://arxiv.org/html/2606.00366#bib.bib20)\]和差分进化\[21 (https://arxiv.org/html/2606.00366#bib.bib21)\]，以及粒子群优化\[22 (https://arxiv.org/html/2606.00366#bib.bib22)\]，代表了一类基于种群的全局搜索方法。这些方法已成功应用于空间轨迹设计\[23 (https://arxiv.org/html/2606.00366#bib.bib23),24 (https://arxiv.org/html/2606.00366#bib.bib24),25 (https://arxiv.org/html/2606.00366#bib.bib25),26 (https://arxiv.org/html/2606.00366#bib.bib26)\]、电路设计\[27 (https://arxiv.org/html/2606.00366#bib.bib27),28 (https://arxiv.org/html/2606.00366#bib.bib28)\]和作业调度\[29 (https://arxiv.org/html/2606.00366#bib.bib29),30 (https://arxiv.org/html/2606.00366#bib.bib30)\]。混合优化方法，例如多起点策略\[31 (https://arxiv.org/html/2606.00366#bib.bib31)\]，首先在解空间上进行全局采样以生成多个初始猜测，然后应用基于梯度的数值求解器收敛到附近的局部最优解\[3 (https://arxiv.org/html/2606.00366#bib.bib3)\]。基于这一思想，MBH\[32 (https://arxiv.org/html/2606.00366#bib.bib32),4 (https://arxiv.org/html/2606.00366#bib.bib4)\]基于邻近局部最优解通常通过漏斗状能量景观相连的观察，向局部优化添加随机扰动。MBH已成功应用于化学结构优化\[33 (https://arxiv.org/html/2606.00366#bib.bib33),34 (https://arxiv.org/html/2606.00366#bib.bib34)\]、生物信息学\[35 (https://arxiv.org/html/2606.00366#bib.bib35),36 (https://arxiv.org/html/2606.00366#bib.bib36)\]和空间轨迹设计\[2 (https://arxiv.org/html/2606.00366#bib.bib2),37 (https://arxiv.org/html/2606.00366#bib.bib37)\]，在某些基准设置中优于进化算法和粒子群优化\[38 (https://arxiv.org/html/2606.00366#bib.bib38)\]。尽管有效，这些经典全局搜索方法通常计算昂贵，因为在高维且高度非线性的空间中确定合适的初始猜测仍然具有挑战性。此外，这些方法通常不利用来自先前求解过的问题实例的数据来学习或重用关于解景观的结构信息，因此当遇到新问题时必须从头开始执行全局搜索。这一局限性激发了基于学习的方法，该方法利用求解器生成的数据来跨问题实例摊销全局搜索的成本。

**机器学习用于优化。** 摊销优化\[5 (https://arxiv.org/html/2606.00366#bib.bib5)\]离线从参数化问题族中学习解结构，以加速在线求解新实例。对于凸问题，该范式已被证明在使用MLP预测QP的热启动\[9 (https://arxiv.org/html/2606.00366#bib.bib9)\]和具有线性动力学的模型预测控制问题\[39 (https://arxiv.org/html/2606.00366#bib.bib39),6 (https://arxiv.org/html/2606.00366#bib.bib6)\]方面有效。对于非凸优化，传统的判别模型，如决策树或基于MLP的回归器，已被用于学习求解策略，例如通过预测活跃约束集或其他结构性质，将原始问题转化为更简单的形式\[8 (https://arxiv.org/html/2606.00366#bib.bib8),7 (https://arxiv.org/html/2606.00366#bib.bib7),40 (https://arxiv.org/html/2606.00366#bib.bib40)\]。然而，学习从问题参数到解的单确定性映射通常不足以处理具有多个局部最优解的高度非线性问题；因此，近期工作探索了生成模型用于学习局部最优解的条件分布。基于图的扩散模型已被提出用于组合优化问题\[12 (https://arxiv.org/html/2606.00366#bib.bib12),41 (https://arxiv.org/html/2606.00366#bib.bib41)\]。在非凸轨迹优化的背景下，支持向量机\[42 (https://arxiv.org/html/2606.00366#bib.bib42)\]、变分自编码器（VAE）\[43 (https://arxiv.org/html/2606.00366#bib.bib43)\]、Transformer\[44 (https://arxiv.org/html/2606.00366#bib.bib44)\]和扩散模型\[13 (https://arxiv.org/html/2606.00366#bib.bib13),17 (https://arxiv.org/html/2606.00366#bib.bib17),45 (https://arxiv.org/html/2606.00366#bib.bib45)\]已被使用。