Skip to content

Learning Multiple Initial Solutions to Optimization Problems

Authors: Elad Sharony, Heng Yang, Tong Che, Marco Pavone, Shie Mannor, Peter Karkus

Published: 2024 (Preprint)

Source: arXiv

Algorithm: MISO

arXiv: 2411.02158

Summary

Learns a generative model that produces multiple diverse initial solutions for optimization problems, enabling warm-started solvers to explore different basins of attraction and improve the probability of finding high-quality global optima.

Abstract

Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications, such as robot control, autonomous driving, and portfolio management. The performance of local optimization methods in these settings is sensitive to the initial solution: poor initialization can lead to slow convergence or suboptimal solutions. To address this challenge, we propose learning to predict \emph{multiple} diverse initial solutions given parameters that define the problem instance. We introduce two strategies for utilizing multiple initial solutions: (i) a single-optimizer approach, where the most promising initial solution is chosen using a selection function, and (ii) a multiple-optimizers approach, where several optimizers, potentially run in parallel, are each initialized with a different solution, with the best solution chosen afterward. Notably, by including a default initialization among predicted ones, the cost of the final output is guaranteed to be equal or lower than with the default initialization. We validate our method on three optimal control benchmark tasks: cart-pole, reacher, and autonomous driving, using different optimizers: DDP, MPPI, and iLQR. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required. The code is available at https://github.com/EladSharony/miso.

Primary

Paper arxiv.org

Standard

arXiv Abstract 2411.02158 arXiv PDF 2411.02158 arXiv HTML 2411.02158

Alternate

GitHub: EladSharony/miso github.com

Tags

  • Trajectory optimization

  • Learning

  • Warm-starting

  • Multi-modal optimization

  • Neural network