A simplified view of first order methods for optimization

• 成果类型: Article; Proceedings Paper
• 署名作者: Teboulle, Marc
• 署名单位: Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1284-2
• 发表日期: 2018
• 页码: 67-96
• 关键词: proximal point algorithm; projected subgradient methods; monotone-operators; variational-inequalities; minimization algorithm; convergence analysis; interior gradient; WEAK-CONVERGENCE; dynamical-system; descent methods

摘要

We discuss the foundational role of the proximal framework in the development and analysis of some iconic first order optimization algorithms, with a focus on non-Euclidean proximal distances of Bregman type, which are central to the analysis of many other fundamental first order minimization relatives. We stress simplification and unification by highlighting self-contained elementary proof-patterns to obtain convergence rate and global convergence both in the convex and the nonconvex settings, which in turn also allows to present some novel results.