##
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.