Interior proximal method for variational inequalities on non-polyhedral sets

Alexander Kaplan ; Rainer Tichatschke

Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 27 (2007), p. 71-93 / Harvested from The Polish Digital Mathematics Library

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

Publié le : 2007-01-01

Zbl 1158.47052

EUDML-ID : urn:eudml:doc:271153

Bibliographie

[000] [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. | Zbl 0855.90095

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

[002] [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. | Zbl 1039.90518

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

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

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

[006] [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. | Zbl 0911.90273

[007] [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. | Zbl 0882.90105

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

[009] [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. | Zbl 1082.65539

[010] [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. | Zbl 0919.90123

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

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

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

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

[015] [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. | Zbl 0804.49011

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

[017] [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. | Zbl 1047.49005

[018] [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. | Zbl 1072.65093

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

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

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

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

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

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

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

[026] [27] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton 1970. | Zbl 0193.18401

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

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

[029] [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. | Zbl 0980.90097

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