A survey on operator splitting and decomposition of convex programs

Lenoir, Arnaud; Mahey, Philippe

RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 1, pp. 17-41.

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.

M.A. Alghamdi, A. Alotaibi, P.L. Combettes and N. Shahzad, A primal-dual method of partial inverses for composite inclusions. Optim. Lett. 8 (2014) 2271–2284. | DOI | MR | Zbl

H. Attouch and M. Soueycatt, 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

H. Attouch, J. Bolte and B.F. Svaiter, 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

J.B. Baillon, R.E. Bruck and S. Reich, On the asymptotic behavior of nonexpansive mappings and semi-groups. Houston J. Math. 4 (1978) 1–9. | MR | Zbl

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

D.P. Bertsekas, 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

R.I. Bot, E.R. Csetnek and A. Heinrich, A primal-dual splitting for finding zeros of sums of maximally monotone operators. SIAM J. Optim. 23 (2013) 2011–2036. | DOI | MR | Zbl

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

L.M. Briceno-Arias, Forward douglas-rachford splitting and forward partial inverse method for solving monotone inclusions. Optimization 64 (2015) 1239–1261. | DOI | MR | Zbl

L.M. Briceno-Arias and P.L. Combettes, A monotone+skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21 (2011) 1230–1250. | DOI | MR | Zbl

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex programs with applications to imaging. J. Math. Imaging Vision 40 (2011) 1–26. | DOI | MR | Zbl

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 (2014) 1–23. | MR | Zbl

G.H.G Chen and R.T. Rockafellar, Convergence rates in forward-backward splitting. SIAM J. Optim. 7 (1997) 421–444. | DOI | MR | Zbl

G.H.G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems. Math. Program. 64 (1994) 81–101. | DOI | MR | Zbl

E. Chouzenoux, J.C. Pesquet and A. Repetti, 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

G. Cohen, 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

P.L. Combettes, 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

P.L. Combettes and J.C. Pesquet, Stochastic quasi-fejér block-coordinate fixed-point iterations with random sweeping. SIAM J. Optim. 25 (2015) 1221–1248. | DOI | MR | Zbl

P.L. Combettes and V.R. Wajs, Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4 (2005) 1168–1200. | DOI | MR | Zbl

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

J. Douglas and J.E. Gunn, A general formulation of alternating direction methods. Numer. Math. 6 (1964) 428–453. | DOI | MR | Zbl

J. Douglas and H.H. Rachford, 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

J.P. Dussault, O.M. Gueye and P. Mahey, Separable augmented lagrangian algorithm with multidimensional scaling for monotropic programming. J. Optim. Theory Appl. 127 (2005) 329–345. | DOI | MR | Zbl

J. Eckstein, Splitting methods for monotone operators with applications to parallel optimization. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1989).

J. Eckstein, 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).

J. Eckstein and D.P. Bertsekas, On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55 (1992) 293–318. | DOI | MR | Zbl

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

J. Eckstein and B.F. Svaiter, General projective splitting methods for sums of maximal monotone operators. SIAM J. Control Optim. 48 (2009) 787–811. | DOI | MR | Zbl

M. Fazel, T.K. Pong, D.F. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 3 (2013) 946–977. | DOI | MR | Zbl

M. Fukushima, 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

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. | DOI | Zbl

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM Philadelphia (1989). | MR | Zbl

R. Glowinski and A. Marocco, 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

D. Goldfarb and S. Ma, Fast multiple splitting algorithms for convex optimization. SIAM J. Optim. 22 (2012) 533–556. | DOI | MR | Zbl

D. Goldfarb, S. Ma and K. Scheinberg, Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. (2009).

A.A. Goldstein, Convex programming in hilbert space. Bull. Amer. Math. Society 70 (1964) 709–710. | DOI | MR | Zbl

A. Hamdi, P. Mahey and J.P. Dussault, A new decomposition method in nonconvex programming via a separable augmented lagrangian. Lect. Notes Econ. Math. Syst. 452 (1997) 90–104. | DOI | MR | Zbl

S.P. Han and G. Lou, A parallel algorithm for a class of convex programs. SIAM J. Control Optim. 26 (1988) 345–355. | DOI | MR | Zbl

B.S. He, H. Yang and S.L. Wang, Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106 (2000) 349–368. | MR | Zbl

M. Hong and Z.Q. Luo, On the linear convergence of the alternating method of multipliers. Preprint (2013). | arXiv

H. Idrissi, O. Lefebvre and C. Michelot, Applications and numerical convergence of the partial inverse method. Lect. Notes Math. 1405 (1989) 39–54. | DOI | MR | Zbl

K.C. Kiwiel, C.H. Rosa and A. Ruszczynski, Proximal decomposition via alternating linearization. SIAM J. Optim. 9 (1999) 668–689. | DOI | MR | Zbl

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

S. Kontogiorgis and R.R. Meyer, A variable-penalty alternating directions method for convex optimization. Math. Program. 83 (1998) 29–53. | DOI | MR | Zbl

L.S. Lasdon, Optimization for Large Systems. Mac Millan (1970). | MR

J. Lawrence and J.E. Spingarn, On fixed points of nonexpansive piecewise isometric mappings. Proc. London Math. Soc. 55 (1987) 605–624. | DOI | MR | Zbl

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

A. Lenoir and P. Mahey, Accelerating a class of splitting algorithms by iterative foldings. Acta Math. Vietnam. 39 (2009) 49–65. | MR | Zbl

J. Lieutaud, Approximation d’opérateurs par les méthodes de décomposition. Ph.D. thesis, Université de Paris (1969).

P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16 (1979) 964–979. | DOI | MR | Zbl

P. Mahey, S. Oualibouch and D.T. Pham, Proximal decomposition on the graph of a maximal monotone operator. SIAM J. Optim. 5 (1995) 454–466. | DOI | MR | Zbl

P. Mahey, A. Ouorou, L. Leblanc and J. Chifflet, A new proximal decomposition algorithm for routing in telecommunication networks. Networks 31 (1998) 227–238. | DOI | Zbl

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

G.J. Minty, Monotone operators in hilbert spaces. Duke Math. J. 29 (1962) 341–346. | DOI | MR | Zbl

J.-J. Moreau, Proximité et dualité dans un espace hilbertien. Bull. de la Société Mathématique Française 93 (1965) 273–299. | DOI | Numdam | MR | Zbl

K. Mouallif, V.H. Nguyen and J.-J. Strodiot, A perturbed parallel decomposition method for a class of nonsmooth convex minimization problems. SIAM J. Control Optim. 29 (1991) 829–847. | DOI | MR | Zbl

Y. Nesterov, A method for unconstrained convex minimization problem with the rate of convergence $o(1/k^2)$. Dokl. Akad. Nauk SSSR 269 (1983) 543–547. | MR | Zbl

G.B. Passty, 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

D.H. Peaceman and H.H. Rachford, The numerical solution of parabolic elliptic differential equations. J. Soc. Indust. Appl. Math. 3 (1955) 28–41. | DOI | MR | Zbl

G. Pierra, Decomposition through formalization on a product space. Math. Program. 28 (1984) 96–115. | DOI | MR | Zbl

R.T. Rockafellar, Augmented lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1 (1976) 97–116. | DOI | MR | Zbl

R.T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976) 877–898. | DOI | MR | Zbl

R.T. Rockafellar, Proto-differentiability of set-valued mappings and its application in optimization. Ann. Inst. Henri Poincaré S6 (1989) 449–482. | DOI | Numdam | MR | Zbl

R.T. Rockafellar and R.J.-B Wets, Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16 (1991) 119–147. | DOI | MR | Zbl

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

M.V. Solodov, 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

J.E. Spingarn, Partial inverse of a monotone operator. Appl. Math. Optim. 10 (1983) 247–265. | DOI | MR | Zbl

J.E. Spingarn, Applications of the method of partial inverses to convex programming:decomposition. Math. Program. 32 (1985) 199–223. | DOI | MR | Zbl

G. Stephanopoulos and A.W. Westerberg, 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

R. Temam, Sur la stabilité et la convergence de la méthode des pas fractionnaires. Ann. Mat. Pura Appl. 79 (1968) 191–379. | DOI | MR | Zbl

P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29 (1991) 119–138. | DOI | MR | Zbl

P. Tseng, 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

M.H. Xu, Proximal alternating directions method for structured variational inequalities. J. Optim. Theory Appl. 134 (2007) 107–117. | DOI | MR | Zbl