Methods of centers for variational inequalities and linear programming

摘要

The ratio of the volumes of the inscribed ellipsoids in the space of residuals for the known cutting plane methods is a constant less than 1. In this paper the conditions are discovered under which the given ratio goes to zero. Analytical centers methods with different potential functions are considered. The algorithms based upon these methods are used for solving non-monotone variational inequalities, as well as for solving linear programming problems with quadratic rate of convergence starting with arbitrary initial approximation.