Differential estimates for fast first-order multilevel nonconvex optimisation
This work addresses optimization challenges in bilevel and PDE-constrained problems, which is incremental as it builds on existing methods with adaptations for inexact settings.
The paper tackles the problem of fast first-order multilevel nonconvex optimization by developing differential estimates for composite functions, enabling a single-loop method that interweaves outer optimization updates with inner problem steps, and demonstrates numerical evaluation on Electrical Impedance Tomography and minimal surface control.
With a view on bilevel and PDE-constrained optimisation, we develop iterative estimates $\widetilde{F'}(x^k)$ of $F'(x^k)$ for composite functions $F :=J \circ S$, where $S$ is the solution mapping of the inner optimisation problem or PDE. The idea is to form a single-loop method by interweaving updates of the iterate $x^k$ by an outer optimisation method, with updates of the estimate by single steps of standard optimisation methods and linear system solvers. When the inner methods satisfy simple tracking inequalities, the differential estimates can almost directly be employed in standard convergence proofs for general forward-backward type methods. We adapt those proofs to a general inexact setting in normed spaces, that, besides our differential estimates, also covers mismatched adjoints and unreachable optimality conditions in measure spaces. As a side product of these efforts, we provide improved convergence results for nonconvex Primal-Dual Proximal Splitting (PDPS). We numerically evaluate our methods on Electrical Impedance Tomography (EIT) and minimal surface control.