Multiscale Methods for Discretized Continuous Optimization: Convergence and Cost Analysis
For practitioners solving discretized optimization problems, this provides a provably more efficient multiscale approach that lowers computational cost when per-iteration cost grows at least linearly with problem size.
This paper analyzes a multiscale method for discretized continuous optimization that solves a hierarchy of increasingly fine grids, achieving four- to sevenfold speedups on probability density demixing problems with reduced memory usage compared to single-scale optimization.
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.