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 : https://doi.org/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},
zbl = {1198.90320},
mrnumber = {2248421},
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
DA  - 2006///
SP  - 37
EP  - 52
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2006008/
UR  - https://zbmath.org/?q=an%3A1198.90320
UR  - https://www.ams.org/mathscinet-getitem?mr=2248421
UR  - https://doi.org/10.1051/ro:2006008
DO  - 10.1051/ro:2006008
LA  - en
ID  - RO_2006__40_1_37_0
ER  - 
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 0976.90110

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :