Learning Multiple Initial SOlutions to Optimization Problems

Elad Sharony¹, Heng Yang^2,3, Tong Che², Marco Pavone^2,4, Shie Mannor^1,2, Peter Karkus²

¹Technion²NVIDIA Research³Harvard University⁴Stanford University

ICRA 2026

Paper coming soon arXiv Code

Overview

Many real-world applications—from autonomous driving to robotic manipulation—require solving similar optimization problems sequentially under strict runtime constraints. The performance of local optimizers is highly sensitive to the initial solution: poor initialization can lead to slow convergence or convergence to suboptimal local minima.

We propose MISO (Learning Multiple Initial SOlutions), a framework that trains a single neural network to predict multiple diverse initial solutions for optimization problems. Unlike ensemble methods that require training and running multiple models, MISO uses a single efficient network with diversity-promoting training objectives.

Single-optimizer setting: Select the most promising initial solution using a selection function, then run a single optimizer.
Multiple-optimizers setting: Initialize multiple parallel optimizers, each with a different predicted solution, and select the best final output.
Guaranteed improvement: By including the default initialization among predictions, MISO is guaranteed to perform equal or better than baseline.
Efficient inference: Unlike ensembles, MISO's inference time remains nearly constant as $K$ increases.

Figure 1. Method overview. Prior work (top) predicts a single initial solution from the problem parameters. MISO (bottom) predicts multiple diverse initial solutions with a single neural network (MISO components outlined in rose) and uses them in one of two ways. With a single optimizer, a candidate evaluator selects the most promising initial solution; with multiple optimizers, every initial solution starts its own optimizer and the evaluator selects the best result. Each block pictures its step: paths on the driving scene of Figure 6, and optimizers descending a cost surface with a shallow and a deep basin, where the one prediction of prior work settles in the shallow one. Point at a block to replay its step and isolate its pipeline.

1 Motivation

Real-world scenario: autonomous driving

Consider an autonomous vehicle following a planned trajectory. Suddenly, a pedestrian steps onto the road, causing the high-level planner to abruptly change the reference path. The previous trajectory (warm-start) is now far from optimal—the optimizer must find a completely different solution within milliseconds. Similar abrupt changes occur with traffic light switches, sudden lane closures, or newly detected obstacles.

Traditional initialization approaches fail in these scenarios:

Warm-start: Reuses the previous solution, which becomes invalid after abrupt changes.
Single-output regression: Learns to predict the mean of multiple modes, often corresponding to a local minimum.
Ensemble of regressors: Each model is biased toward the same mean, failing to cover multiple modes.

Figure 2. Toy task. Left: The one-dimensional cost function $c(x)$ with global minima at A and C and a local minimum at B; the optimal solutions in the training data sit at A and C. Right: Predicted initial solution for different methods, demonstrating why explicitly promoting multimodality is important. Hover a prediction for its value.

Key insight

By explicitly training for diversity using winner-takes-all or mixture losses, MISO learns to cover multiple modes of the solution distribution, enabling the optimizer to reach global optima regardless of which mode is active.

2 Method

Given a parameter vector $\boldsymbol{\psi}$ that defines a problem instance (e.g., current state, goal, obstacles), our multi-output predictor outputs $K$ candidate initial solutions:

$$\{\hat{\boldsymbol{x}}_{k}^{\mathrm{init}}\}_{k=1}^{K} = \boldsymbol{f}(\boldsymbol{\psi}; \boldsymbol{\theta})$$

Training strategies

To ensure diverse outputs that cover multiple modes, we introduce three training strategies:

Winner-takes-all (WTA) loss

Only penalize the best-predicted output, allowing other outputs to specialize on different modes:

$$\mathcal{L}_{\mathrm{WTA}} = \min_{k} \{\mathcal{L}_{\mathrm{reg}}(\hat{\boldsymbol{x}}_{k}^{\mathrm{init}}, \boldsymbol{x}^{\star})\}$$

Pairwise distance (PD) loss

Add a term to encourage dispersion among outputs:

$$\mathcal{L}_{\mathrm{PD}} = \frac{1}{K} \sum_{k=1}^{K} \mathcal{L}_{\mathrm{reg}}(\hat{\boldsymbol{x}}_{k}^{\mathrm{init}}, \boldsymbol{x}^{\star}) + \alpha_K \frac{1}{K(K-1)} \sum_{k \neq k'} \| \hat{\boldsymbol{x}}_{k}^{\mathrm{init}} - \hat{\boldsymbol{x}}_{k'}^{\mathrm{init}} \|$$

Mixture loss

Combine WTA with pairwise distance for enhanced diversity control:

$$\mathcal{L}_{\mathrm{MIX}} = \min_{k} \left\{\mathcal{L}_{\mathrm{reg}}(\hat{\boldsymbol{x}}_{k}^{\mathrm{init}}, \boldsymbol{x}^{\star}) + \alpha_K \Phi\left(\mathcal{L}_{\mathrm{PD}, k}\right)\right\}$$

Selection function

In the single-optimizer setting, a selection function $\Lambda$ chooses the most promising initial solution. A natural choice is selecting the candidate that minimizes the objective: $\Lambda := \arg\min_{k} J(\hat{\boldsymbol{x}}_{k}^{\mathrm{init}}; \boldsymbol{\psi})$. Alternative criteria include constraint satisfaction, robustness measures, or domain-specific requirements.

3 Experiments

We evaluate MISO across three optimal control benchmark tasks, each using a different local optimization algorithm:

Cart-pole task — **Cart-pole**Box-DDP[1] optimizer

Reacher task — **Reacher**MPPI[2] optimizer

Autonomous driving task — **Driving (nuPlan)**[4]iLQR[3] optimizer

Main results

Single optimizer setting

**Table 1.** Mean cost (lower is better) for single optimizer with different initialization methods. Best in bold, second best underlined.
Method	K	One-Off Optimization			Sequential Optimization
Method	K	Reacher	Cart-pole	Driving	Reacher	Cart-pole	Driving
Warm-start	1	13.48	11.69	283.86	13.48	11.69	283.86
Regression	1	13.40	11.19	74.23	19.56	6.18	70.62
Ensemble	32	13.39	10.94	47.22	8.40	3.55	52.59
MISO WTA	32	13.36	10.48	30.17	2.72	0.83	30.75
MISO mix	32	12.74	10.48	33.95	2.44	0.79	33.38

Key results

MISO WTA and MISO mix consistently outperform all baselines. On the challenging driving task, MISO reduces mean cost by 89% compared to warm-start and 42% compared to ensemble methods in sequential optimization.

Scaling with number of initial solutions

(a) Single optimizer

(b) Multiple optimizers

Figure 3. Scaling with $K$. Mean cost on the driving task (sequential optimization) for varying $K$ values. MISO scales effectively with the number of predicted initial solutions. Hover a marker for its value; click a legend entry to hide a method in both panels. Values are recovered from the paper's vector figure; at $K = 32$ they match Table 1.

Inference time comparison

Figure 4. Inference time. Mean inference time as $K$ increases. MISO (multi-output) maintains nearly constant inference time, while ensemble inference time grows linearly with $K$. Hover a marker for its value.

Mode frequency analysis

Figure 5. Output selection frequency. Heatmap of output selection frequency for MISO WTA on the driving task. All outputs remain active, demonstrating that MISO effectively utilizes all predicted initial solutions. Hover a cell for its share; values are recovered from the paper figure's colour scale (≈).

4 Qualitative results

(a) Driving, single optimizer

(b) Cart-pole, multiple initial solutions

Figure 6. Example trajectories. (a) Single optimizer for the driving task. When the high-level planner abruptly modifies the reference path, warm-start and regression fail to adapt, while MISO closely follows the updated reference. (b) MISO's multiple initial solutions for cart-pole capture different modes of reaching the goal pose (dashed): sliding while balancing the pole, or swinging it down and back up on either side. Play to animate both panels, or drag the slider; hover a trajectory to isolate it; the legend toggles methods in (a). In (b) the pole tips trace the paper's curves exactly, the pole keeps its 1 m length, and the timing comes from a cart-pole under gravity (1 kg cart, 0.3 kg pole, as in the paper) fitted to each curve, since the recorded rollouts are not available.

5 Visualizations

Scenario

Figure 7. Driving scenarios. Select a nuPlan scenario to play its recording.

Citation

@article{sharony2024learningmultipleinitialsolutions,
  title={Learning Multiple Initial Solutions to Optimization Problems},
  author={Elad Sharony and Heng Yang and Tong Che and Marco Pavone and Shie Mannor and Peter Karkus},
  journal={arXiv preprint arXiv:2411.02158},
  year={2024},
}

References

Amos, B., et al. (2018). Differentiable MPC for end-to-end planning and control. NeurIPS.
Williams, G., et al. (2015). Model predictive path integral control using covariance variable importance sampling. arXiv:1509.01149.
Li, W., & Todorov, E. (2004). Iterative linear quadratic regulator design for nonlinear biological movement systems. ICINCO.
Caesar, H., et al. (2021). nuPlan: A closed-loop ML-based planning benchmark for autonomous vehicles. CVPR Workshop.
Guzman-Rivera, A., et al. (2012). Multiple choice learning: Learning to produce multiple structured outputs. NeurIPS.