Abstract
在许多应用中，如机器人控制、自动驾驶和投资组合管理，需要在严格的运行时间限制下连续地解决相似的优化问题。在这种情况下，局部优化方法的性能对初始解的质量非常敏感：不良的初始化可能会导致收敛缓慢或得到次优解。为应对这一挑战，我们提出了一种学习预测多个多样化初始解的方法，以给定定义问题实例的参数为基础。我们介绍了两种使用多初始解的策略：(i) 单优化器方法，通过选择函数选择最优的初始解；(ii) 多优化器方法，其中多个优化器被分别初始化，最终选择最佳解。我们在三个优化控制基准任务上验证了此方法：倒立摆、目标到达和自动驾驶，并使用了不同的优化器：DDP、MPPI 和 iLQR。我们发现该方法在所有评估设置中均显著且一致地提高了性能，并证明了其随着初始解数量的增加而有效扩展。
代码获取：https://github.com/EladSharony/miso
欢迎加入自动驾驶实战群
Introduction
许多应用，如机器人和自动驾驶中的轨迹优化以及金融中的投资组合管理，需要在紧张的运行时间约束下连续解决类似的优化问题 。在这些情况下，局部优化器的性能通常高度依赖于提供的初始解，而不良的初始化可能导致次优解或无法在限定时间内收敛 。因此，始终生成高质量初始解对于保证性能和安全性非常重要。
传统的初始解选择方法通常依赖启发式方法或“热启动”技术，即重复使用先前已解问题实例的解。最近，还提出了基于学习的解决方案，使用神经网络来预测初始解。然而，在更具挑战性的情况下，例如当优化景观高度非凸或连续的问题实例快速变化时，预测单一优质初始解变得困难。
为此，我们提出了学习多个初始解的方法 (MISO)（如图 1 所示），通过训练神经网络来预测多个初始解。我们的方法适用于两种关键设置：(i) 单优化器方法，使用选择函数利用问题实例的先验知识来识别最优的初始解，并将其提供给优化器；(ii) 多优化器方法，生成多个初始解以支持多个优化器的执行，这些优化器可能并行运行，最后选择最佳解。
具体来说，我们的神经网络接收一个参数向量，用于表征问题实例，并输出 𝐾个候选初始解。网络在问题实例与（近）最优解配对的数据集上进行训练，并在此前未见过的实例上进行评估。网络不仅旨在预测接近最优解的初始解，还确保这些解具有足够的多样性，以覆盖问题中的所有潜在模式。为积极鼓励这种多模态性，我们在训练中实施了一些策略，如赢家通吃损失（仅惩罚损失最低的候选解）、基于分散的损失项（促进解的分散性），以及两者的结合。
我们在三个局部优化算法上评估了 MISO，这些算法被应用于不同的机器人控制任务：用于倒立摆任务的第一阶 Box 差分动态规划（DDP）、用于目标到达任务的基于采样的模型预测路径积分控制（MPPI）、以及用于自动驾驶任务的迭代线性二次调节器（iLQR）。结果显示，MISO 显著优于依赖启发式方法的现有初始化方法、学习单一初始解的方法以及独立学习模型的集合方法。
3.3. 初始化优化器
问题设定。在最一般的形式下，我们需要求解一个参数化优化问题的实例，
其中
是要优化的变量向量，J是目标函数，g和 h是不等式和等式约束的集合，而
是定义问题实例的参数向量，例如目标函数和约束的参数，这些参数在不同的问题实例中有所不同。局部优化算法 Opt 试图找到 J 的最优解，即
其中
是提供给优化器的初始解，是运行时间限制。
启发式方法。初始解 的常见选择是先前已解决的类似问题实例的解，这被称为热启动。例如，在最优控制中，热启动通常是前一个时间步的解，该解经过平移并用零填充，即
。这种启发式方法在实践中通常效果较好，但当问题实例在连续的时间步中发生较大变化时，可能会出现问题，导致最优解显著变化。例如，在自动驾驶中，诸如红绿灯突然变化或行人突然出现等突发事件，可能会大幅改变参考轨迹或约束。在这种情况下，先前的解成为一个较差的初始化，优化器可能无法在规定时间内找到良好的解。
4. 学习多个初始解 (MISO)
MISO 的主要思想是训练一个神经网络来预测优化问题的多个初始解，使得这些初始解能够覆盖优化景观中有潜力的区域，从而使局部优化器找到接近全局最优解的解。关键问题在于如何设计多输出预测器、如何在现有优化器中利用多个初始解，以及如何训练预测器输出多样化的初始解。在以下部分中，我们讨论了这些问题的解决方案，使用一个简单的例子说明多模态的需求，并探讨其在最优控制中的应用。
4.1 多输出预测器
我们的多输出预测器是一个神经网络，它以问题实例作为输入，并为该优化问题输出 K 个初始解，
其中 θ是网络学习的参数。我们在包含问题实例及其对应的（近）最优解的数据集
上训练网络。此类数据集可以离线生成，例如通过运行一个较慢但全局最优的求解器，或允许相同的局部优化器在更长的时间限制下从不同的初始解多次运行以生成。
4.2 使用多重初始解的优化
我们提出了两种利用多个初始解的不同设置：单优化器和多优化器。生成的框架如图1所示。
单优化器。在单优化器设置中，我们使用最有潜力的初始解运行一个优化器实例，计算公式为
。我们引入一个选择函数，该函数在给定一组候选解和问题实例 ψ的情况下，返回最有潜力的候选解
。在实验中，我们使用的是选择能够最小化目标函数的候选解，即
。其他可能的选择包括基于风险评估、性能稳定性、稳健性、探索性，或与总体任务目标一致的领域特定指标。
多优化器。在多优化器设置中，我们假设可以并行执行多个优化器实例。然后用不同的初始解初始化每个优化器，计算公式为
，其中
。从优化器的输出中选择一个单一解，我们可以使用与前述相同的选择函数 ，例如选择能够最小化目标函数的解。
我们的框架可以很容易地推广到允许使用不同数量的优化器和初始解预测，以及使用一组异构的优化方法。此外，为了保持性能保证，可以将默认解（例如热启动）作为考虑的初始解之一，这确保了即使预测结果较差，最终解的质量也不会下降。
4.3 训练策略
最终目标是预测多个初始解，以便下游优化器能够找到接近全局最优的解，即
。通常，直接为此目标训练神经网络并不可行。因此，我们提出了结合两个项的代理训练目标：一个回归项，鼓励输出接近全局最优，例如
，其中 是距离度量；另一个是多样性项，鼓励输出彼此不同，从而覆盖解空间的不同区域。在第4.4节中有一个示例说明。以下我们介绍三种简单的训练策略，以促进多样性并防止模式崩溃。我们在第7节讨论概率建模和强化学习等替代方案。
成对距离损失。一种鼓励模型输出彼此不同的简单方法是惩罚所有输出之间的成对距离。整体损失将此分散性提升项与回归损失相结合：
其中 是平衡准确性与分散性权衡的超参数。
赢家通吃损失。一种更有趣的促进多模态的方法是在训练时选择最佳预测输出，并仅对该特定预测的回归损失进行最小化：
直观上，模型只需要其一个输出接近真实值，而其他预测偏离则不受惩罚，可能会对齐到基础分布的不同区域。类似的损失已在多选学习中使用。这种方法的一个优势是它不需要超参数。
混合损失。最后，我们考虑结合前两种方法，以可能提高性能，因为它提供了一些可调节的分散度：
其中 是一个有上限的函数，例如 min或 tanh，旨在限制成对距离项的贡献。
除了上述损失，MISO 还可以与其他训练范式（例如强化学习或概率建模）结合。我们在第7节讨论了这些选项，但将调查留待未来的工作中。
4.4 示例说明
上图展示了一维成本函数 c(x)，具有在 A 和 C 处的全局最小值及在 B 处的局部最小值。下图则展示了不同方法预测的初始解，显示了为何明确促进多模态性十分重要。为了说明单一多模态输出模型的优势，我们考察了一个简单的一维优化问题，目标是最小化图2顶部所示的成本函数 c(x)。该函数在 A 和 C 处有两个全局最小值，并在二者之间的 B 处存在一个局部最小值。
将我们的学习框架应用于此简单问题时，最优解的数据集包括了 A 和 C 的实例。单输出回归模型无法区分这两种模式，不可避免地会预测数据集实例的平均值，大致位于 B 附近。因此，局部优化器很可能会收敛到次优的局部最小值 B。构建此类模型的集成方法来生成多个初始解也无法缓解这一问题，因为每个集成成员往往偏向于位于 B 附近的两种模式的均值。我们在图2底部展示了不同训练策略的预测结果。确实，单输出预测器集成未能预测出全局最优，而我们的多输出预测器通过赢家通吃和混合损失方法成功实现了这一目标。
虽然该问题本身故意简化，但局部最小值的存在是大多数优化问题中的主要挑战。
4.5 最优控制中的应用
MISO 适用于广泛的序列优化问题；不过，为了评估，我们专注于最优控制问题。最优控制在机器人、自动驾驶以及许多具有严格运行时要求的领域中有广泛应用。由于约束和非凸成本带来的复杂性，本地优化算法对初始解高度敏感。
在最优控制中，优化变量 x 表示一个由离散时间步的状态和控制输入序列定义的轨迹
，
分别表示时间步
的状态和控制输入，
是优化的时域。约束条件包括满足系统动力学
起始于初始状态
，其中 表示系统的当前状态。问题实例的参数 ψ包括初始状态和其他参数，如目标状态、参考轨迹、障碍物位置、摩擦系数、温度等。
最优控制问题的一个特性在于，优化变量状态和控制之间的关系由动力学约束定义，并且初始状态是已知的。因此，控制序列唯一地定义了（初始）解。我们可以利用这一特性，只预测控制序列而非状态-控制序列的完整优化变量。此外，可以在控制、状态或状态-控制序列上定义训练损失，并在动力学约束可微的情况下通过它进行梯度回传。在我们的实验中，我们默认使用状态-控制损失，因为我们发现这对我们和基线学习方法都有所改进。
5.Experiment
我们在不同初始解下的优化主要结果分别在表1和表2中报告，适用于单优化器和多优化器设置。图4展示了预测初始解数量的效果。图5提供了定性结果。
单优化器：在单优化器设置中（见表1），我们首先观察到，甚至一个学习初始化在几乎所有设置中（尤其在最具挑战性的自动驾驶任务中）都优于启发式解（即回归与热启动）。接下来我们考察了生成多个初始解的影响。基于扰动的方法在多数情况下比单一初始化方法有一定改进，而独立训练的模型集成始终优于单模型。最终，我们提出的多输出方法在所有基线上表现出显著的提升，因为这些方法能够学习预测多样的多模态初始解。具体来说，MISO赢家通吃或MISO混合在所有任务中都实现了最低的平均成本。仅考虑成对距离项不足以确保充分的多样性，而与MISO赢家通吃结合通常能提高性能，但其效果不一，这突显了选择最优超参数的难度。正如预期，在更重要的序列优化设置中改进更为显著，因为误差会随着时间累积。
多优化器：在多优化器设置中，观察到相同的趋势。基于学习的方法优于启发式方法，多输出方法进一步提升了效果。正如预期的那样，由于增加了对解空间的探索，使用多个优化器相比于单优化器设置带来了持续更好的结果。
随着初始解数量的扩展：图4显示了我们的方法在预测初始解数量 KKK 上的有效扩展能力，并在不同的 KKK 值下始终优于其他方法。重要的是，随着 KKK 的增加，集成方法的推理时间增加，而MISO几乎保持不变（见附录A.6）。我们进一步在附录A.8中评估了模式多样性，结果表明符合我们的结论，即使 KKK 增加，所有MISO输出依然有效。
定性结果：图5（左）展示了在自动驾驶任务中，使用不同初始解得到的优化器输出轨迹。在这一场景中，高级规划器突然改变了参考路径，这可能由于新检测到的行人而发生。参考路径的改变使得之前的解（热启动）成为一个较差的初始化，优化器收敛到控制努力最小但偏离目标路径的局部最小值。回归模型和模型集成也未能预测出好的初始解。相比之下，MISO赢家通吃适应了这一突如其来的参考变化，紧跟参考路径。图5（右）展示了MISO在倒立摆任务中的初始解。不同的输出捕获了解空间中的不同模式（直立移动、左摆移动、右摆移动），显示了MISO生成多样和多模态解的能力。
总体而言，我们的方法在两种设置中都显著优于其他基线。MISO混合和MISO赢家通吃方法在不同任务和配置中的持续优越性突显了使用基于学习的多输出策略生成初始解的优势。这些发现表明，在多个初始解中促进多样性对于优化结果的改善至关重要，尤其在与多个优化器结合时更为显著。
结论
本文的主要贡献如下：
1.提出了一种用于预测多个初始解的全新框架。
2.引入了两种使用预测初始解的策略：(i) 单优化器方法，通过选择函数选择最优解；(ii) 多优化器方法，通过初始化多个优化器后选择最佳解。
3.设计并实现了具体的训练目标，以防止模式崩塌，并确保预测解保持多模态性。
4.将该框架应用于三个连续优化任务，并进行了广泛的评估。
文章引用：LEARNING MULTIPLE INITIAL SOLUTIONS TO OPTI-MIZATION PROBLEMS
最后别忘了，帮忙点“在看”。
您的点赞，在看，是我创作的动力。
AiFighing是全网第一且唯一以代码、项目的形式讲解自动驾驶感知方向的关键技术。
长按扫描下面二维码，加入知识星球。
