Primal-Dual Splitting Algorithm for Solving Inclusions with Mixtures of Composite, Lipschitzian, and Parallel-Sum Type Monotone Operators
详细信息 查看全文
- 作者：Patrick L. Combettes (1) plc@math.jussieu.fr
Jean-Christophe Pesquet (2) jean-christophe.pesquet@univ-paris-est.fr - 关键词：Maximal monotone operator – ; Monotone inclusion – ; Nonsmooth convex optimization – ; Parallel sum – ; Set ; valued duality – ; Splitting algorithm
- 刊名：Set-Valued and Variational Analysis
- 出版年：2012
- 出版时间：June 2012
- 年：2012
- 卷：20
- 期：2
- 页码：307-330
- 全文大小：503.5 KB
- 参考文献：1. Acker, F., Prestel, M.A.: Convergence d’un sch茅ma de minimisation altern茅e. Ann. Fac. Sci. Toulouse V. S茅r. Math. 2, 1–9 (1980)
2. Alduncin, G.: Composition duality principles for mixed variational inequalities. Math. Comput. Model. 41, 639–654 (2005)
3. Attouch, H., Brice帽o-Arias, L.M., Combettes, P.L.: A parallel splitting method for coupled monotone inclusions. SIAM J. Control Optim. 48, 3246–3270 (2010)
4. Attouch, H., Redont, P., Soubeyran, A.: A new class of alternating proximal minimization algorithms with costs-to-move. SIAM J. Optim. 18, 1061–1081 (2007)
5. Attouch, H., Th茅ra, M.: A general duality principle for the sum of two operators. J. Convex Anal. 3, 1–24 (1996)
6. Aujol, J.-F., Chambolle, A.: Dual norms and image decomposition models. Int. J. Comput. Vis. 63, 85–104 (2005)
7. Bauschke, H.H., Burke, J.V., Deutsch, F.R., Hundal, H.S., Vanderwerff, J.D.: A new proximal point iteration that converges weakly but not in norm. Proc. Am. Math. Soc. 133, 1829–1835 (2005)
8. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)
9. Bauschke, H.H., Combettes, P.L., Reich, S.: The asymptotic behavior of the composition of two resolvents. Nonlinear Anal. 60, 283–301 (2005)
10. Brice帽o-Arias, L.M., Combettes, P.L.: A monotone + skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. (2011, in press)
11. Brice帽o-Arias, L.M., Combettes, P.L.: Monotone operator methods for Nash equilibria in non-potential games. http://arxiv.org/abs/1106.0144
12. Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numer. Math. 76, 167–188 (1997)
13. Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475–504 (2004)
14. Combettes, P.L., Dũng, D., Vũ, B.C.: Proximity for sums of composite functions. J. Math. Anal. Appl. 380, 680–688 (2011)
15. Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4, 1168–1200 (2005)
16. Eckstein, J., Ferris, M.C.: Smooth methods of multipliers for complementarity problems. Math. Program. 86, 65–90 (1999)
17. Ekeland, I., Temam, R.: Analyse Convexe et Probl猫mes Variationnels. Dunod, Paris, 1974. Convex Analysis and Variational Problems. SIAM, Philadelphia, PA (1999)
18. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
19. Fenchel, W.: Convex Cones, Sets and Functions. Princeton University, Princeton, NJ (1953)
20. Fukushima, M.: The primal Douglas–Rachford splitting algorithm for a class of monotone mappings with applications to the traffic equilibrium problem. Math. Program. 72, 1–15 (1996)
21. Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary Value Problems, pp. 299–331. North-Holland, Amsterdam (1983)
22. Glowinski, R., Le Tallec, P. (eds.): Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989)
23. Goh, C.J., Yang, X.Q.: Duality in Optimization and Variational Inequalities. Taylor & Francis, London (2002)
24. Gol’shteĭn, E.G.: Teoriya Dvoistvennosti v Matematicheskom Programmirovanii i ee Prilozheniya (Duality Theory in Mathematical Programming and Its Applications). Nauka, Moscow (1971)
25. G眉ler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29, 403–419 (1991)
26. Konnov, I.V.: The splitting method with a linear search for direct-dual variational inequalities. Comput. Math. Math. Phys. 43, 494–507 (2003)
27. Lebedev, V.N., Tynjanskĭ, N.T.: Duality theory of concave-convex games. Sov. Math. Dokl. 8, 752–756 (1967)
28. Luque, J.: Convolutions of maximal monotone mappings. Technical report LIDS-P-1597, MIT Libraries, Cambridge, MA. http://mit.dspace.org/handle/1721.1/2953 (1986)
29. McLinden, L.: An extension of Fenchel’s duality theorem to saddle functions and dual minimax problems. Pac. J. Math. 50, 135–158 (1974)
30. Mercier, B.: Topics in finite element solution of elliptic problems. In: Lectures on Mathematics, vol. 63. Tata Institute of Fundamental Research, Bombay (1979)
31. Mercier, B.: In茅quations variationnelles de la m茅canique. In: Publications Math茅matiques d’Orsay, vol. 80.01. Universit茅 de Paris-XI, Orsay, France (1980)
32. Moreau, J.-J.: Th茅or猫mes “inf-sup”. C. R. Acad. Sci. Paris S茅r. A Math. 258, 2720–2722 (1964)
33. Moreau, J.-J.: Fonctionnelles Convexes. S茅minaire Jean Leray sur les 脡quations aux D茅riv茅es Partielles, no. 2, Coll猫ge de France, Paris, 1966–1967. Corrected reprint: Edizioni del Dipartimento di Ingegneria Civile. Universit脿 di Roma Tor Vergata, Rome (2003)
34. Mosco, U.: Dual variational inequalities. J. Math. Anal. Appl. 40, 202–206 (1972)
35. Moudafi, A.: On the stability of the parallel sum of maximal monotone operators. J. Math. Anal. Appl. 199, 478–488 (1996)
36. Passty, G.B.: The parallel sum of nonlinear monotone operators. Nonlinear Anal. 10, 215–227 (1986)
37. Pennanen, T.: Dualization of generalized equations of maximal monotone type. SIAM J. Optim. 10, 809–835 (2000)
38. Robinson, S.M.: Composition duality and maximal monotonicity. Math. Program. 85, 1–13 (1999)
39. Rockafellar, R.T.: Minimax theorems and conjugate saddle-functions. Math. Scand. 14, 151–173 (1964)
40. Rockafellar, R.T.: Duality and stability in extremum problems involving convex functions. Pac. J. Math. 21, 167–187 (1967)
41. Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia, PA (1974)
42. Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
43. Seeger, A.: Direct and inverse addition in convex analysis and applications. J. Math. Anal. Appl. 148, 317–349 (1990)
44. Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29, 119–138 (1991)
45. Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38, 431–446 (2000)
46. Zălinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, River Edge, NJ (2002) - 作者单位：1. Laboratoire Jacques-Louis Lions, UMR CNRS 7598, UPMC Universit茅 Paris 06, 75005 Paris, France2. Laboratoire d鈥橧nformatique Gaspard Monge, UMR CNRS 8049, Universit茅 Paris-Est, 77454 Marne la Vall茅e Cedex 2, France
- 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Analysis
Geometry - 出版者：Springer Netherlands
- ISSN：1877-0541
文摘
We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.