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