Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity

• 成果类型: Article
• 署名作者: Attouch, Hedy; Chbani, Zaki; Peypouquet, Juan; Redont, Patrick
• 署名单位: Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); Cadi Ayyad University of Marrakech; Universidad Tecnica Federico Santa Maria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0992-8
• 发表日期: 2018
• 页码: 123-175
• 关键词: maximal monotone-operators; proximal method; EQUATIONS; BEHAVIOR; SYSTEM

摘要

In a Hilbert space setting H, we study the fast convergence properties as t -> +infinity of the trajectories of the second-order differential equation x(t) + alpha/t(x) over dot(t) + del Phi(x(t)) = g(t), where del Phi is the gradient of a convex continuously differentiable function Phi : H -> R, alpha is a positive parameter, and g : [t(0),+infinity[-> H is a small perturbation term. In this inertial system, the viscous damping coefficient alpha/t vanishes asymptotically, but not too rapidly. For alpha >= 3, and integral(+infinity)(t0) t parallel to g(t)parallel to dt < +infinity, just assuming that argmin Phi not equal theta, we show that any trajectory of the above system satisfies the fast convergence property Phi(x(t)) - min(H) Phi <= C/t(2). Moreover, for alpha > 3, any trajectory converges weakly to a minimizer of Phi. The strong convergence is established in various practical situations. These results complement the O(t(-2)) rate of convergence for the values obtained by Su, Boyd and Candes in the unperturbed case g = 0. Time discretization of this system, and some of its variants, provides new fast converging algorithms, expanding the field of rapid methods for structured convex minimization introduced by Nesterov, and further developed by Beck and Teboulle with FISTA. This study also complements recent advances due to Chambolle and Dossal.