PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Multiple Initial Solutions to Optimization Problems

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

arXiv:2411.02158v2cs.LGcs.AIcs.ROcs.SYeess.SY

TL;DR

Sequential optimization under tight runtime constraints is sensitive to its initial solution, and difficult instances can make one good start hard to predict. MISO learns multiple diverse candidates and uses them to initialize one or several optimizers. Across optimal-control evaluations, it significantly outperforms existing initialization methods and scales efficiently with the number of initializations.

  • Problem

    For challenging optimization instances, predicting one good initial solution is difficult, despite the sensitivity of local optimization performance to initialization.

    Source: §1 · p. 1

  • Method

    MISO trains a neural network to predict multiple diverse initial solutions for use by a single optimizer or several optimizers.

    Source: §1 · p. 1

  • Results

    MISO significantly outperforms heuristic, single-solution, and ensemble initialization methods across three robot-control tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Optimal-control experiments show that learning multiple diverse initial solutions can enhance local optimizers' reliability and efficiency across settings.

    Source: §7 · p. 8

    MISO depends on training-data coverage and quality and does not directly interact with the optimizer or underlying objective function.

    Source: §7 · p. 8

Abstract

from arXiv · show

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 MISO (https://github.com/EladSharony/miso).

1. Introduction

MISO learns multiple diverse initial solutions to address the difficulty of predicting one good start for challenging optimization instances. It offers single-optimizer and multiple-optimizers strategies and significantly outperforms existing initialization methods across three robot-control tasks.

1. Introduction

  • Sequential optimization under tight runtime constraints is sensitive to initialization, while non-convex landscapes or rapidly changing instances make one good prediction difficult.Poor initialization can produce suboptimal solutions or prevent convergence within the allowed time.Source: §1 · p. 1
  • A single neural network predicts multiple initial solutions for either selection by one optimizer or use by several optimizers, potentially in parallel.The multiple-optimizer strategy chooses the best solution afterward.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Given problem-instance parameters, the network predicts K candidates trained for solution quality and diversity using winner-takes-all and dispersion-based losses.The paper also combines the two loss strategies.Source: §1 · p. 1
  • Including an existing initialization among the predictions guarantees a final cost equal to or lower than that from the default initialization.The framework can therefore retain an existing initialization strategy alongside learned candidates.Source: §1 · pp. 1–2
  • MISO significantly outperforms heuristic, single-solution, and ensemble initialization methods across three robot-control tasks.The evaluation uses DDP for cart-pole, MPPI for reacher, and iLQR for autonomous driving.Source: §1 · p. 2

2. Related Work

Related work applies learning to optimization algorithms, initial-solution prediction, and parallel optimization. MISO differs by using one neural network to generate multiple initializations without strong task or optimizer assumptions.

Learning for optimization

  • Learning-based optimization has replaced components of classical convex optimization algorithms; newer work aims to replace methods end-to-end or generate algorithms, while other work enhances optimization-based control and learns constraints, objective functions, and system dynamics.Source: §2 · p. 2

Learning initial solutions

  • Initial-solution work includes heuristic warm-starts and learned predictions for mixed-integer programming, power flow, trajectory optimization, and robot control.Robot-control predictors include Chen et al. (2022a), Wang & Ba (2019), and Lembono et al. (2020); differentiable methods also learn through optimization (Amos et al., 2018; East et al., 2019).Source: §2 · pp. 2–3
  • Unlike prior learning-based initializers, MISO predicts multiple initializations without strong assumptions about the task or optimizer.Bouzidi et al. (2023) also used multiple initializations, but for autonomous driving with a dedicated motion-prediction module.Source: §2 · p. 3

Parallel optimizers

  • Parallel optimization methods include GPU-based and multi-maneuver approaches, but the cited works do not use learning to generate initializations.Lembono et al. (2020) explored learning-based initialization using prior-solution databases and ensemble-learned models; MISO reports outperforming that ensemble approach.Source: §2 · p. 3

3. Initializing optimizers

The section frames optimization as finding an optimum for a parameterized problem with a local algorithm under a runtime limit. It describes warm-starting from a related instance and the risk when successive instances change substantially.

3. Initializing optimizers

  • A problem instance is parameterized by ψ, while the local optimizer seeks an optimum of objective J using an initial solution and a runtime limit.The setup identifies x as the variable vector and g and h as inequality and equality constraints.Source: §3 · p. 3
  • A warm-start reuses the solution from a previously solved similar instance, typically shifted and padded with zeros in optimal control.The warm-start is the prior solution from the previous timestep.Source: §3 · p. 3
  • Large changes between consecutive instances can make a warm-start poor and prevent the optimizer from finding a good solution within its time limit.Examples include a traffic-light change or a suddenly appearing pedestrian that alters a driving reference trajectory or constraints.Source: §3 · p. 3

4. Learning Multiple Initial SOlutions

MISO predicts diverse initial solutions to cover promising regions of an optimization landscape, then uses them through either a single optimizer or multiple optimizers. The section develops the predictor, selection strategies, diversity-promoting training, an illustrative example, and an optimal-control application.

4.1. Multi-output predictor

  • A Transformer maps each problem instance ψ to K candidate initial solutions, trained on instance and (near-)optimal-solution pairs that can be generated offline.The predictor is presented as a standard Transformer chosen for simplicity and clarity.Source: §4.1 · pp. 3–4

4.2. Optimization with multiple initial solutions

  • MISO either selects one candidate for a single optimizer or starts multiple optimizers from distinct candidates; retaining the default initialization guarantees an equal-or-better outcome.The single-optimizer selection function can minimize the objective or use other criteria such as robustness or constraint satisfaction.Source: §4.2 · p. 4

4.3. Training strategies

  • Training combines regression toward near-optimal solutions with diversity, using pairwise-distance, winner-takes-all, or mixture losses to promote multimodal outputs.The pairwise-distance loss balances accuracy against dispersion; winner-takes-all is hyperparameter-free, while mixture loss combines the approaches.Source: §4.3 · p. 4

4.4. Illustrative example

  • In the toy cost landscape, single-output regression and ensembles cluster near local minimum B, while multi-output winner-takes-all and mixture losses reach a global minimum.The illustrated landscape has global minima at A and C, with local minimum B between them.Source: §4.4 · p. 5, Figure 2 · p. 5

4.5. Application to optimal control

  • For optimal control, MISO predicts control sequences that define trajectories through system dynamics; experiments use state-control loss, which improved both MISO and baseline learning methods.The paper focuses its evaluation on optimal control, while describing MISO as applicable to a broader class of sequential optimization problems.Source: §4.5 · p. 5

5. Experimental setup

The experiments evaluate three optimal-control tasks with distinct local optimizers, compare single- and multiple-initialization baselines, and assess one-off and sequential settings. Training data comes from warm-started instances paired with solutions from an oracle optimizer run under a longer time limit.

Tasks

  • Cart-pole uses DDP, reacher uses MPPI, and autonomous driving uses iLQR across the three benchmark tasks.The tasks cover pole balancing, a two-link arm reaching a target, and urban trajectory tracking.Source: §5 · pp. 5–6

Baselines

  • Baselines include warm-start and single-output regression, perturbed and multi-output variants, ensembles, and three MISO loss variants.Oracle Proxy uses optimization with unlimited runtime and also generates training data.Source: §5 · p. 6

Evaluation settings

  • One-off evaluation measures mean optimizer-output cost on isolated instances, while sequential evaluation executes solutions and re-optimizes from the resulting state.Performance is averaged over problems within sequences and then across sequences.Source: §5 · p. 6

Implementation details

  • Training instances are generated with default warm-starts and paired with solutions from an oracle optimizer given a longer runtime; inference was under 0.85 ms for all methods except the ensemble.In autonomous driving, optimizer runtime was reduced to account for inference time.Source: §5 · p. 6

6. Results

MISO winner-takes-all and MISO mix achieve the lowest mean costs across tasks in the single-optimizer setting, while multi-output methods also improve results with multiple optimizers. MISO scales across values of K, and including a warm-start candidate preserves or improves the resulting cost.

Single optimizer

  • MISO winner-takes-all and MISO mix achieve the lowest mean costs across tasks in the single-optimizer setting.The reported comparison covers multiple initialization methods and tasks.Source: §6 · p. 6, Table 1 · p. 7

Multiple optimizers

  • Learning-based multi-output approaches further improve results with multiple optimizers, which consistently outperform the single-optimizer setting.The authors attribute the multiple-optimizer improvement to increased exploration of the solution space.Source: Table 2 · p. 7, §6 · p. 7

Scaling with the number of initial solutions

  • MISO scales effectively as K increases, outperforming other approaches across values of K while its inference time remains almost constant.Ensemble inference time grows with K; all MISO outputs remain useful as K increases.Source: §6 · p. 7, Figure 4 · p. 8

Performance guarantees

  • Adding the warm-start to MISO’s candidates yields a best initial-solution cost no higher than warm-start in single-optimizer tests, and a final-solution cost no higher in multiple-optimizer tests.Mean costs remained mostly similar to MISO and improved slightly in some cases.Source: §6 · p. 7

Qualitative results

  • After an abrupt reference-path change in driving, MISO winner-takes-all follows the new path, while the warm-start, regression, and model ensemble do not find a good initialization.For cart-pole, MISO outputs capture balance, left-swing, and right-swing solution modes.Source: §6 · p. 7, Figure 5 · p. 8

7. Conclusions and Future Work

The paper concludes that MISO improves local optimization across settings and scales with the number of initializations. It identifies training-data dependence and difficult high-dimensional solutions as limitations, and proposes objective-aware training, reinforcement learning, and other extensions.

Conclusions

  • MISO consistently outperforms baseline approaches in optimal-control experiments and scales efficiently with the number of initializations.The framework learns multiple diverse initial solutions for local optimization algorithms.Source: §7 · p. 8

Limitations

  • MISO depends on training-data coverage and quality, and accurately learning candidates may become challenging for highly complex, high-dimensional solutions.The regression-loss assumption that closer-to-global-optimum starts improve optimization may not hold in complex constrained landscapes.Source: §7 · p. 8

Future work

  • Future work could incorporate the optimization objective into training or use reinforcement learning, although RL would require many optimizer runs during training.The proposed RL reward is the negative cost of the optimizer’s final solution.Source: §7 · p. 8
  • Other proposed extensions include probabilistic models, alternative selection criteria, and heterogeneous parallel optimizers, with mode collapse, diversity, and inference overhead remaining challenges for probabilistic models.The paper also names applications beyond optimal control, including localization, financial optimization, and traffic routing.Source: §7 · p. 8

A.1. Detailed Descriptions of Baseline Optimizers

The appendix describes DDP, MPPI, and iLQR as the baseline optimizers used in the evaluations. Their approaches range from first-order linearization to stochastic sampling and iterative trajectory optimization.

Overview

  • The evaluations use these three algorithms as commonly used and effective approaches for optimal-control problems across domains.Source: §A.1 · p. 12

First-order Box Differential Dynamic Programming (DDP)

  • First-order Box-DDP uses first-order linearization rather than second-order derivatives, reducing computational complexity while handling box constraints on states and controls.The description builds on the simplified Box-DDP version introduced by Amos et al. (2018).Source: §A.1 · p. 12

Model Predictive Path Integral (MPPI)

  • MPPI iteratively refines control inputs by sampling perturbed control sequences, simulating trajectories, and updating inputs with a weighted average favoring lower-cost trajectories.It is described as a sampling-based model predictive control algorithm.Source: §A.1 · p. 12

Iterative Linear Quadratic Regulator (iLQR)

  • iLQR iteratively refines control sequences using linearized dynamics and a quadratic cost approximation, alternating forward simulation with backward control updates.The evaluated implementation is provided in the nuPlan simulator.Source: §A.1 · p. 12

A.2. Detailed Task Descriptions and Hyperparameters

The experiments cover cart-pole, reacher, and autonomous-driving control tasks, with task-specific dynamics, controls, and hyperparameters. The driving evaluation fixes the total runtime budget across initialization and optimization.

Cart-pole

  • Cart-pole swings a pole upright while moving the cart to a target, using a four-dimensional state and one force input; the control horizon is 10 steps.Episodes last up to 50 steps, and the initial cart position and target are sampled from −2 to 2 m.Source: §A.2 · p. 12

Reacher

  • Reacher moves a two-link planar arm’s end-effector to a random target, with joint angles and velocities as state and two joint torques as controls.The prediction horizon is 10; online MPPI uses 3 samples, compared with 50 for the oracle optimizer.Source: §A.2 · pp. 12–13

Autonomous Driving

  • Autonomous driving evaluates trajectory tracking in urban scenarios using a five-dimensional vehicle state, acceleration and steering-rate controls, and PDM-generated references.The horizon is 40 steps; total runtime includes initialization and optimization, with a 5 ms limit.Source: §A.2 · p. 13

A.3. Network Architecture and Training Details

The experiments use a task-configured Transformer to predict multiple control trajectories from warm-start information. Training data comes from optimizer and oracle rollouts, with standardized features and AdamW training.

A.3. Network Architecture and Training Details

  • The base model is a standard Transformer with absolute positional embeddings, a linear decoder, and output scaling, configured for each task.Its input combines the warm-start state-trajectory error with the warm-start control trajectory, and it predicts K control trajectories for the next optimization step.Source: §A.3 · p. 13, Table 3 · p. 13
  • Training data pairs optimizer-generated warm-start rollouts with oracle-optimizer rollouts, and includes 500,000 instances per task.The oracle uses enhanced capabilities such as more optimization steps or additional sampled trajectories; features are standardized before AdamW training with gradient-norm clipping.Source: §A.3 · pp. 13–14, Table 4 · p. 14

A.4. Descriptions of Baseline Methods

The appendix compares initialization baselines and MISO variants, reports their performance across tasks and evaluation settings, and describes extensions to selection, training, and inference. Its findings include improved costs across varying candidate counts, efficient multi-output inference, and benefits from state loss in sequential optimization.

A.4. Descriptions of Baseline Methods

  • The baselines span warm-start and oracle strategies, single-output regression, ensembles, perturbations, and multi-output losses; naive summed losses risk mode collapse.Pairwise-distance and winner-takes-all losses address multimodality differently; the mixed variant combines them but adds hyperparameter and stability complexity.Source: §A.4 · pp. 14–15

A.5. Illustrative Example

  • In the illustrative multimodal example, winner-takes-all and MISO mix predict both optimal sequences, unlike ensemble and pairwise-distance results that remain away from either optimum.The example's non-convex cost has two global minima.Source: §A.5 · p. 15, Table 5 · p. 15

A.6. Inference Time: Ensemble vs. Multi-Output Models

  • The multi-output model's inference time changes little as K increases, while ensemble inference time rises significantly, limiting its practicality at larger K.The comparison measures mean inference time on CPU and GPU; the paper identifies multi-output as viable for time-sensitive settings.Source: Figure 6 · p. 15, §A.6 · p. 16

A.7. State Loss

  • State loss benefits both one-off and sequential optimization, with a more pronounced improvement in sequential settings and at longer horizons.The reported difference between using and omitting state loss grows from cart-pole's H = 9 to driving's H = 40; the gap is larger for single-output regression.Source: §A.7 · pp. 16–17, Table 6 · p. 17

A.8. Mode frequency

  • MISO winner-takes-all keeps every output mode active, and even less-frequent modes sometimes identify the optimal action.Figure 7 shows selection frequency by mode; Figure 8 compares MISO winner-takes-all and MISO mix with the approximately uniform ensemble distribution.Source: §A.8 · p. 17, Figure 7 · p. 17, Figure 8 · p. 17

A.9. Mean Cost Sequential Optimization

  • Across cart-pole and reacher, MISO scales effectively and outperforms other approaches as K varies.Figure 9 reports mean cost for both environments under single- and multiple-optimizer settings.Source: Figure 9 · p. 18, §A.9 · p. 18

A.10. Selection Function Λ

  • The selection function can prioritize constraints, robustness, or context, and may be learned; evaluations distinguish isolated one-off problems from sequential environment interaction.The appendix also notes that the multi-output concept can transfer to other neural backbones, while sampling-based architectures can scale poorly with K under strict runtime constraints.Source: §A.10.1 · p. 19, §A.10.2 · p. 19, §A.11 · p. 19

A.15. Experiments on combining MISO with warm-start

  • Adding warm-start as an extra candidate consistently improves over warm-start alone, and sometimes improves on MISO without that candidate.MISO⋆ denotes the setting that adds the heuristic warm-start candidate.Source: §A.15 · p. 20, Table 7 · p. 20, Table 8 · p. 20
Loading 2411.02158v2…