Abstract

The Bregman-function-based Proximal Point Algorithm (BPPA) for solving variational inequalities is considered. In this framework the customary assumption of the cutting plane property (CPP) of the related operator is investigated. Since this property cannot be expected in saddle-point-problems, it should be considered as rather restrictive. This paper contributes to the situation when the CPP fails to hold. For this situation, interior proximal(-like) methods have only been constructed for polyhedral sets up to now. Under very mild assumptions (not implying the CPP) we show that whenever the sequence of iterates (generated by the BPPA) is convergent, its limit can only be a solution of the given problem. Further, using a (known) slight modification of Bregman functions, we show – still without using the CPP – that the sequence generated by the BPPA is convergent to a solution when the feasible set has some special nonlinear structure like a ball.

Author information

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

Keywords

  • Pseudomonotone operators
  • variational inequalities
  • Bregman distances
  • Proximal Point Algorithm
  • cutting plane property
  • nonconvex optimization

Mathematics Subject Classification

47J20, 65J20, 65K10, 90C26, 90C30

References

  1. A. Auslender, M. Teboulle, S. Ben-Tiba: A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl. 12 (1999) 31–40.https://doi.org/10.1007/978-1-4615-5197-3_3Google Scholar
  2. H. Bauschke, J. Borwein: Legendre functions and the method of random Bregman projections, J. Convex Analysis 4 (1997) 27–67.https://doi.org/10.68381/jca04002Google Scholar
  3. E. Blum, W. Oettli: From optimization and variational inequalities to equilibrium problems, Math. Stud. 63 (1994) 123–145.Google Scholar
  4. R. Burachik, A. Iusem: A generalized proximal point algorithm for the variational inequality problem in Hilbert space, SIAM J. Optim. 8 (1998) 197–216.https://doi.org/10.1137/S1052623495286302Google Scholar
  5. Y. Censor, A. Iusem, S. A. Zenios: An interior point method with Bregman functions for the variational inequality problem with paramonotone operators, Math. Program. 81 (1998) 373–400.https://doi.org/10.1007/BF01580089Google Scholar
  6. J.-P. Crouzeix: Pseudo-monotone variational inequality problems: existence of solutions, Math. Program. 78 (1997) 305–314.https://doi.org/10.1007/BF02614358Google Scholar
  7. J.-P. Crouzeix, D. L. Zhu, P. Marcotte: Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities, Math. Program. 88 (2000) 521–539.https://doi.org/10.1007/PL00011384Google Scholar
  8. P. da Silva, J. Eckstein, C. Humes: Rescaling and stepsize selection in proximal methods using separable generalized distances, SIAM J. Optim. 12 (2001) 238–261.https://doi.org/10.1137/S1052623499365784Google Scholar
  9. F. Facchinei, J.-S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York (2003).https://doi.org/10.1007/b97543Google Scholar
  10. N. Hadjisavvas, S. Schaible: On a generalization of paramonotone maps and its application to solving the stampacchia variational inequality, Optimization 55 (2006) 593–604.https://doi.org/10.1080/02331930600816114Google Scholar
  11. A. Iusem: On some properties of paramonotone operators, J. Convex Analysis 5 (1998) 269–278.https://doi.org/10.68381/jca05-19Google Scholar
  12. A. Kaplan, R. Tichatschke: Interior proximal method for variational inequalities: case of non-paramonotone operators, Set-Valued Anal. 12 (2004) 357–382.https://doi.org/10.1007/s11228-004-4379-2Google Scholar
  13. A. Kaplan, R. Tichatschke: Bregman functions and proximal methods for variational problems with nonlinear constraints, Optimization 56(1–2) (2007) 253–265.https://doi.org/10.1080/02331930600809259Google Scholar
  14. A. Kaplan, R. Tichatschke: Interior proximal method for variational inequalities on non-polyhedral sets, Discuss. Math., Differ. Incl. Control Optim. 27(1) (2007) 71–93.https://doi.org/10.7151/dmdico.1077Google Scholar
  15. A. Kaplan, R. Tichatschke: On the convergence of interior proximal methods for variational inequalities on non-polyhedral sets, Discuss. Math., Differ. Incl. Control Optim. 30(1) (2010) 51–59.https://doi.org/10.7151/dmdico.1111Google Scholar
  16. S. Karamardian: Complementarity problems over cones with monotone and pseudomonotone maps, J. Optimization Theory Appl. 18 (1976) 445–454.https://doi.org/10.1007/BF00932654Google Scholar
  17. B. Kien, J.-C. Yao, N. Yen: On the solution existence of pseudomonotone variational inequalities, J. Glob. Optim. 41 (2008) 135–145.https://doi.org/10.1007/s10898-007-9251-0Google Scholar
  18. N. Langenberg: Convergence analysis of an extended auxiliary problem principle with various stopping criteria, Optim. Methods Softw. 26(1) (2011) 127–154.https://doi.org/10.1080/10556780903406589Google Scholar
  19. N. Langenberg: Pseudomonotone operators and the Bregman Proximal Point Algorithm, J. Glob. Optim. 47(4) (2010) 537–555.https://doi.org/10.1007/s10898-009-9470-7Google Scholar
  20. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1997).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  21. M. Solodov, B. Svaiter: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Math. Oper. Res. 25 (2000) 214–230.https://doi.org/10.1287/moor.25.2.214.12222Google Scholar

Suggested citation

N. Langenberg. “On the Cutting Plane Property and the Bregman Proximal Point Algorithm.” Journal of Convex Analysis 18 (2011), No. 3, 601–619. https://doi.org/10.68381/jca18038

Download BibTeXPublished by Heldermann Verlag.

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