Multiple cuts in the analytic center cutting plane method

Jean-Louis Goffin and Jean-Philippe Vial

We analyze the multiple cut generation scheme in the analytic center cutting plane method. We propose an optimal primal and dual updating direction when the cuts are central. The direction is optimal in the sense that it maximizes the product of the new dual slacks and of the new primal variables within the trust regions defined by Dikin's primal and dual ellipsoids. The new primal and dual directions use the variance--covariance matrix of the normals to the new cuts in the metric given by Dikin's ellipsoid. We prove that the recovery of a new analytic center from the optimal restoration direction can be done in $O(p\log (p+1))$ damped Newton steps, where $p$ is the number of new cuts added by the oracle. The results and the proofs are independent of the specific scaling matrix---primal, dual or primal-dual---that is used in the computations. The computation of the optimal direction uses Newton's method applied to a self-concordant function of $p$ variables. The convergence result of Ye holds here also: the algorithm stops after $O^*(\frac{p^2n^2}{\varepsilon^2})$ cutting planes have been generated.

Logilab Technical Report 98.10, Department of Management Studies, University of Geneva, 102 Bd Carl Vogt, CH-1211 Geneva 4 Switzerland, June, 1998.

Contact: [email protected]

[DVI] [PS] [IP PAGE] [SEARCH AGAIN]