Multiscale Methods for Discretized Continuous Optimization: Convergence and Cost Analysis
arXiv:2512.13993
The paper studies a multiscale algorithm that solves a sequence of increasingly fine discretizations of continuous optimization problems, using coarse solutions to warm‑start finer levels and proving faster convergence and lower total computational cost than single‑scale methods.
Abstract
Discretized versions of optimization problems over continuous arguments are routinely solved at a single fine resolution, incurring a per-iteration cost that grows, often superlinearly, with the number of grid points. This paper analyzes a multiscale method that instead solves a hierarchy of increasingly fine dyadic discretizations. Linear interpolation of each coarse solution warm starts the next finer scale using any q-linearly convergent update rule as the inner solver. Each coarse problem is a consistent discretization of the continuous problem. Structural properties such as convexity and smoothness are preserved. For problems with Lipschitz-continuous solutions, two variants of the method converge to the fine-scale solution with explicit error bounds. The fine-scale solution in turn approximates the continuous solution once the grid is sufficiently fine, with quantified constants. The total cost to reach a fixed accuracy is provably lower than that of single-scale optimization whenever the cost of one update grows at least linearly in the problem size. Numerical experiments on probability density demixing problems, including geological survey data, show four- to sevenfold speedups while using a fraction of the memory.
32 pages, 7 figures, 2 tables