An analytic center cutting plane algorithm for finding equilibrium points
RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1, pp. 37-52.

We present a variant of the analytic center cutting plane algorithm proposed by Goffin et al. (1996) to approximately solve equilibrium problems as proposed by Blum and Oettli (1994), which include as particular problems the variational inequalities problem, the Nash equilibria problem in non-cooperative games, the convex minimization problem, and the fixed point problem. Furthermore, we analyze the convergence and complexity of the modified algorithm.

DOI : 10.1051/ro:2006008
Classification : 90C25, 90C51
Mots-clés : equilibrium problems, convex feasibility problem, analytic center cutting plane algorithm 
@article{RO_2006__40_1_37_0,
     author = {Raupp, Fernanda M. P. and Sosa, Wilfredo},
     title = {An analytic center cutting plane algorithm for finding equilibrium points},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {37--52},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     doi = {10.1051/ro:2006008},
     mrnumber = {2248421},
     zbl = {1198.90320},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2006008/}
}
TY  - JOUR
AU  - Raupp, Fernanda M. P.
AU  - Sosa, Wilfredo
TI  - An analytic center cutting plane algorithm for finding equilibrium points
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2006
SP  - 37
EP  - 52
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2006008/
DO  - 10.1051/ro:2006008
LA  - en
ID  - RO_2006__40_1_37_0
ER  - 
%0 Journal Article
%A Raupp, Fernanda M. P.
%A Sosa, Wilfredo
%T An analytic center cutting plane algorithm for finding equilibrium points
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2006
%P 37-52
%V 40
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2006008/
%R 10.1051/ro:2006008
%G en
%F RO_2006__40_1_37_0
Raupp, Fernanda M. P.; Sosa, Wilfredo. An analytic center cutting plane algorithm for finding equilibrium points. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1, pp. 37-52. doi : 10.1051/ro:2006008. http://www.numdam.org/articles/10.1051/ro:2006008/

[1] A.S. Antipin and F.P. Vasil'Ev, A stabilization method for equilibrium programming problems with an inexactly specified set. Comp. Math. Math. Phys. 39 (1999) 1707-1714. | Zbl

[2] A.S. Antipin, From Optima to Equilibria, in Proceedings of ISA RAS, Dynamics of Non-Homogeneous Systems. Editorial URSS-Moscow 3 (2000) 35-64.

[3] Bianchi-Pini, A note on equilibrium problems with properly quasimonotone bifunctions. J. Global Optim. 20 (2001) 67-76. | Zbl

[4] E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems. The Mathematics Student 63 (1994) 123-145. | Zbl

[5] L.M. Bregman, The relaxation method for finding a common point of convex sets and its applications to solution of problems in convex programming. USSR Comp. Math. Math. Phys. 7 (1967) 200-217. | Zbl

[6] H. Brezis, L. Niremberg and G. Stampachia, A remark on Ky Fan's minimax principle. Boll. Un. Mat. Ital. 6 (1972) 293-300. | Zbl

[7] K. Fan, A minimax inequality and applications, in Inequality III, edited by O. Shisha. Academic Press, NY (1972) 103-113. | Zbl

[8] J.-L. Goffin, Z.-Q. Luo and Y. Ye, Complexity analysis of an interior cutting plane method for convex feasibility pProblems. SIAM J. Optim. 6 (1996) 638-652. | Zbl

[9] J.-L. Goffin, J. Gonzio, R. Sarkissian and J.-P. Vial, Solving nonlinear multicommodity flow problems by analytic center cutting plane method. Interior point methods in theory and practice. Math. Program. Ser. B 76 (1997) 131-154. | Zbl

[10] C.C. Gonzaga, Path following methods for linear programming. SIAM Rev. 34 (1992) 167-224. | Zbl

[11] G.M. Korpelevich, Extragradient method for finding saddle points and other problems. Matecon 12 (1976) 747-756.

[12] A.N. Iusem and W. Sosa, New existence results for equilibrium problems. Nonlinear Anal.-Theor. 52 (2003) 621-635. | Zbl

[13] A.N. Iusem and W. Sosa, Iterative algorithms for equilibrium problems. Optimization 52 (2003) 301-316.

[14] Y. Nesterov, Complexity estimates of some cutting plane methods based on the analytic barrier. Nondifferentiable and large-scale optimization. Math. Program. Ser. B 69 (1995) 149-176. | Zbl

[15] H. Nikaido and K. Isoda, Note on noncooperative convex games. Pacific J. Math. 5 (1955) 807-815. | Zbl

[16] F.M.P. Raupp and C.C. Gonzaga, A center cutting plane algorithm for a likelihood estimate problem. Comput. Optim. Appl. 21 (2001) 277-300. | Zbl

[17] G. Sonnevend, New algorithms in convex programming based on a notation of center and on rational extrapolations. International Series of Numerical Mathematics, Birkhauser Verlag, Basel, Switzerland 84 (1988) 311-327. | Zbl

[18] P.M. Vaidya, A Locally Well-Behaved Potential Function and a Simple Newton-Type Method for Finding the Center of a Polytope. Progress in Mathematical Programming: Interior Point and Related Methods, edited by N. Megiddo. Springer, New York (1989) 79-90. | Zbl

[19] Y. Ye, A potential reduction algorithm allowing column generation. SIAM J. Optim. 2 (1992) 7-20. | Zbl

[20] Y. Ye, Complexity analysis of the analytic center cutting plane method that uses multiple cuts. Math. Program. 78 (1997) 85-104. | Zbl

[21] Y. Ye, Interior Point Algorithms: Theory and Analysis. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, New York (1997). | Zbl

Cité par Sources :