# An analytic center cutting plane algorithm for finding equilibrium points

Fernanda M.P. Raupp; Wilfredo Sosa

RAIRO - Operations Research (2006)

- Volume: 40, Issue: 1, page 37-52
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topRaupp, Fernanda M.P., and Sosa, Wilfredo. "An analytic center cutting plane algorithm for finding equilibrium points." RAIRO - Operations Research 40.1 (2006): 37-52. <http://eudml.org/doc/249625>.

@article{Raupp2006,

abstract = {
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.
},

author = {Raupp, Fernanda M.P., Sosa, Wilfredo},

journal = {RAIRO - Operations Research},

keywords = {Equilibrium problems; convex feasibility problem;
analytic center cutting plane algorithm.; equilibrium problems; analytic center cutting plane algorithm},

language = {eng},

month = {7},

number = {1},

pages = {37-52},

publisher = {EDP Sciences},

title = {An analytic center cutting plane algorithm for finding equilibrium points},

url = {http://eudml.org/doc/249625},

volume = {40},

year = {2006},

}

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

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 1

SP - 37

EP - 52

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

LA - eng

KW - Equilibrium problems; convex feasibility problem;
analytic center cutting plane algorithm.; equilibrium problems; analytic center cutting plane algorithm

UR - http://eudml.org/doc/249625

ER -

## References

top- 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.
- A.S. Antipin, From Optima to Equilibria, in Proceedings of ISA RAS, Dynamics of Non-Homogeneous Systems. Editorial URSS-Moscow 3 (2000) 35–64.
- Bianchi-Pini, A note on equilibrium problems with properly quasimonotone bifunctions. J. Global Optim.20 (2001) 67–76.
- E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems. The Mathematics Student63 (1994) 123–145.
- 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.
- H. Brezis, L. Niremberg and G. Stampachia, A remark on Ky Fan's minimax principle. Boll. Un. Mat. Ital.6 (1972) 293–300.
- K. Fan, A minimax inequality and applications, in Inequality III, edited by O. Shisha. Academic Press, NY (1972) 103–113.
- 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.
- 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. B76 (1997) 131–154.
- C.C. Gonzaga, Path following methods for linear programming. SIAM Rev.34 (1992) 167–224.
- G.M. Korpelevich, Extragradient method for finding saddle points and other problems. Matecon12 (1976) 747–756.
- A.N. Iusem and W. Sosa, New existence results for equilibrium problems. Nonlinear Anal.-Theor.52 (2003) 621–635.
- A.N. Iusem and W. Sosa, Iterative algorithms for equilibrium problems. Optimization52 (2003) 301–316.
- Y. Nesterov, Complexity estimates of some cutting plane methods based on the analytic barrier. Nondifferentiable and large-scale optimization. Math. Program. Ser. B69 (1995) 149–176.
- H. Nikaido and K. Isoda, Note on noncooperative convex games. Pacific J. Math.5 (1955) 807–815.
- 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.
- 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.
- 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.
- Y. Ye, A potential reduction algorithm allowing column generation. SIAM J. Optim.2 (1992) 7–20.
- Y. Ye, Complexity analysis of the analytic center cutting plane method that uses multiple cuts. Math. Program.78 (1997) 85–104.
- Y. Ye, Interior Point Algorithms: Theory and Analysis. Wiley–Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, New York (1997).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.