##
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

Contact: fernanda@lncc.br