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

Christina Jager

Discussiones Mathematicae, Differential Inclusions, Control and Optimization (2007)

  • Volume: 27, Issue: 1, page 51-69
  • ISSN: 1509-9407

Abstract

top
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].

How to cite

top

Christina Jager. "Numerical considerations of a hybrid proximal projection algorithm for solving variational inequalities." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 27.1 (2007): 51-69. <http://eudml.org/doc/271192>.

@article{ChristinaJager2007,
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].},
author = {Christina Jager},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
keywords = {variational inequality; proximal point algorithm; bundle method},
language = {eng},
number = {1},
pages = {51-69},
title = {Numerical considerations of a hybrid proximal projection algorithm for solving variational inequalities},
url = {http://eudml.org/doc/271192},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Christina Jager
TI - Numerical considerations of a hybrid proximal projection algorithm for solving variational inequalities
JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization
PY - 2007
VL - 27
IS - 1
SP - 51
EP - 69
AB - 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].
LA - eng
KW - variational inequality; proximal point algorithm; bundle method
UR - http://eudml.org/doc/271192
ER -

References

top
  1. [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. Zbl1039.90529
  2. [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. Zbl0911.90273
  3. [3] A. Cegielski and R. Dylewski, Selection strategies in projection methods for convex minimization problems, Discrete Math. 22 (1) (2002), 97-123. Zbl1175.90310
  4. [4] A. Cegielski and R. Dylewski, Residual selection in a projection method for convex minimization problems, Optimization 52 (2) (2003), 211-220. Zbl1057.49021
  5. [5] G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Mathematical Programming 64 (1994), 81-101. Zbl0823.90097
  6. [6] C. Jager, Numerische Analyse eines proximalen Projektions-Algorithmus, Diploma Thesis, University of Trier 2004. 
  7. [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. Zbl0804.49011
  8. [8] A. Kaplan and R. Tichatschke, Multi-step-prox-regularization method for solving convex variational problems, Optimization 33(4) (1995), 287-319. Zbl0820.65035
  9. [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. Zbl0996.65066
  10. [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. Zbl1047.49005
  11. [11] A. Kaplan and R. Tichatschke, Interior proximal method for variational inequalities: case of nonparamonotone operators, Set-Valued Analysis 12 (4) (2004), 357-382. Zbl1072.65093
  12. [12] K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Mathematical Programming 46 (1990), 105-122. Zbl0697.90060
  13. [13] C. Lemaréchal and R. Mifflin, eds, Nonsmooth Optimization, volume 3 of IIASA Proceedings Series, Oxford, 1978. Pergamon Press. 
  14. [14] C. Lemaréchal, A. Nemirovski and Y. Nesterov, New variants of bundle methods, Mathematical Programming 69 (1) (B) (1995), 111-147. Zbl0857.90102
  15. [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. Zbl0215.21103
  16. [16] Numerical Algorithms Group, NAG-Library, http://www.nag.co.uk/. 
  17. [17] R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14 (1976), 877-898. Zbl0358.90053
  18. [18] R.T. Rockafellar, On the maximality of sums of nonlinear monotone operators, Transactions of the American Mathematical Society 149 (1970), 75-88. Zbl0222.47017
  19. [19] H. Schramm, Eine Kombination von Bundle-und Trust-Region-Verfahren zur Lösung nichtdifferenzierbarer Optimierungsprobleme, Bayreuth. Math. Schr. 30 (1989), viii+205. Zbl0683.90069
  20. [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. Zbl0761.90090
  21. [21] N.Z. Shor, Minimization Methods for Nondifferentiable Functions, Springer-Verlag 1985. 
  22. [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. Zbl0971.90062

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.