Many structured convex minimization problems can be modeled by the search of a zero of the sum of two monotone operators. Operator splitting methods have been designed to decompose and regularize at the same time these kind of models. We review here these models and the classical splitting methods. We focus on the numerical sensitivity of these algorithms with respect to the scaling parameters that drive the regularizing terms, in order to accelerate convergence rates for different classes of models.
Mots-clés : Operator splitting, Augmented Lagrangian, Decomposition methods
@article{RO_2017__51_1_17_0, author = {Lenoir, Arnaud and Mahey, Philippe}, title = {A survey on operator splitting and decomposition of convex programs}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {17--41}, publisher = {EDP-Sciences}, volume = {51}, number = {1}, year = {2017}, doi = {10.1051/ro/2015065}, zbl = {1360.65169}, mrnumber = {3589262}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2015065/} }
TY - JOUR AU - Lenoir, Arnaud AU - Mahey, Philippe TI - A survey on operator splitting and decomposition of convex programs JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 17 EP - 41 VL - 51 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2015065/ DO - 10.1051/ro/2015065 LA - en ID - RO_2017__51_1_17_0 ER -
%0 Journal Article %A Lenoir, Arnaud %A Mahey, Philippe %T A survey on operator splitting and decomposition of convex programs %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 17-41 %V 51 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2015065/ %R 10.1051/ro/2015065 %G en %F RO_2017__51_1_17_0
Lenoir, Arnaud; Mahey, Philippe. A survey on operator splitting and decomposition of convex programs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 17-41. doi : 10.1051/ro/2015065. http://www.numdam.org/articles/10.1051/ro/2015065/
A primal-dual method of partial inverses for composite inclusions. Optim. Lett. 8 (2014) 2271–2284. | DOI | MR | Zbl
, , and ,Augmented lagrangian and proximal alternating direction method of multipliers in hilbert spaces. applications to games, pde’s and control. Pacific J. Optim. 5 (2008) 17–37. | MR | Zbl
and ,Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting and regularized gauss-seidel methods. Math. Program. 137 (2013) 91–129. | DOI | MR | Zbl
, and ,On the asymptotic behavior of nonexpansive mappings and semi-groups. Houston J. Math. 4 (1978) 1–9. | MR | Zbl
, and ,H.H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Verlag (2011). | MR | Zbl
A. Bensoussan, J.L. Lions and R. Temam, Sur les méthodes de décomposition, décentralisation et de coordination et applications. Technical report, Cahiers de l’INRIA (1972). | MR | Zbl
Convexification procedures and decomposition methods for nonconvex optimization problems. J. Optim. Theory Appl. 29 (1979) 169–197. | DOI | MR | Zbl
,D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englewood Cliffs, New Jersey (1989). | Zbl
A primal-dual splitting for finding zeros of sums of maximally monotone operators. SIAM J. Optim. 23 (2013) 2011–2036. | DOI | MR | Zbl
, and ,S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning with the alternating direction method of multipliers. In Vol. 3 of Found. Trends Mach. Learn., edited by M. Jordan (2011) 1–122. | Zbl
H. Brezis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. Vol. 5 of Lect. Notes. North-Holland (1973). | MR | Zbl
Forward douglas-rachford splitting and forward partial inverse method for solving monotone inclusions. Optimization 64 (2015) 1239–1261. | DOI | MR | Zbl
,A monotone+skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21 (2011) 1230–1250. | DOI | MR | Zbl
and ,A first-order primal-dual algorithm for convex programs with applications to imaging. J. Math. Imaging Vision 40 (2011) 1–26. | DOI | MR | Zbl
and ,The direct extension of admm for multi block convex minimization problems is not necessarily convergent. Math. Program. 155 (2014) 1–23. | MR | Zbl
, , and ,Convergence rates in forward-backward splitting. SIAM J. Optim. 7 (1997) 421–444. | DOI | MR | Zbl
and ,A proximal-based decomposition method for convex minimization problems. Math. Program. 64 (1994) 81–101. | DOI | MR | Zbl
and ,Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J. Optim. Theory Appl. 162 (2014) 107–132. | DOI | Zbl
, and ,Auxiliary problem principle and decomposition of optimization problems. J. Opt. Theory Appl. 32 (1980) 277–305. | DOI | MR | Zbl
,G. Cohen and D.L. Zhu, Decomposition coordination methods in large-scale optimization problems. the nondifferentiable case and the use of augmented lagrangians. In Vol. 1 of Advances in Large-Scale Systems, edited by J.B. Cruz Junior. JAI Press Inc. (1983). | MR
Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53 (2004) 475–504. | DOI | MR | Zbl
,P.L. Combettes and J.C. Pesquet, Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, edited by P.L. Combettes V. Elser D.R. Luke H. Wolkowicz H.H. Bauschke and R.S. Burachik, Springer Verlag (2011) 185–212. | MR | Zbl
Stochastic quasi-fejér block-coordinate fixed-point iterations with random sweeping. SIAM J. Optim. 25 (2015) 1221–1248. | DOI | MR | Zbl
and ,Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4 (2005) 1168–1200. | DOI | MR | Zbl
and ,D. Davis, Convergence rate analysis of forward-douglas-rachford splitting scheme. Technical Report 15-xx, UCLA CAM. Preprint (2015). | arXiv
D. Davis and W. Yin, Convergence rate analysis of several splitting schemes. Technical Report 14-51, UCLA CAM. Preprint (2014). | arXiv
A general formulation of alternating direction methods. Numer. Math. 6 (1964) 428–453. | DOI | MR | Zbl
and ,On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. Amer. Math. Soc. 82 (1956) 421–439. | DOI | MR | Zbl
and ,Separable augmented lagrangian algorithm with multidimensional scaling for monotropic programming. J. Optim. Theory Appl. 127 (2005) 329–345. | DOI | MR | Zbl
, and ,J. Eckstein, Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1989).
Some saddle-point splitting method for convex programming. Optimization Methods Softw. 4 (1994) 75–83. | DOI
,J. Eckstein, Augmented lagrangian and alternating direction method of multipliers: A tutorial and some illustrative computational examples. Technical report, RUTCOR Research Rept - RRR32-2012, December (2012).
On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55 (1992) 293–318. | DOI | MR | Zbl
and ,J. Eckstein and M. Fukushima, Some reformulations and applications of the alternating direction method of multipliers. In Large Scale Optimization: State of the Art. Springer (1994) 119–138. | Zbl
General projective splitting methods for sums of maximal monotone operators. SIAM J. Control Optim. 48 (2009) 787–811. | DOI | MR | Zbl
and ,Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 3 (2013) 946–977. | DOI | MR | Zbl
, , and ,Application of the alternating direction method of multipliers to separable convex programming. Comput. Optim. Appl. 1 (1992) 93–112. | DOI | MR | Zbl
,D. Gabay, Applications of the method of multipliers to variational inequalities. In Augmented Lagrangian Methods: Application to numerical solutions of boundary-value problems, edited by M. Fortin and R. Glowinski. Vol. 15 of Stud. Math. Appl. North-Holland (1983) 299–331. | MR
A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Comput. Math. Appl. 2 (1976) 17–40. | DOI | Zbl
and ,R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM Philadelphia (1989). | MR | Zbl
Sur l’approximation par éléments finis d’ordre 1 et la résolution par pénalisation-dualité d’une classe de problèmes de dirichlet. RAIRO: Anal. Numer. 2 (1975) 41–76. | Numdam | MR | Zbl
and ,Fast multiple splitting algorithms for convex optimization. SIAM J. Optim. 22 (2012) 533–556. | DOI | MR | Zbl
and ,D. Goldfarb, S. Ma and K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. (2009).
Convex programming in hilbert space. Bull. Amer. Math. Society 70 (1964) 709–710. | DOI | MR | Zbl
,A new decomposition method in nonconvex programming via a separable augmented lagrangian. Lect. Notes Econ. Math. Syst. 452 (1997) 90–104. | DOI | MR | Zbl
, and ,A parallel algorithm for a class of convex programs. SIAM J. Control Optim. 26 (1988) 345–355. | DOI | MR | Zbl
and ,Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106 (2000) 349–368. | MR | Zbl
, and ,M. Hong and Z.Q. Luo, On the linear convergence of the alternating method of multipliers. Preprint (2013). | arXiv
Applications and numerical convergence of the partial inverse method. Lect. Notes Math. 1405 (1989) 39–54. | DOI | MR | Zbl
, and ,Proximal decomposition via alternating linearization. SIAM J. Optim. 9 (1999) 668–689. | DOI | MR | Zbl
, and ,N. Komodakis and J.C. Pesquet, Playing with duality: an overview of recent primal-dual approaches for solving large-scale optimization problems. SIAM J. Optim. (2014).
A variable-penalty alternating directions method for convex optimization. Math. Program. 83 (1998) 29–53. | DOI | MR | Zbl
and ,L.S. Lasdon, Optimization for Large Systems. Mac Millan (1970). | MR
On fixed points of nonexpansive piecewise isometric mappings. Proc. London Math. Soc. 55 (1987) 605–624. | DOI | MR | Zbl
and ,A. Lenoir, Modèles et algorithmes pour la planification de production à moyen terme en environnement incertain. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand (2008).
Accelerating a class of splitting algorithms by iterative foldings. Acta Math. Vietnam. 39 (2009) 49–65. | MR | Zbl
and ,J. Lieutaud, Approximation d’opérateurs par les méthodes de décomposition. Ph.D. thesis, Université de Paris (1969).
Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16 (1979) 964–979. | DOI | MR | Zbl
and ,Proximal decomposition on the graph of a maximal monotone operator. SIAM J. Optim. 5 (1995) 454–466. | DOI | MR | Zbl
, and ,A new proximal decomposition algorithm for routing in telecommunication networks. Networks 31 (1998) 227–238. | DOI | Zbl
, , and ,P. Mahey, J.P. Dussault, A. Benchakroun and A. Hamdi, Adaptive scaling and convergence rates of a separable augmented lagrangian algorithm. In Optimization, edited by V.H. Nguyen, J.J. Strodiot and P. Tossingsvolume, Vol. 481 of Lect. Notes Econ. Math. Syst. Springer (2000) 278–287. | MR | Zbl
B. Martinet, Régularistion d’inéquations variationnelles par approximations successives. Revue Française d’Informatique et de Recherche Opérationnelle (1970) 154–159. | Numdam | MR | Zbl
B. Mercier, Lectures on Topics in Finite-Element Solution of Elliptic Problems. Vol. 63. Lectures on Mathematics and Physics. Springer (1979). | MR | Zbl
Monotone operators in hilbert spaces. Duke Math. J. 29 (1962) 341–346. | DOI | MR | Zbl
,Proximité et dualité dans un espace hilbertien. Bull. de la Société Mathématique Française 93 (1965) 273–299. | DOI | Numdam | MR | Zbl
,A perturbed parallel decomposition method for a class of nonsmooth convex minimization problems. SIAM J. Control Optim. 29 (1991) 829–847. | DOI | MR | Zbl
, and ,A method for unconstrained convex minimization problem with the rate of convergence . Dokl. Akad. Nauk SSSR 269 (1983) 543–547. | MR | Zbl
,Ergodic convergence to a zero of the sum of monotone operators in hilbert spaces. J. Math. Anal. Appl. 72 (1979) 383–390. | DOI | MR | Zbl
,The numerical solution of parabolic elliptic differential equations. J. Soc. Indust. Appl. Math. 3 (1955) 28–41. | DOI | MR | Zbl
and ,Decomposition through formalization on a product space. Math. Program. 28 (1984) 96–115. | DOI | MR | Zbl
,Augmented lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1 (1976) 97–116. | DOI | MR | Zbl
,Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976) 877–898. | DOI | MR | Zbl
,Proto-differentiability of set-valued mappings and its application in optimization. Ann. Inst. Henri Poincaré S6 (1989) 449–482. | DOI | Numdam | MR | Zbl
,Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16 (1991) 119–147. | DOI | MR | Zbl
and ,R. Shefi and M. Teboulle, Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization. SIAM J. Optim. (2014). | MR | Zbl
A class of decomposition methods for convex optimization and monotone variational inclusions via the hybrid inexact proximal point framework. Optim. Methods Softw. 19 (2004) 557–575. | DOI | MR | Zbl
,Partial inverse of a monotone operator. Appl. Math. Optim. 10 (1983) 247–265. | DOI | MR | Zbl
,Applications of the method of partial inverses to convex programming:decomposition. Math. Program. 32 (1985) 199–223. | DOI | MR | Zbl
,The use of Hestenes method of multipliers to resolve dual gaps in engineering system optimization. J. Optim. Theory Appl. 15 (1975) 285–309. | DOI | MR | Zbl
and ,Sur la stabilité et la convergence de la méthode des pas fractionnaires. Ann. Mat. Pura Appl. 79 (1968) 191–379. | DOI | MR | Zbl
,Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29 (1991) 119–138. | DOI | MR | Zbl
,A modified forward-backward plotting method for maximal mono tone mappings. SIAM J. Control Optim. 38 (2000) 431–446. | DOI | MR | Zbl
,R.S. Varga, Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ (1966). | MR
Proximal alternating directions method for structured variational inequalities. J. Optim. Theory Appl. 134 (2007) 107–117. | DOI | MR | Zbl
,Cité par Sources :