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

Yu Hong Dai, Deren Han, Xiaoming YUAN, Wenxing Zhang

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

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 closedform 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.

Original languageEnglish
Pages (from-to)315-343
Number of pages29
JournalMathematics of Computation
Volume86
Issue number303
DOIs
Publication statusPublished - Jan 2017

Scopus Subject Areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Augmented Lagrangian method
  • Convex programming
  • Image processing
  • Method of multipliers
  • Splitting method

Fingerprint

Dive into the research topics of 'A sequential updating scheme of the lagrange multiplier for separable convex programming'. Together they form a unique fingerprint.

Cite this