Shallow, deep and very deep cuts in the analytic center cutting plane method

The analytic center cutting plane (ACCPM) methods aims to solve nondifferen tiable convex problems. The technique consists of building an increasingly refined polyhedral approximation of the solution set. The linear inequaliti es that define the approximation are generated by an oracle as hyperplanes separating a query point from the solution set. In ACCPM, the query point i s the analytic center, or an approximation of it, for the current polyhedra l relaxation. A primal projective algorithm is used to recover feasibility and then centrality. In this paper we show that the cut doe's not need to go through the query p oint: it can be deep or shallow. The primal framework leads to a simple ana lysis of the potential variation, which shows that the inequality needed fo r convergence of the algorithm is in fact attained at the first iterate of the feasibility step.