ANALYSIS OF OPTIMIZATION ALGORITHMS VIA INTEGRAL QUADRATIC CONSTRAINTS: NONSTRONGLY CONVEX PROBLEMS
ANALYSIS OF OPTIMIZATION ALGORITHMS VIA INTEGRAL QUADRATIC CONSTRAINTS: NONSTRONGLY CONVEX PROBLEMS
复制标题
DOI：
10.1137/17m1136845
复制
发表时间：
2018-01-01
影响因子：
3.1
通讯作者：
Preciado, Victor M.
中科院分区：
文献类型：
--
作者：
Fazlyab, Mahyar;Ribeiro, Alejandro;Preciado, Victor M.
在本文中，我们开发了一个统一的框架，能够证明指数和次指数收敛率的迭代一阶优化算法的广泛范围。为此，我们构造了一组参数相关的非二次Lyapunov函数，除了证明渐近收敛外，还可以生成收敛率。利用鲁棒控制理论中的积分二次约束（IQCs），提出了一个线性矩阵不等式（LMI）来指导搜索Lyapunov函数的参数，从而建立一个速率界。基于这一结果，我们建立了一个半定规划框架，它的解产生了最优的收敛速率，该收敛速率可以用考虑的李雅普诺夫函数类来证明。我们通过分析（强）凸问题的梯度方法、近端算法及其加速变体来说明我们的结果的实用性。我们还发展了连续时间的对应物，即我们分析了涅斯特洛夫加速方法的梯度流和连续时间极限。
In this paper, we develop a unified framework capable of certifying both exponential and subexponential convergence rates for a wide range of iterative first-order optimization algorithms. To this end, we construct a family of parameter-dependent nonquadratic Lyapunov functions that can generate convergence rates in addition to proving asymptotic convergence. Using integral quadratic constraints (IQCs) from robust control theory, we propose a linear matrix inequality (LMI) to guide the search for the parameters of the Lyapunov function in order to establish a rate bound. Based on this result, we develop a semidefinite programming (SDP) framework whose solution yields the best convergence rate that can be certified by the class of Lyapunov functions under consideration. We illustrate the utility of our results by analyzing the gradient method, proximal algorithms, and their accelerated variants for (strongly) convex problems. We also develop the continuous-time counterpart, whereby we analyze the gradient flow and the continuous-time limit of Nesterov's accelerated method.