EQUILIBRIUM PROGRAMMING USING PROXIMAL-LIKE ALGORITHMS

We compute constrained equilibria satisfying an optimality condition. Important examples include convex programming, saddle problems, noncoo perative games, and variational inequalities. Under a monotonicity hyp othesis we show that equilibrium solutions can be found via iterative convex minimization. In the main algorithm each stage of computation r equires 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 e rrors. (C) 1997 The Mathematical Programming Society, Inc. Published b y Elsevier Science B.V.