An analytic center cutting plane algorithm for finding equilibrium points

Fernanda M. P. Raupp and Wilfredo Sosa

We apply an analytic center cutting plane algorithm in order to solve approximately the following Scalar Equilibrium Problem (SEP in short): find $\bar x \in K$ such that $f(\bar x,y) \geq 0$ for all $y \in K$, where K is a nonempty closed convex subset of $[0,1]^n$ and $f : [0,1]^n\times [0,1]^n \rightarrow \R$ is a function that is upper semicontinuous in the first variable, lower semicontinuous and convex in the second one. $f$ also satisfies the following properties: $f(x,x) = 0$ for all $x\in K$ and $f(x,y) \geq 0$ implies $f(y,x) \leq 0$. This problem is associated to a convex feasibility problem and has as particular cases: variational inequality problem, fixed point problem, complementarity problem, convex-concave constrained saddle point problem, convex minimization problem and Nash equilibria problem for noncooperative games, among others. We analyze the convergence and complexity of the algorithm, which is a variant of one in Goffin, Luo and Ye of 1996.

Technical Report 07/2000 LNCC - MCT - Brazil