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

Abstract

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

How to cite

top

Raupp, 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
  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.  
  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.  
  4. E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems. The Mathematics Student63 (1994) 123–145.  
  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.  
  6. H. Brezis, L. Niremberg and G. Stampachia, A remark on Ky Fan's minimax principle. Boll. Un. Mat. Ital.6 (1972) 293–300.  
  7. K. Fan, A minimax inequality and applications, in Inequality III, edited by O. Shisha. Academic Press, NY (1972) 103–113.  
  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.  
  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. B76 (1997) 131–154.  
  10. C.C. Gonzaga, Path following methods for linear programming. SIAM Rev.34 (1992) 167–224.  
  11. G.M. Korpelevich, Extragradient method for finding saddle points and other problems. Matecon12 (1976) 747–756.  
  12. A.N. Iusem and W. Sosa, New existence results for equilibrium problems. Nonlinear Anal.-Theor.52 (2003) 621–635.  
  13. A.N. Iusem and W. Sosa, Iterative algorithms for equilibrium problems. Optimization52 (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. B69 (1995) 149–176.  
  15. H. Nikaido and K. Isoda, Note on noncooperative convex games. Pacific J. Math.5 (1955) 807–815.  
  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.  
  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.  
  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.  
  19. Y. Ye, A potential reduction algorithm allowing column generation. SIAM J. Optim.2 (1992) 7–20.  
  20. Y. Ye, Complexity analysis of the analytic center cutting plane method that uses multiple cuts. Math. Program.78 (1997) 85–104.  
  21. Y. Ye, Interior Point Algorithms: Theory and Analysis. Wiley–Interscience Series in Discrete Mathematics and Optimization, John Wiley and Sons, New York (1997).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.