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

Jager, Christina

Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 27 (2007) no. 1, pp. 51-69.

Résumé

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

Détail

Keywords: variational inequality, proximal point algorithm, bundle method

Bibliographie

[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.