- Indefinite linearized augmented Lagrangian method for convex programming with linear inequality constraints Bingsheng He (hebmanju.edu.cn) Shengjie Xu (xsjnsu163.com) Jing Yuan (jyuanxidian.edu.cn) Abstract: The augmented Lagrangian method (ALM) is a benchmark for tackling the convex optimization problem with linear constraints; ALM and its variants for linearly equality-constrained convex minimization models have been well studied in the literatures. However, much less attention has been paid to ALM for efficiently solving the linearly inequality-constrained convex minimization model. In this paper, we exploit an enlightening reformulation of the most recent indefinite linearized (equality-constrained) ALM, and present a novel indefinite linearized ALM scheme for efficiently solving the convex optimization problem with linear inequality constraints. The proposed method enjoys great advantages, especially for large-scale optimization cases, in two folds mainly: first, it significantly simplifies the optimization of the challenging key subproblem of the classical ALM by employing its linearized reformulation, while keeping low complexity in computation; second, we prove that a smaller proximity regularization term is needed for convergence guarantee, which allows a bigger step-size and can largely reduce required iterations for convergence. Moreover, we establish an elegant global convergence theory of the proposed scheme upon its equivalent compact expression of prediction-correction, along with a worst-case $\mathcal{O}(1/N)$ convergence rate. Numerical results demonstrate that the proposed method can reach a faster converge rate for a higher numerical efficiency as the regularization term turns smaller, which confirms the theoretical results presented in this study. Keywords: augmented Lagrangian method, convex programming, convergence analysis, inequality constraints, image segmentation Category 1: Convex and Nonsmooth Optimization Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF]Entry Submitted: 05/10/2019Entry Accepted: 05/10/2019Entry Last Modified: 05/03/2021Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.