Lagrangian-based methods in convex optimization: prediction-correction frameworks with non-ergodic convergence rates

2023/04/05 by Tao Zhang, Yong Xia, Zhang, Tao +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2304.02459

openalex publication_date 2023/04/05 · openalex created_date 2023/04/07 · openalex updated_date 2026/07/28

Abstract

Lagrangian-based methods are classical methods for solving convex optimization problems with equality constraints. We present novel prediction-correction frameworks for such methods and their variants, which can achieve O(1/k) non-ergodic convergence rates for general convex optimization and O(1/k²) non-ergodic convergence rates under the assumption that the objective function is strongly convex or gradient Lipschitz continuous. We give two approaches (updating~multiplier~once or~twice) to design algorithms satisfying the presented prediction-correction frameworks. As applications, we establish non-ergodic convergence rates for some well-known Lagrangian-based methods (esp., the ADMM type methods and the multi-block ADMM type methods).

Related

• Lagrangian-based methods in convex optimization: prediction-correction frameworks with ergodic convergence rates
• Solving separable convex optimization problems: Faster prediction-correction framework
• Two Innovations in Inexact Augmented Lagrangian Methods for Convex Optimization
• Augmented Lagrangian methods for infeasible convex optimization problems and diverging proximal-point algorithms
• Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization