Bulletin 105, Mai 99 

A special case of variational inequality problems is the linear or quadratic minimization problem over a polytop. We consider the cutting plane algorithm with analytic centers for solving such problems. Suppose a linear programming problem with nonempty feasible set Ay <= b minimizing c^Ty. The set of analytic centers

defines a smooth path by variing t called the central path, going from the analytic center of the polytop Ay <= b to the analytic center of the optimal face. The sequence of points computed by the analytic center cutting plane method lies on this central path. This implies linear convergence with respect to the objective value.

For the quadratic minimization problem

with Ay <= b, where Q is symmetric and positive semi-definite, the idea of the analytic center cutting plane method has to be generalized. Instead of using cuts defined by the gradient vector field we use cuts defined by level sets of the objective function. We show that the iterates y^k lie on a certain central path and converge at least linearly (in the sense of the objective) to an optimal solution.

Matthias Wick
mwick@math.unibas.ch