Groupe d’études et de recherche en analyse des décisions


A Two-Cut Approach in the Analytic Center Cutting Plane Method


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 calls to the oracle and primal (damped) projected Newton steps. We also handle the case of deep cuts.

, 20 pages