A two-cut approach in the analytic center cutting plane method

Jean-Louis Goffin and Jean-Philippe Vial

We analyze the process of a two cut generation scheme in the analytic center cutting plane method. We propose an optimal restoration direction when the two cuts are central. The direction is optimal in the sense that it maximizes the product of the new slacks within the trust region defined by Dikin's ellipsoid. Using a long step argument, we prove convergence in $O^*(\frac{n^2}{\varepsilon^2})$ calls to the oracle and $O^*(\frac{n^2}{\varepsilon^2}\log \frac{1}{\varepsilon})$ primal (damped) projected Newton steps. We also handle the case of deep cuts.

Logilab Technical Report 97.6, Logilab, Department of Management Studies, University of Geneva

Contact: jpvial@uni2a.unige.ch, jlg@crt.umontreal.ca.