Interior proximal method for variational inequalities on non-polyhedral sets

Kaplan, Alexander ; Tichatschke, Rainer

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

Résumé

Interior proximal methods for variational inequalities are, in fact, designed to handle problems on polyhedral convex sets or balls, only. Using a slightly modified concept of Bregman functions, we suggest an interior proximal method for solving variational inequalities (with maximal monotone operators) on convex, in general non-polyhedral sets, including in particular the case in which the set is described by a system of linear as well as strictly convex constraints. The convergence analysis of the method studied admits the use of the -enlargement of the operator and an inexact solution of the subproblems.

Détail

Keywords: variational inequalities, Bregman function, proximal algorithm

Bibliographie

[1] A. Auslender and M. Haddou, An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities, Math. Programming 71 (1995), 77-100.

[2] A. Auslender and M. Teboulle, Entropic proximal decomposition methods for convex programs and variational inequalities, Math. Programming Ser. A 91 (2001), 33-47.

[3] A. Auslender, M. Teboulle and S. Ben-Tiba, Interior proximal and multiplier methods based on second order homogeneous kernels, Mathematics of Oper. Res. 24 (1999), 645-668.

[4] A. Auslender, M. Teboulle and S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities, Computational Optimization and Applications 12 (1999), 31-40.

[5] H. Bauschke and J. Borwein, Legendre functions and the method of random Bregman projections, J. Convex Analysis 4 (1997), 27-67.

[6] H. Brézis, Équations et inéquations non linéaires dans les espaces vectoriels en dualité, Ann. Inst. Fourier 18 (1968), 115-175.

[7] R. Burachik and A. Iusem, A generalized proximal point algorithm for the variational inequality problem in Hilbert space, SIAM J. Optim. 8 (1998), 197-216.

[8] R. Burachik, A. Iusem and B. Svaiter, Enlargements of maximal monotone operators with application to variational inequalities, Set-Valued Analysis 5 (1997), 159-180.

[9] R. Burachik and B. Svaiter, ϵ-enlargement of maximal monotone operators in Banach spaces, Set-Valued Analysis 7 (1999), 117-132.

[10] R. Burachik and B. Svaiter, A relative error tolerance for a family of generalized proximal point methods, Math. of Oper. Res. 26 (2001), 816-831.

[11] Y. Censor, A. Iusem and S.A. Zenios, An interior point method with Bregman functions for the variational inequality problem with paramonotone operators, Math. Programming 81 (1998), 373-400.

[12] Y. Censor and S.A. Zenios, Proximal minimization algorithm with d-functions, J. Optim. Theory Appl. 73 (1992), 451-464.

[13] J. Eckstein, Approximate iterations in Bregman-function-based proximal algorithms, Math. Programming 83 (1998), 113-123.

[14] A. Iusem, On some properties of generalized proximal point methods for quadratic and linear programming, JOTA 85 (1995), 593-612.

[15] A. Iusem, On some properties of paramonotone operators, J. of Conv. Analysis 5 (1998), 269-278.

[16] A. Kaplan and R. Tichatschke, Stable Methods for Ill-Posed Variational Problems - Prox-Regularization of Elliptic Variational Inequalities and Semi-Infinite Optimization Problems, Akademie Verlag, Berlin 1994.

[17] A. Kaplan and R. Tichatschke, Proximal point approach and approximation of variational inequalities, SIAM J. Control Optim. 39 (2000), 1136-1159.

[18] A. Kaplan and R. Tichatschke, Convergence analysis of non-quadratic proximal methods for variational inequalities in Hilbert spaces, J. of Global Optimization 22 (2002), 119-136.

[19] A. Kaplan and R. Tichatschke, Interior proximal method for variational inequalities: Case of non-paramonotone operators, Journal of Set-Valued Analysis 12 (2004), 357-382.

[20] A. Kaplan and R. Tichatschke, On inexact generalized proximal methods with a weakened error tolerance criterion, Optimization 53 (2004), 3-17.

[21] K. Kiwiel, Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim. 35 (1997), 1142-1168.

[22] J.L. Lions, Quelques Méthodes de Résolution de Problèmes Nonlinéaires, Dunod, Paris 1969.

[23] B. Martinet, Régularisation d'inéquations variationelles par approximations successives, RIRO 4 (1970), 154-159.

[24] N. Megiddo, Pathways to the optimal set in linear programming, In Progress in Mathematical Programming, Interior Point and Related Methods (1989), N. Megiddo, Ed., Springer, New York, pp. 131-158.

[25] D. Pascali and S. Sburlan, Nonlinear Mappings of Monotone Type, Editura Academiei, Bucharest 1978.

[26] B.T. Polyak, Introduction to Optimization, Optimization Software, Inc. Publ. Division, New York 1987.

[27] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton 1970.

[28] R.T. Rockafellar, On the maximality of sums of nonlinear monotone operators, Trans. Amer. Math. Soc. 149 (1970), 75-88.

[29] R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), 877-898.

[30] M. Solodov and 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.

[31] M. Teboulle, Convergence of proximal-like algorithms, SIAM J. Optim. 7 (1997), 1069-1083.