G-96-20
Shallow, Deep and Very Deep Cuts in the Analytic Center Cutting Plane Method
and BibTeX reference
The analytic center cutting plane (ACCPM) methods aims to solve nondifferentiable convex problems. The technique consists of building an increasingly refined polyhedral approximation of the solution set. The linear inequalities that define the approximation are generated by an oracle as hyperplanes separating a query point from the solution set. In ACCPM, the query point is the analytic center, or an approximation of it, for the current polyhedral relaxation. A primal projective algorithm is used to recover feasibility and then centrality. In this paper we show that the cut does not need to go through the query point: it can be deep or shallow. The primal framework leads to a simple analysis of the potential variation, which shows that the inequality needed for convergence of the algorithm is in fact attained at the first iterate of the feasibility step.
Published May 1996 , 21 pages
This cahier was revised in July 1997