Learning Multiple Initial Solutions to Optimization Problems
Elad Sharony, Heng Yang, Tong Che, Marco Pavone, Shie Mannor, Peter Karkus
AI summary
Problem
Local optimization algorithms are highly sensitive to initial guesses, often failing or converging slowly when initialization is poor. Existing learning-based methods typically predict only a single solution, which struggles in non-convex or rapidly changing problem landscapes.
Approach
The authors propose MISO, a neural network that predicts multiple diverse candidate initializations for a given problem instance. These candidates are either fed to a single optimizer via a selection function or used to initialize multiple parallel optimizers, with training explicitly penalizing mode collapse to ensure solution diversity.
Key results
- Significantly outperforms warm-start, single-output regression, and ensemble baselines across three optimal control benchmarks
- Guarantees final solution quality equal to or better than default initialization strategies
- Demonstrates efficient scaling of performance with the number of predicted initial solutions
- Successfully handles non-convex landscapes and rapid problem instance shifts in cart-pole, reacher, and autonomous driving tasks
Why it matters
Provides a robust, scalable initialization strategy that enhances the performance and safety of real-time optimization in robotics, autonomous systems, and control applications.
Abstract
Sequentially solving similar optimization prob- lems 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 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.