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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A.S. Antipin, Controlled proximal differential systems for saddle problems,Differential Equations 28 (1992) 1498–1510.
A.S. Antipin, Feed-back controlled saddle gradient processes,Automat. Remote Control 55 (1994) 311–320.
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.
A. Auslender, J.P. Crouzeix and P. Fedit, Penalty-proximal methods in convex programming,Journal of Optimization Theory and Applications 55 (1987) 1–21.
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.
D.P. Bertsekas and P. Tseng, Partial proximal minimization algorithms for convex programming,SIAM Journal of Optimization 4 (1994) 551–572.
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.
A. Brønsted and R.T. Rockafellar, On the subdifferentiability of convex functions,Proceedings of the American Mathematical Society 16 (1965) 605–611.
Y. Censor and S. Zenios, The proximal minimization algorithm with D-functions,Journal of Optimization Theory and Applications 73 (1992) 451–464.
G. Chen and M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions,SIAM Journal of Optimization 3 (1993) 538–543.
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).
J. Eckstein, Nonlinear proximal point algorithms using Bregman functions with applications to convex programming,Mathematics of Operations Research 18 (1) (1993) 202–226.
P.P.B. Eggermont, Multiplicative iterative algorithms for convex programming,Linear Algebra and its Applications 130 (1990) 25–42.
Yu.M. Ermol’ev and S.P. Uryas’ev, Nash equilibrium inn-person games,Kibernetika 3 (1982) 85–88 (in Russian).
S.D. Flåm, Paths to constrained Nash equilibria,Applied Mathematics and Optimization 27 (1993) 275–289.
S.D. Flåm and A. Ruszczynski, Noncooperative games: Computing equilibrium by partial regularization, Working Paper IIASA 42, 1994.
S.D. Flåm, Approaches to economic equilibrium,Journal of Economic Dynamics and Control 20 (1996) 1505–1522.
N. Hadjisavvas and S. Schaible, On strong monotonicity and (semi)strict quasimonotonicty,Journal of Optimization Theory and Applications 79 (1993) 139–155.
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.
J.-B. Hiriart-Urruty and C. Lemaréchal,Convex Analysis and Minimization Algorithms (Springer, Berlin, 1993).
A.N. Iusem, B.F. Svaiter and M. Teboulle, Entopy-like proximal methods in convex programming,Mathematics of Operations Research 19 (1994) 790–814.
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.
G.M. Korpelevich, The extragradient method for finding saddle points and other problems,Ekon. i Mat. Metody 12 (1976) 747–756.
B. Martinet, Perturbations des methodes d’optimisation,RAIRO Anal. Numer. 12 (1978) 153–171.
M.J. Osborne and A. Rubinstein,A Course in Game Theory (MIT Press, Cambridge, MA, 1994).
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.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar, Monotone operators and the proximal point algorithm,SIAM Journal of Control and Optimization 14 (1976) 877–898.
J.B. Rosen, Existence and uniqueness of equilibrium points for concaveN-person games,Econometrica 33 (1965) 520–534.
A. Ruszczynski, A partial regularization method for saddle point seeking, Working Paper IIASA 20, 1994.
M. Teboulle, Entropic proximal mappings with applications to nonlinear programming,Mathematics of Operations Research 17 (1992) 670–690.
J. Tirole,The Theory of Industrial Organization (MIT Press, Cambridge, MA, 1988).
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported partly by the Norwegian Research Council, project: Quantec 111039/401.
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02614504