Skip to main content
SpringerLink
Log in

Equilibrium programming using proximal-like algorithms

  • Published:
Mathematical Programming Submit manuscript

Abstract

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncooperative games, and variational inequalities. Under a monotonicity hypothesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation requires two proximal steps, possibly using Bregman functions. One step serves to predict the next point; the other helps to correct the new prediction. To enhance practical applicability we tolerate numerical errors.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A.S. Antipin, Controlled proximal differential systems for saddle problems,Differential Equations 28 (1992) 1498–1510.

    MathSciNet  Google Scholar 

  2. A.S. Antipin, Feed-back controlled saddle gradient processes,Automat. Remote Control 55 (1994) 311–320.

    MATH  MathSciNet  Google Scholar 

  3. A.S. Antipin, Convergence and estimates of the rate of convergence of proximal methods to fixed points of extremal mappings,Zh. Vychisl. Mat. Fiz. 35 (1995) 688–704.

    MathSciNet  Google Scholar 

  4. A. Auslender, J.P. Crouzeix and P. Fedit, Penalty-proximal methods in convex programming,Journal of Optimization Theory and Applications 55 (1987) 1–21.

    Article  MATH  MathSciNet  Google Scholar 

  5. A. Auslender and M. Haddou, An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities,Mathematical Programming 71 (1995) 77–100.

    MathSciNet  Google Scholar 

  6. D.P. Bertsekas and P. Tseng, Partial proximal minimization algorithms for convex programming,SIAM Journal of Optimization 4 (1994) 551–572.

    Article  MATH  MathSciNet  Google Scholar 

  7. L.M. Bregman, The relaxation method of finding the common point of convex sets and its applications to the solution of problems in convex programming,USSR Computational Mathematics and Mathematical Physics 7 (1967) 200–217.

    Article  Google Scholar 

  8. A. Brønsted and R.T. Rockafellar, On the subdifferentiability of convex functions,Proceedings of the American Mathematical Society 16 (1965) 605–611.

    Article  MathSciNet  Google Scholar 

  9. Y. Censor and S. Zenios, The proximal minimization algorithm with D-functions,Journal of Optimization Theory and Applications 73 (1992) 451–464.

    Article  MATH  MathSciNet  Google Scholar 

  10. G. Chen and M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions,SIAM Journal of Optimization 3 (1993) 538–543.

    Article  MATH  MathSciNet  Google Scholar 

  11. A. Cournot,Recherches sur les Principes Mathématiques de la Théorie des Richesses (Paris, 1838); English translation:Researches into the Mathematical Principles of the Theory of Wealth (N. Bacon, ed.) (Macmillan, New York, 1897).

  12. J. Eckstein, Nonlinear proximal point algorithms using Bregman functions with applications to convex programming,Mathematics of Operations Research 18 (1) (1993) 202–226.

    MATH  MathSciNet  Google Scholar 

  13. P.P.B. Eggermont, Multiplicative iterative algorithms for convex programming,Linear Algebra and its Applications 130 (1990) 25–42.

    Article  MATH  MathSciNet  Google Scholar 

  14. Yu.M. Ermol’ev and S.P. Uryas’ev, Nash equilibrium inn-person games,Kibernetika 3 (1982) 85–88 (in Russian).

    MathSciNet  Google Scholar 

  15. S.D. Flåm, Paths to constrained Nash equilibria,Applied Mathematics and Optimization 27 (1993) 275–289.

    Article  MATH  MathSciNet  Google Scholar 

  16. S.D. Flåm and A. Ruszczynski, Noncooperative games: Computing equilibrium by partial regularization, Working Paper IIASA 42, 1994.

  17. S.D. Flåm, Approaches to economic equilibrium,Journal of Economic Dynamics and Control 20 (1996) 1505–1522.

    Article  MathSciNet  Google Scholar 

  18. N. Hadjisavvas and S. Schaible, On strong monotonicity and (semi)strict quasimonotonicty,Journal of Optimization Theory and Applications 79 (1993) 139–155.

    Article  MATH  MathSciNet  Google Scholar 

  19. P.T. Harker and J.-S. Pang, Finite-dimensional variational inequalities and nonlinear complementarity problems: A survey of theory, algorithms and applications,Mathematical Programming 48 (1990) 161–220.

    Article  MATH  MathSciNet  Google Scholar 

  20. J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Berlin, 1993).

    Google Scholar 

  21. A.N. Iusem, B.F. Svaiter and M. Teboulle, Entopy-like proximal methods in convex programming,Mathematics of Operations Research 19 (1994) 790–814.

    Article  MATH  MathSciNet  Google Scholar 

  22. A. N. Iusem, Some properties of generalized proximal point methods for quadratic and linear programming,Journal of Optimization Theory and Applications 85 (1995) 593–612.

    Article  MATH  MathSciNet  Google Scholar 

  23. G.M. Korpelevich, The extragradient method for finding saddle points and other problems,Ekon. i Mat. Metody 12 (1976) 747–756.

    MATH  Google Scholar 

  24. B. Martinet, Perturbations des methodes d’optimisation,RAIRO Anal. Numer. 12 (1978) 153–171.

    MATH  MathSciNet  Google Scholar 

  25. M.J. Osborne and A. Rubinstein,A Course in Game Theory (MIT Press, Cambridge, MA, 1994).

    Google Scholar 

  26. H. Robbins and D. Siegmund, A convergence theorem for nonnegative almost surmartingales and some applications, in: J. Rustagi, ed.,Optimizing Methods in Statistics (Academic Press, New York, 1971) 235–257.

    Google Scholar 

  27. R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).

    MATH  Google Scholar 

  28. R.T. Rockafellar, Monotone operators and the proximal point algorithm,SIAM Journal of Control and Optimization 14 (1976) 877–898.

    Article  MATH  MathSciNet  Google Scholar 

  29. J.B. Rosen, Existence and uniqueness of equilibrium points for concaveN-person games,Econometrica 33 (1965) 520–534.

    Article  MATH  MathSciNet  Google Scholar 

  30. A. Ruszczynski, A partial regularization method for saddle point seeking, Working Paper IIASA 20, 1994.

  31. M. Teboulle, Entropic proximal mappings with applications to nonlinear programming,Mathematics of Operations Research 17 (1992) 670–690.

    MATH  MathSciNet  Google Scholar 

  32. J. Tirole,The Theory of Industrial Organization (MIT Press, Cambridge, MA, 1988).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Economics Department, Bergen University, 5007, Bergen, Norway

    Sjur Didrik Flåm

  2. Computing Centre, Russian Academy of Sciences, 117967, Moscow, Russia

    Anatoly S. Antipin

Authors
  1. Sjur Didrik Flåm
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anatoly S. Antipin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sjur Didrik Flåm.

Additional information

Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Flåm, S.D., Antipin, A.S. Equilibrium programming using proximal-like algorithms. Mathematical Programming 78, 29–41 (1996). https://doi.org/10.1007/BF02614504

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02614504

Keywords

Search

Navigation