Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A sequential updating scheme of the Lagrange multiplier for separable convex programming

Authors: Yu-Hong Dai, Deren Han, Xiaoming Yuan and Wenxing Zhang
Journal: Math. Comp. 86 (2017), 315-343
MSC (2010): Primary 90C25, 65K10, 94A08, 68W10
Published electronically: April 13, 2016
MathSciNet review: 3557801
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. Solving the augmented subproblems over the primal variables can be regarded as sequentially providing inputs for updating the Lagrange multiplier (i.e., the dual variable). We consider the separable case of a convex minimization problem where its objective function is the sum of more than two functions without coupled variables. When applying the ALM to this case, at each iteration we can (sometimes must) split the resulting augmented subproblem in order to generate decomposed subproblems which are often easy enough to have closed-form solutions. But the decomposition of primal variables only provides less accurate inputs for updating the Lagrange multiplier, and it points out the lack of convergence for such a decomposition scheme. To remedy this difficulty, we propose to update the Lagrange multiplier sequentially once each decomposed subproblem over the primal variables is solved. This scheme updates both the primal and dual variables in Gauss-Seidel fashion. In addition to the exact version which is useful enough for the case where the functions in the objective are all simple such that the decomposed subproblems all have closed-form solutions, we investigate an inexact version of this scheme which allows the decomposed subproblems to be solved approximately subject to certain inexactness criteria. Some preliminary numerical results when the proposed scheme is respectively applied to an image decomposition problem and an allocation problem are reported.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C25, 65K10, 94A08, 68W10

Retrieve articles in all journals with MSC (2010): 90C25, 65K10, 94A08, 68W10

Additional Information

Yu-Hong Dai
Affiliation: LSEC, Institute of Computational Mathematics, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100190, People’s Republic of China

Deren Han
Affiliation: School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China

Xiaoming Yuan
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong, People’s Republic of China

Wenxing Zhang
Affiliation: School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China

Keywords: Convex programming, augmented Lagrangian method, splitting method, method of multipliers, image processing
Received by editor(s): June 29, 2013
Received by editor(s) in revised form: August 16, 2014, and July 27, 2015
Published electronically: April 13, 2016
Additional Notes: The first author was partially supported by the China National Funds for Distinguished Young Scientists Grant 11125107, the Key Project of Chinese National Programs for Fundamental Research and Development Grant 2015CB856000, NSFC Grant 11331012, and the CAS Program for Cross $&$ Cooperative Team of the Science $&$ Technology Innovation.
The second author was supported by a project funded by PAPD of Jiangsu Higher Education Institutions and the NSFC grants 11371197, 11431002
The third author was supported by the General Research Fund of Hong Kong: HKBU203613
The fourth author was supported by the NSFC grant 11301055
Article copyright: © Copyright 2016 American Mathematical Society