File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming

TitleOn full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
Authors
KeywordsOperator splitting methods
Jacobian decomposition
Convex programming
Augmented Lagrangian method
Convergence rate
Contraction methods
Issue Date2015
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/siopt.php
Citation
SIAM Journal on Optimization, 2015, v. 25, n. 4, p. 2274-2312 How to Cite?
Abstract© 2015 Societ y for Industrial and Applied Mathematics. The augmented Lagrangian method (ALM) is a benchmark for solving a convex minimization model with linear constraints. We consider the special case where the objective is the sum of m functions without coupled variables. For solving this separable convex minimization model, it is usually required to decompose the ALM subproblem at each iteration into m smaller subproblems, each of which only involves one function in the original objective. Easier subproblems capable of taking full advantage of the functions' properties individually could thus be generated. In this paper, we focus on the case where full Jacobian decomposition is applied to ALM subproblems, i.e., all the decomposed ALM subproblems are eligible for parallel computation at each iteration. For the first time, we show, by an example, that the ALM with full Jacobian decomposition could be divergent. To guarantee the convergence, we suggest combining a relaxation step and the output of the ALM with full Jacobian decomposition. A novel analysis is presented to illustrate how to choose refined step sizes for this relaxation step. Accordingly, a new splitting version of the ALM with full Jacobian decomposition is proposed. We derive the worst-case O(1/k) convergence rate measured by the iteration complexity (where k represents the iteration counter) in both the ergodic and nonergodic senses for the new algorithm. Finally, some numerical results are reported to show the efficiency of the new algorithm.
Persistent Identifierhttp://hdl.handle.net/10722/251134
ISSN
2020 Impact Factor: 2.85
2020 SCImago Journal Rankings: 2.066
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHe, Bingsheng-
dc.contributor.authorHou, Liusheng-
dc.contributor.authorYuan, Xiaoming-
dc.date.accessioned2018-02-01T01:54:42Z-
dc.date.available2018-02-01T01:54:42Z-
dc.date.issued2015-
dc.identifier.citationSIAM Journal on Optimization, 2015, v. 25, n. 4, p. 2274-2312-
dc.identifier.issn1052-6234-
dc.identifier.urihttp://hdl.handle.net/10722/251134-
dc.description.abstract© 2015 Societ y for Industrial and Applied Mathematics. The augmented Lagrangian method (ALM) is a benchmark for solving a convex minimization model with linear constraints. We consider the special case where the objective is the sum of m functions without coupled variables. For solving this separable convex minimization model, it is usually required to decompose the ALM subproblem at each iteration into m smaller subproblems, each of which only involves one function in the original objective. Easier subproblems capable of taking full advantage of the functions' properties individually could thus be generated. In this paper, we focus on the case where full Jacobian decomposition is applied to ALM subproblems, i.e., all the decomposed ALM subproblems are eligible for parallel computation at each iteration. For the first time, we show, by an example, that the ALM with full Jacobian decomposition could be divergent. To guarantee the convergence, we suggest combining a relaxation step and the output of the ALM with full Jacobian decomposition. A novel analysis is presented to illustrate how to choose refined step sizes for this relaxation step. Accordingly, a new splitting version of the ALM with full Jacobian decomposition is proposed. We derive the worst-case O(1/k) convergence rate measured by the iteration complexity (where k represents the iteration counter) in both the ergodic and nonergodic senses for the new algorithm. Finally, some numerical results are reported to show the efficiency of the new algorithm.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/siopt.php-
dc.relation.ispartofSIAM Journal on Optimization-
dc.subjectOperator splitting methods-
dc.subjectJacobian decomposition-
dc.subjectConvex programming-
dc.subjectAugmented Lagrangian method-
dc.subjectConvergence rate-
dc.subjectContraction methods-
dc.titleOn full Jacobian decomposition of the augmented Lagrangian method for separable convex programming-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1137/130922793-
dc.identifier.scopuseid_2-s2.0-84953267278-
dc.identifier.volume25-
dc.identifier.issue4-
dc.identifier.spage2274-
dc.identifier.epage2312-
dc.identifier.isiWOS:000367019700013-
dc.identifier.issnl1052-6234-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats