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

2022/06/10 by Zhang, T., Xia, Y., Li, S. R.
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2206.05088

Abstract

We study the convergence rates of the classical Lagrangian-based methods and their variants for solving convex optimization problems with equality constraints. We present a generalized prediction-correction framework to establish O(1/K²) ergodic convergence rates. Under the strongly convex assumption, based on the presented prediction-correction framework, some Lagrangian-based methods with O(1/K²) ergodic convergence rates are presented, such as the augmented Lagrangian method with the indefinite proximal term, the alternating direction method of multipliers (ADMM) with a larger step size up to (1+√(5))/2, the linearized ADMM with the indefinite proximal term, and the multi-block ADMM type method (under an alternative assumption that the gradient of one block is Lipschitz continuous).

Related

• Lagrangian-based methods in convex optimization: prediction-correction frameworks with non-ergodic convergence rates
• Augmented Lagrangian methods for infeasible convex optimization problems and diverging proximal-point algorithms
• Two Innovations in Inexact Augmented Lagrangian Methods for Convex Optimization
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• Solving separable convex optimization problems: Faster prediction-correction framework