标题： 学习以保证优化：线性收敛算法的完整表征 显示英文标题

标题： Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms

摘要： 在高风险的工程应用中，优化算法必须在数学定义的问题类上提供可证明的最坏情况保证。 然而，为最坏情况设计会不可避免地牺牲在实际中经常出现的具体问题实例上的性能。 我们解决的问题是增强给定的线性收敛算法，以在受限的目标问题集上提高其平均情况性能——例如，将现成的求解器定制用于模型预测控制（MPC）以应用于特定的动力系统——同时保持在整个问题类上的最坏情况保证。 为了达到这个目标，我们表征了对于非光滑复合优化问题类实现线性收敛的算法类。 特别是，从一个基本的线性收敛算法出发，我们推导出所有且仅有的对其更新规则的修改，这些修改保持其收敛性质。 我们的结果适用于增强遗留算法，如非凸、梯度主导函数的梯度下降；强凸函数的Nesterov加速方法；以及在多面体可行性集上的投影方法。 我们在求解具有严格迭代预算的优化问题中展示了该方法的有效性，应用于病态线性方程组和线性系统的模型预测控制（MPC）。 显示英文摘要

摘要： In high-stakes engineering applications, optimization algorithms must come with provable worst-case guarantees over a mathematically defined class of problems. Designing for the worst case, however, inevitably sacrifices performance on the specific problem instances that often occur in practice. We address the problem of augmenting a given linearly convergent algorithm to improve 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 its worst-case guarantees across the entire problem class. Toward this goal, we characterize the class of algorithms that achieve linear convergence for classes of nonsmooth composite optimization problems. In particular, starting from a baseline linearly convergent algorithm, we derive all - and only - the modifications to its update rule that maintain its convergence properties. Our results apply to augmenting legacy algorithms such as gradient descent for nonconvex, gradient-dominated functions; Nesterov's accelerated method for strongly convex functions; and projected methods for optimization over polyhedral feasibility sets. We showcase effectiveness of the approach on solving optimization problems with tight iteration budgets in application to ill-conditioned systems of linear equations and MPC for linear systems.