Homogeneous Analytic Center Cutting Plane Methods for Convex Problems and Variational Inequalities

Y. Nesterov and J.-Ph, Vial

In this paper we consider a new analytic center cutting plane method in a projective space. We prove the efficiency estimates for the general scheme and show that these results can be used in the analysis of a feasibility problem, the variational inequality problem and the problem of constrained minimization. Our analysis is valid even for the problems whose solution belongs to the boundary of the domain.

Logilab Technical Report 1997.4 July 9, 1997

Contact: jpvial@uni2a.unige.ch,nesterov@core.ucl.ac.be