First-order methods for constrained convex programming based on linearized augmented Lagrangian function

Abstract

First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one. For the first method, we establish its global iterate convergence as well as global sublinear and local linear convergence, and for the second method, we show a global sublinear convergence result in expectation. Numerical experiments are carried out on the basis pursuit denoising and a convex quadratically constrained quadratic program to show the empirical performance of the proposed methods. Their numerical behaviors closely match the established theoretical results.

References in corpus (6)

• Coordinate Friendly Structures, Algorithms and Applications
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• Randomized Primal-Dual Proximal Block Coordinate Updates
• On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
• A Primal-Dual Type Algorithm with the $O(1/t)$ Convergence Rate for Large Scale Constrained Convex Programs
• Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization

Cited by in corpus (7)

• Primal-dual stochastic gradient method for convex programs with many functional constraints
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Efficient Projection onto the ${\ell }_{\infty ,1}$ Mixed-Norm Ball using a Newton root search method
• A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
• Contraction Analysis on Primal-Dual Gradient Optimization
• Stochastic Primal-Dual Coordinate Method with Large Step Size for Composite Optimization with Composite Cone-constraints