Abstract
In high-stakes engineering applications, optimization algorithms must comewith provable worst-case guarantees over a mathematically defined class ofproblems. Designing for the worst case, however, inevitably sacrificesperformance on the specific problem instances that often occur in practice. Weaddress the problem of augmenting a given linearly convergent algorithm toimprove its average-case performance on a restricted set of target problems -for example, tailoring an off-the-shelf solver for model predictive control(MPC) for an application to a specific dynamical system - while preserving itsworst-case guarantees across the entire problem class. Toward this goal, wecharacterize the class of algorithms that achieve linear convergence forclasses of nonsmooth composite optimization problems. In particular, startingfrom a baseline linearly convergent algorithm, we derive all - and only - themodifications to its update rule that maintain its convergence properties. Ourresults apply to augmenting legacy algorithms such as gradient descent fornonconvex, gradient-dominated functions; Nesterov's accelerated method forstrongly convex functions; and projected methods for optimization overpolyhedral feasibility sets. We showcase effectiveness of the approach onsolving optimization problems with tight iteration budgets in application toill-conditioned systems of linear equations and MPC for linear systems.