Multi-Trajectory Parallel-in-Iteration Optimization
Abstract
Previously, we developed a ``parallel-in-iteration'' optimization framework that uses multigrid reduction-in-time (MGRIT) to parallelize slowly converging optimization methods, such as gradient descent. Unlike time-dependent evolution problems, optimization requires only a final point with a sufficiently small gradient, rather than an accurate approximation of the entire trajectory of iterates. This motivates a different use of MGRIT: instead of repeatedly improving the approximation of a single long trajectory, we introduce restarted MGRIT (R-MGRIT), which performs one MGRIT iteration on a trajectory, takes the approximate final point as a new initial guess, and repeats the process on a new trajectory. Each restart thus defines a new all-at-once system, allowing progress toward the solution without accurately approximating the preceding trajectory. Moreover, we find that these trajectories can be shortened without increasing the number of restarts needed for convergence. We provide theoretical results comparing MGRIT and R-MGRIT for linear problems and demonstrate the convergence behavior of the shortened trajectories numerically for both linear and nonlinear problems. Shortening the trajectories increases the estimated parallel speedup while reducing the number of processors required.
Related
- Cost-Aware Iteration Allocation for Sequential Multi-Fidelity First-Order Optimization
- Cubature-Based Statistical Moment Steering for Nonlinear, Non-Gaussian Trajectory Optimization
- Learning-Accelerated Optimization-based Trajectory Planning for Cooperative Aerial-Ground Handover Missions
- Dual-Axis Policy Optimization for LLM Agents: Bayesian Feedback Attribution and Trajectory Mass Normalization
- Parallel Optimization: Theory, Algorithms, and Applications,
BibTeX
@misc{araujo2026multitrajectory,
title = {{Multi-Trajectory Parallel-in-Iteration Optimization}},
author = {Guilherme H. M. Araujo and Oliver A. Krzysik and Hans De Sterck},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03621},
eprint = {2611.03621},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03621},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Multi-Trajectory Parallel-in-Iteration Optimization
AU - Guilherme H. M. Araujo
AU - Oliver A. Krzysik
AU - Hans De Sterck
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03621
UR - https://arxiv.org/abs/2611.03621
AB - Previously, we developed a ``parallel-in-iteration'' optimization framework that uses multigrid reduction-in-time (MGRIT) to parallelize slowly converging optimization methods, such as gradient descent. Unlike time-dependent evolution problems, optimization requires only a final point with a sufficiently small gradient, rather than an accurate approximation of the entire trajectory of iterates. This motivates a different use of MGRIT: instead of repeatedly improving the approximation of a single long trajectory, we introduce restarted MGRIT (R-MGRIT), which performs one MGRIT iteration on a trajectory, takes the approximate final point as a new initial guess, and repeats the process on a new trajectory. Each restart thus defines a new all-at-once system, allowing progress toward the solution without accurately approximating the preceding trajectory. Moreover, we find that these trajectories can be shortened without increasing the number of restarts needed for convergence. We provide theoretical results comparing MGRIT and R-MGRIT for linear problems and demonstrate the convergence behavior of the shortened trajectories numerically for both linear and nonlinear problems. Shortening the trajectories increases the estimated parallel speedup while reducing the number of processors required.
ER -