Abstract

We extend the general decomposition scheme of M. V. Solodov [Optimization Methods and Software 19 (2004) 557–575], which is based on the hybrid inexact proximal point method of M. V. Solodov and B. F. Svaiter [Numerical Functional Analysis and Optimization 22 (2001) 1013–1035], to allow the use of variable metric in subproblems, along the lines described in a previous paper of the authors [SIAM Journal on Optimization 19 (2008) 240–260]. We show that the new general scheme includes as special cases the splitting method for composite mappings [see T. Pennanen, Numerical Functional Analysis and Optimization 23 (2002) 875–890] and the proximal alternating directions method [see J. Eckstein, Optimization Methods and Software 4 (1994) 75–83, and B. He, L. Z. Liao, D. Han and H. Yang, Mathematical Programming 92 (2002) 103–118] (in addition to the decomposition methods of X. Chen and M. Teboulle [Mathematical Programming 64 (1994) 81–101] and P. Tseng [SIAM Journal on Optimization 7 (1997) 951–965] that were already covered in the above-mentioned article by M. V. Solodov [Optimization Methods and Software 19 (2004) 557–575]). Apart from giving a unified insight into the decomposition methods in question and openning the possibility of using variable metric, which is a computationally important issue, this development also provides linear rate of convergence results not previously available for splitting of composite mappings and for the proximal alternating directions methods.

Author information

Contact details are reproduced from the original publication and may be historical.

Pablo A. Lotito

Dep. de Matemática, FCEIA, Universidad Nacional Rosario, Avenida Pellegrini 250, 2000 Rosario, Argentina
and: CONICET, Argentina
and: PLADEMA, UNICEN, Argentina

plotito@exa.unicen.edu.ar

Lisandro A. Parente

CONICET, Argentina
and: Dep. de Matemática, FCEIA, Universidad Nacional Rosario, Avenida Pellegrini 250, 2000 Rosario, Argentina

lparente@fceia.unr.edu.ar

Mikhail Solodov

Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil

solodov@impa.br

Keywords

  • Proximal point methods
  • variable metric
  • maximal monotone operator
  • variational inclusion
  • splitting
  • decomposition

References

  1. H. H. Bauschke: Projection algorithms: results and open problems, in: Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, D. Butnariu, Y. Censor, S. Reich (eds.), Studies in Computational Mathematics 8, Elsevier, Amsterdam (2001) 11–22.https://doi.org/10.1016/S1570-579X(01)80003-3Google Scholar
  2. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: A family of variable metric proximal methods, Math. Program., Ser. A 68 (1995) 15–47.https://doi.org/10.1007/BF01585756Google Scholar
  3. R. S. Burachik, A. N. Iusem, B. F. Svaiter: Enlargement of monotone operators with applications to variational inequalities, Set-Valued Anal. 5 (1997) 159–180.https://doi.org/10.1023/A:1008615624787Google Scholar
  4. R. S. Burachik, C. A. Sagastizábal, B. F. Svaiter: ε-Enlargements of maximal monotone operators: Theory and applications, in: Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi (eds.), Kluwer, Boston (1999) 25–44.https://doi.org/10.1007/978-1-4757-6388-1_2Google Scholar
  5. R. S. Burachik, C. A. Sagastizábal, S. Scheimberg: An inexact method of partial inverses and a parallel bundle method, Optim. Methods Softw. 21 (2006) 385–400.https://doi.org/10.1080/10556780500094887Google Scholar
  6. J. V. Burke, M. Qian: A variable metric proximal point algorithm for monotone operators, SIAM J. Control Optimization 37 (1997) 353–375.https://doi.org/10.1137/S0363012992235547Google Scholar
  7. J. V. Burke, M. Qian: On the local super-linear convergence of a matrix secant implementation of the variable metric proximal point algorithm for monotone operators, in: Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi (eds.), Kluwer, Boston (1999) 317–334.https://doi.org/10.1007/978-1-4757-6388-1_16Google Scholar
  8. J. V. Burke, M. Qian: On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating, Math. Program., Ser. A 88 (2000) 157–181.https://doi.org/10.1007/PL00011373Google Scholar
  9. X. Chen, M. Fukushima: Proximal quasi-Newton methods for nondifferentiable convex optimization, Math. Program., Ser. A 85 (1999) 313–334.https://doi.org/10.1007/s101070050059Google Scholar
  10. X. Chen, M. Teboulle: A proximal-based decomposition method for convex minimization problems, Math. Program., Ser. A 64 (1994) 81–101.https://doi.org/10.1007/BF01582566Google Scholar
  11. X. Chen, R. T. Rockafellar: Convergence rates in forward-backward splitting, SIAM J. Optim. 7 (1997) 421–444.https://doi.org/10.1137/S1052623495290179Google Scholar
  12. J. Eckstein, D. P. Bertsekas: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., Ser. A 55 (1992) 293–318.https://doi.org/10.1007/BF01581204Google Scholar
  13. J. Eckstein: Some saddle-function splitting methods for convex programming, Optim. Methods Softw. 4 (1994) 75–83.https://doi.org/10.1080/10556789408805578Google Scholar
  14. J. Eckstein, M. C. Ferris: Operator splitting methods for monotone affine variational inequalities, with a parallel application to optimal control, INFORMS J. Comput. 10 (1998) 218–235.https://doi.org/10.1287/ijoc.10.2.218Google Scholar
  15. D. Gabay: Applications of the method of multipliers to variational inequalities, in: Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, M. Fortin, R. Glowinski (eds.), North-Holland, Amsterdam (1983) 229–331.Google Scholar
  16. Y. García, M. Lassonde, J. P. Revalski: Extended sums and extended compositions of monotone operators, J. Convex Analysis 13 (2006) 721–738.https://doi.org/10.68381/jca13054Google Scholar
  17. B. He, L. Z. Liao, D. Han, H. Yang: A new inexact alternating directions method for monotone variational inequalities, Math. Program., Ser. A 92 (2002) 103–118.https://doi.org/10.1007/s101070100280Google Scholar
  18. B. Lemaire: The proximal algorithm, in: New Methods of Optimization and Their Industrial Uses, J. P. Penot (ed.), International Series of Numerical Mathematics 87, Birkhäuser, Basel (1989) 73–87.Google Scholar
  19. C. Lemaréchal, C. Sagastizábal: Variable metric bundle methods: from conceptual to implementable forms, Math. Program., Ser. B 76 (1997) 393–410.https://doi.org/10.1007/BF02614390Google Scholar
  20. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  21. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  22. A. Ouorou: Epsilon-proximal decomposition method, Math. Program., Ser. A 99 (2004) 89–108.https://doi.org/10.1007/s10107-003-0371-0Google Scholar
  23. L. A. Parente, P. A. Lotito, M. V. Solodov: A class of inexact variable metric proximal point algorithms, SIAM J. Optim. 19 (2008) 240–260.https://doi.org/10.1137/070688146Google Scholar
  24. T. Pennanen: Dualization of generalized equations of maximal monotone type, SIAM J. Optim. 10 (2000) 809–835.https://doi.org/10.1137/S1052623498340448Google Scholar
  25. T. Pennanen: A splitting method for composite mappings, Numer. Funct. Anal. Optimization 23 (2002) 875–890.https://doi.org/10.1081/NFA-120016274Google Scholar
  26. L. Qi, X. Chen: A preconditioning proximal Newton’s method for nondifferentiable convex optimization, Math. Program., Ser. B 76 (1995) 411–430.https://doi.org/10.1007/BF02614391Google Scholar
  27. S. M. Robinson: Composition duality and maximal monotonicity, Math. Program., Ser. A 85 (1999) 1–13.https://doi.org/10.1007/s101070050043Google Scholar
  28. R. T. Rockafellar: On the maximality of sums of nonlinear monotone operators, Trans. Amer. Math. Soc. 149 (1970) 75–88.https://doi.org/10.1090/S0002-9947-1970-0282272-5Google Scholar
  29. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  30. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  31. R. T. Rockafellar, J.-B. Wets: Variational Analysis, Springer, New York (1997).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  32. 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.https://doi.org/10.1080/1055678042000218957Google Scholar
  33. M. V. Solodov, B. F. Svaiter: A globally convergent inexact Newton method for systems of monotone equations, in: Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi (eds.), Kluwer, Boston (1999) 355–369.https://doi.org/10.1007/978-1-4757-6388-1_18Google Scholar
  34. M. V. Solodov, B. F. Svaiter: A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Anal. 7 (1999) 323–345.https://doi.org/10.1023/A:1008777829180Google Scholar
  35. M. V. Solodov, B. F. Svaiter: A hybrid projection-proximal point algorithm, J. Convex Analysis 6 (1999) 59–70.https://doi.org/10.68381/jca06005Google Scholar
  36. M. V. Solodov, B. F. Svaiter: Error bounds for proximal point subproblems and associated inexact proximal point algorithms, Math. Program., Ser. B 88 (2000) 371–389.https://doi.org/10.1007/s101070050022Google Scholar
  37. M. V. Solodov, B. F. Svaiter: A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem, SIAM J. Optim. 10 (2000) 605–625.https://doi.org/10.1137/S1052623498337546Google Scholar
  38. M. V. Solodov, B. F. Svaiter: A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optimization 22 (2001) 1013–1035.https://doi.org/10.1081/NFA-100108320Google Scholar
  39. M. V. Solodov, B. F. Svaiter: A new proximal-based globalization strategy for the Josephy-Newton method for variational inequalities, Optim. Methods Softw. 17 (2002) 965–983.https://doi.org/10.1080/1055678021000056563Google Scholar
  40. J. E. Spingarn: Applications of the method of partial inverses to convex programming, Math. Program. 32 (1985) 199–223.https://doi.org/10.1007/BF01586091Google Scholar
  41. P. Tseng: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optimization 29 (1991) 119–138.https://doi.org/10.1137/0329006Google Scholar
  42. P. Tseng: Alternating projection-proximal methods for convex programming and variational inequalities, SIAM J. Optim. 7 (1997) 951–965.https://doi.org/10.1137/S1052623495279797Google Scholar
  43. P. Tseng: A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optimization 38 (2000) 431–446.https://doi.org/10.1137/S0363012998338806Google Scholar

Suggested citation

P. A. Lotito, L. A. Parente, M. Solodov. “A Class of Variable Metric Decomposition Methods for Monotone Variational Inclusions.” Journal of Convex Analysis 16 (2009), No. 3&4, 857–880. https://doi.org/10.68381/jca16052

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2009. Rights now held by Banach Press LLC.