论文标题
凸优化中基于拉格朗日的方法更快
Faster Lagrangian-Based Methods in Convex Optimization
论文作者
论文摘要
在本文中，我们旨在统一，简化和改善基于拉格朗日的凸优化问题的基于拉格朗日的方法的收敛率分析。我们首先介绍了Nice Primal算法图的概念，该图在统一和简化大多数基于拉格朗日的方法的分析中起着核心作用。然后，我们采用了精美的原始算法图，我们引入了一种多功能通用方案，该方案允许设计和分析更快的Lagrangian（flag）方法，其可证明是新的sublinear收敛速率，该方法以功能值表示，并违反了原始（非迫使）生成序列。为了证明我们的方法和结果的功能和多功能性，我们表明，最著名的标志性标志性基于拉格朗日的方案承认了一个不错的原始算法图，因此在其相应的标志中共享了新的更快的收敛速度。
In this paper, we aim at unifying, simplifying and improving the convergence rate analysis of Lagrangian-based methods for convex optimization problems. We first introduce the notion of nice primal algorithmic map, which plays a central role in the unification and in the simplification of the analysis of most Lagrangian-based methods. Equipped with a nice primal algorithmic map, we then introduce a versatile generic scheme, which allows for the design and analysis of Faster LAGrangian (FLAG) methods with new provably sublinear rate of convergence expressed in terms of function values and feasibility violation of the original (non-ergodic) generated sequence. To demonstrate the power and versatility of our approach and results, we show that most well-known iconic Lagrangian-based schemes admit a nice primal algorithmic map, and hence share the new faster rate of convergence results within their corresponding FLAG.
