A sequential updating scheme of the Lagrange multiplier for separable convex programming
HTML articles powered by AMS MathViewer
- by Yu-Hong Dai, Deren Han, Xiaoming Yuan and Wenxing Zhang PDF
- Math. Comp. 86 (2017), 315-343 Request permission
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
- 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.
- Heinz H. Bauschke and Patrick L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2011. With a foreword by Hédy Attouch. MR 2798533, DOI 10.1007/978-1-4419-9467-7
- 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
- D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996.
- 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.
- 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, DOI 10.1007/s10107-014-0826-5
- 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, DOI 10.1007/978-1-4419-9569-8_{1}0
- 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, DOI 10.1137/130940402
- 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 84194, DOI 10.1090/S0002-9947-1956-0084194-4
- 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
- Francisco Facchinei and Jong-Shi Pang, Finite-dimensional variational inequalities and complementarity problems. Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003. MR 1955648
- 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.
- 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.
- Roland Glowinski, Numerical methods for nonlinear variational problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. MR 737005, DOI 10.1007/978-3-662-12613-4
- 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, DOI 10.1007/978-94-017-9054-3_{4}
- 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, DOI 10.1137/1.9781611970838
- 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
- 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 English summary). MR 388811
- 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, DOI 10.1137/080725891
- 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, DOI 10.1007/s10957-012-0003-z
- Per Christian Hansen, James G. Nagy, and Dianne P. O’Leary, Deblurring images, Fundamentals of Algorithms, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Matrices, spectra, and filtering. MR 2271138, DOI 10.1137/1.9780898718874
- 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, DOI 10.1007/s101070100280
- 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).
- 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, DOI 10.1137/13090849X
- 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, DOI 10.1137/110822347
- 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, DOI 10.1016/S0167-6377(98)00044-3
- 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, DOI 10.1137/110836936
- Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
- M. Hong and Z. Q. Luo, On the linear convergence of alternating direction method of multipliers, Math. Program., to appear.
- 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, DOI 10.1137/0716071
- 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, DOI 10.1287/moor.18.4.846
- S. Q. Ma, Alternating proximal gradient method for convex minimization, preprint (2012).
- B. Martinet, Régularisation d’inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (1970), no. Sér. R-3, 154–158 (French). MR 0298899
- Yves Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, 2001. The fifteenth Dean Jacqueline B. Lewis memorial lectures. MR 1852741, DOI 10.1090/ulect/022
- Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273–299 (French). MR 201952
- 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. MR 2030155, DOI 10.1137/S1540345902416247
- Michael Patriksson, A survey on the continuous nonlinear resource allocation problem, European J. Oper. Res. 185 (2008), no. 1, 1–46. MR 2358684, DOI 10.1016/j.ejor.2006.12.006
- 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 71874
- 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
- 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
- R. Tyrrell Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), no. 5, 877–898. MR 410483, DOI 10.1137/0314056
- Leonid I. Rudin, Stanley Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), no. 1-4, 259–268. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). MR 3363401, DOI 10.1016/0167-2789(92)90242-F
- Hayden Schaeffer and Stanley Osher, A low patch-rank interpretation of texture, SIAM J. Imaging Sci. 6 (2013), no. 1, 226–262. MR 3032953, DOI 10.1137/110854989
- 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, DOI 10.1109/TIP.2005.852206
- Hirofumi Uzawa, Market mechanisms and mathematical programming, Econometrica 28 (1960), 872–881. MR 136447, DOI 10.2307/1907569
- Luminita A. Vese and Stanley J. Osher, Modeling textures with total variation minimization and oscillating patterns in image processing, J. Sci. Comput. 19 (2003), no. 1-3, 553–572. Special issue in honor of the sixtieth birthday of Stanley Osher. MR 2028858, DOI 10.1023/A:1025384832106
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
- MR Author ID: 620453
- 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
- MR Author ID: 664477
- Email: handeren@njnu.edu.cn
- Xiaoming Yuan
- Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon, Hong Kong, People’s Republic of China
- MR Author ID: 729439
- 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
- 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 - © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 315-343
- MSC (2010): Primary 90C25, 65K10, 94A08, 68W10
- DOI: https://doi.org/10.1090/mcom/3104
- MathSciNet review: 3557801