Download PDF - Numerical considerations of a hybrid proximal projection algorithm for solving variational inequalitiesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Numerical considerations of a hybrid proximal projection algorithm for solving variational inequalities

Authors 1

Affiliations

  1. Department of Mathematics, University of Trier, 54286 Trier, Germany

Abstract

In this paper, some ideas for the numerical realization of the hybrid proximal projection algorithm from Solodov and Svaiter [22] are presented. An example is given which shows that this hybrid algorithm does not generate a Fejér-monotone sequence. Further, a strategy is suggested for the computation of inexact solutions of the auxiliary problems with a certain tolerance. For that purpose, ε-subdifferentials of the auxiliary functions and the bundle trust region method from Schramm and Zowe [20] are used. Finally, some numerical results for non-smooth convex optimization problems are given which compare the hybrid algorithm to the inexact proximal point method from Rockafellar [17].

Keywords

ENG
variational inequality, proximal point algorithm, bundle method

Bibliography

  1. A. Auslender, M. Teboulle and S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Computational Optimization and Applications 12 (1-3) (1999), 31-40.
  2. R.S. Burachik and A.N. Iusem, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM Journal on Optimization 8 (1) (1998), 197-216.
  3. A. Cegielski and R. Dylewski, Selection strategies in projection methods for convex minimization problems, Discrete Math. 22 (1) (2002), 97-123.
  4. A. Cegielski and R. Dylewski, Residual selection in a projection method for convex minimization problems, Optimization 52 (2) (2003), 211-220.
  5. G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Mathematical Programming 64 (1994), 81-101.
  6. C. Jager, Numerische Analyse eines proximalen Projektions-Algorithmus, Diploma Thesis, University of Trier 2004.
  7. A. Kaplan and R. Tichatschke, Stable Methods for Ill-Posed Variational Problems-Prox-Regularization of Elliptic Variational Inequalities and Semi-Infinite Problems, Akademie Verlag 1994.
  8. A. Kaplan and R. Tichatschke, Multi-step-prox-regularization method for solving convex variational problems, Optimization 33(4) (1995), 287-319.
  9. A. Kaplan and R. Tichatschke, A general view on proximal point methods to variational inequalities in Hilbert spaces-iterative regularization and approximation, Journal of Nonlinear and Convex Analysis 2(3) (2001), 305-332.
  10. A. Kaplan and R. Tichatschke, Convergence analysis of non-quadratic proximal methods for variational inequalities in Hilbert spaces, Journal of Global Optimization 22 (1-4) (2002), 119-136.
  11. A. Kaplan and R. Tichatschke, Interior proximal method for variational inequalities: case of nonparamonotone operators, Set-Valued Analysis 12 (4) (2004), 357-382.
  12. K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Mathematical Programming 46 (1990), 105-122.
  13. C. Lemaréchal and R. Mifflin, eds, Nonsmooth Optimization, volume 3 of IIASA Proceedings Series, Oxford, 1978. Pergamon Press.
  14. C. Lemaréchal, A. Nemirovski and Y. Nesterov, New variants of bundle methods, Mathematical Programming 69 (1) (B) (1995), 111-147.
  15. B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (R-3) (1970), 154-158.
  16. Numerical Algorithms Group, NAG-Library, http://www.nag.co.uk/.
  17. R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14 (1976), 877-898.
  18. R.T. Rockafellar, On the maximality of sums of nonlinear monotone operators, Transactions of the American Mathematical Society 149 (1970), 75-88.
  19. H. Schramm, Eine Kombination von Bundle-und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme, Bayreuth. Math. Schr. 30 (1989), viii+205.
  20. H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM Journal on Optimization 2 (1992), 121-152.
  21. N.Z. Shor, Minimization Methods for Nondifferentiable Functions, Springer-Verlag 1985.
  22. M.V. Solodov and B.F. Svaiter, Forcing strong convergence of proximal point iterations in a Hilbert space, Mathematical Programming A87 (2000), 189-202.
Discussiones Mathematicae, Differential Inclusions, Control and Optimization
2007/27/1
Export to PBN, Opens in new tab
Pages:
51-69
Main language of publication
English
Received
2006-02-16
Published
2007

DOI: 10.7151/dmdico1076

Exact and natural sciences