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
DOI: https://doi.org/10.1090/mcom/3104
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?)

  • [1] J. F. Aujol, G. Gilboa, T. Chan, and S. Osher, Structure-texture image decomposition--modeling, algorithms, and parameter selection, Int. J. Comput. Vision 67 (2006), 111-136.
  • [2] Heinz H. Bauschke and Patrick L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, with a foreword by Hédy Attouch. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2011. MR 2798533 (2012h:49001)
  • [3] Dimitri P. Bertsekas, Constrained optimization and Lagrange multiplier methods, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 690767 (84k:90068)
  • [4] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996.
  • [5] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3 (2010), 1-122.
  • [6] Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program. 155 (2016), no. 1-2, Ser. A, 57-79. MR 3439797, https://doi.org/10.1007/s10107-014-0826-5
  • [7] Patrick L. Combettes and Jean-Christophe Pesquet, Proximal splitting methods in signal processing, Fixed-point algorithms for inverse problems in science and engineering, Springer Optim. Appl., vol. 49, Springer, New York, 2011, pp. 185-212. MR 2858838 (2012i:90117), https://doi.org/10.1007/978-1-4419-9569-8_10
  • [8] Etienne Corman and Xiaoming Yuan, A generalized proximal point algorithm and its convergence rate, SIAM J. Optim. 24 (2014), no. 4, 1614-1638. MR 3268621, https://doi.org/10.1137/130940402
  • [9] Jim Douglas Jr. and H. H. Rachford Jr., On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc. 82 (1956), 421-439. MR 0084194 (18,827f)
  • [10] Jonathan Eckstein and Wang Yao, Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives, Pac. J. Optim. 11 (2015), no. 4, 619-644. MR 3420805
  • [11] Francisco Facchinei and Jong-Shi Pang, Finite-dimensional variational inequalities and complementarity problems. Vols. I, II, Springer Series in Operations Research, Springer-Verlag, New York, 2003. MR 1955648 (2004g:90003a)
  • [12] D. Gabay, Applications of the method of multipliers to variational inequalities, In: Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (M. Fortin, R. Glowinski), North-Holland, Amsterdam, 1983, pp. 299-331.
  • [13] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl. 2 (1976), 17-40.
  • [14] Roland Glowinski, Numerical methods for nonlinear variational problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. MR 737005 (86c:65004)
  • [15] Roland Glowinski, On alternating direction methods of multipliers: a historical perspective, Modeling, simulation and optimization for science and technology, Comput. Methods Appl. Sci., vol. 34, Springer, Dordrecht, 2014, pp. 59-82. MR 3330832, https://doi.org/10.1007/978-94-017-9054-3_4
  • [16] Roland Glowinski and Patrick Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics, SIAM Studies in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1060954 (91f:73038)
  • [17] Roland Glowinski, Tommi Kärkkäinen, and Kirsi Majava, On the convergence of operator-splitting methods, Numerical methods for scientific computing. Variational problems and applications, Internat. Center Numer. Methods Eng. (CIMNE), Barcelona, 2003, pp. 67-79. MR 2427782 (2009j:65284)
  • [18] R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41-76 (French, with Loose English summary). MR 0388811 (52 #9645)
  • [19] Tom Goldstein and Stanley Osher, The split Bregman method for $ L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323-343. MR 2496060 (2010e:65087), https://doi.org/10.1137/080725891
  • [20] Deren Han and Xiaoming Yuan, A note on the alternating direction method of multipliers, J. Optim. Theory Appl. 155 (2012), no. 1, 227-238. MR 2983116, https://doi.org/10.1007/s10957-012-0003-z
  • [21] Per Christian Hansen, James G. Nagy, and Dianne P. O'Leary, Deblurring images, Matrices, spectra, and filtering, Fundamentals of Algorithms, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. MR 2271138 (2008d:94007)
  • [22] Bingsheng He, Li-Zhi Liao, Deren Han, and Hai Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program. 92 (2002), no. 1, Ser. A, 103-118. MR 1892298 (2003b:90111), https://doi.org/10.1007/s101070100280
  • [23] B. S. He, H. Liu, J. Lu, and X. M. Yuan, Application of the strictly contractive Peaceman-Rachford splitting method to multi-block convex programming, manuscript (2014).
  • [24] Bingsheng He, Han Liu, Zhaoran Wang, and Xiaoming Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim. 24 (2014), no. 3, 1011-1040. MR 3231988, https://doi.org/10.1137/13090849X
  • [25] Bingsheng He, Min Tao, and Xiaoming Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim. 22 (2012), no. 2, 313-340. MR 2968856, https://doi.org/10.1137/110822347
  • [26] Bingsheng He and Hai Yang, Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities, Oper. Res. Lett. 23 (1998), no. 3-5, 151-161. MR 1677664 (2000d:90089), https://doi.org/10.1016/S0167-6377(98)00044-3
  • [27] Bingsheng He and Xiaoming Yuan, On the $ O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal. 50 (2012), no. 2, 700-709. MR 2914282, https://doi.org/10.1137/110836936
  • [28] Magnus R. Hestenes, Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969), 303-320. MR 0271809 (42 #6690)
  • [29] M. Hong and Z. Q. Luo, On the linear convergence of alternating direction method of multipliers, Math. Program., to appear.
  • [30] P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979), no. 6, 964-979. MR 551319 (81g:47070), https://doi.org/10.1137/0716071
  • [31] Zhi-Quan Luo and Paul Tseng, On the convergence rate of dual ascent methods for linearly constrained convex minimization, Math. Oper. Res. 18 (1993), no. 4, 846-867. MR 1251683 (95a:90070), https://doi.org/10.1287/moor.18.4.846
  • [32] S. Q. Ma, Alternating proximal gradient method for convex minimization, preprint (2012).
  • [33] B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (1970), no. Ser. R-3, 154-158 (French). MR 0298899 (45 #7948)
  • [34] Yves Meyer, Oscillating patterns in image processing and nonlinear evolution equations, The fifteenth Dean Jacqueline B. Lewis memorial lectures. University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, 2001. MR 1852741 (2002j:43001)
  • [35] Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273-299 (French). MR 0201952 (34 #1829)
  • [36] Stanley Osher, Andrés Solé, and Luminita Vese, Image decomposition and restoration using total variation minimization and the $ H^{-1}$ norm, Multiscale Model. Simul. 1 (2003), no. 3, 349-370 (electronic). MR 2030155 (2004k:49004), https://doi.org/10.1137/S1540345902416247
  • [37] Michael Patriksson, A survey on the continuous nonlinear resource allocation problem, European J. Oper. Res. 185 (2008), no. 1, 1-46. MR 2358684 (2008g:91153), https://doi.org/10.1016/j.ejor.2006.12.006
  • [38] D. W. Peaceman and H. H. Rachford Jr., The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl. Math. 3 (1955), 28-41. MR 0071874 (17,196d)
  • [39] M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283-298. MR 0272403 (42 #7284)
  • [40] H. Robbins and D. Siegmund, A convergence theorem for non negative almost supermartingales and some applications, Optimizing methods in statistics (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971) Academic Press, New York, 1971, pp. 233-257. MR 0343355 (49 #8097)
  • [41] R. Tyrrell Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976), no. 5, 877-898. MR 0410483 (53 #14232)
  • [42] Leonid I. Rudin, Stanley Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), no. 1-4, 259-268. MR 3363401
  • [43] Hayden Schaeffer and Stanley Osher, A low patch-rank interpretation of texture, SIAM J. Imaging Sci. 6 (2013), no. 1, 226-262. MR 3032953, https://doi.org/10.1137/110854989
  • [44] Jean-Luc Starck, Michael Elad, and David L. Donoho, Image decomposition via the combination of sparse representations and a variational approach, IEEE Trans. Image Process. 14 (2005), no. 10, 1570-1582. MR 2483314, https://doi.org/10.1109/TIP.2005.852206
  • [45] Hirofumi Uzawa, Market mechanisms and mathematical programming, Econometrica 28 (1960), 872-881. MR 0136447 (24 #B2481)
  • [46] Luminita A. Vese and Stanley J. Osher, Modeling textures with total variation minimization and oscillating patterns in image processing, Special issue in honor of the sixtieth birthday of Stanley Osher, J. Sci. Comput. 19 (2003), no. 1-3, 553-572. MR 2028858 (2004k:49006), https://doi.org/10.1023/A:1025384832106

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
Email: dyh@lsec.cc.ac.cn

Deren Han
Affiliation: School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China
Email: handeren@njnu.edu.cn

Xiaoming Yuan
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong, People’s Republic of China
Email: xmyuan@hkbu.edu.hk

Wenxing Zhang
Affiliation: School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, People’s Republic of China
Email: wxzh1984@126.com

DOI: https://doi.org/10.1090/mcom/3104
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

American Mathematical Society