Shallow, deep and very deep cuts in the analytic
center cutting plane method
Jean-Louis Goffin and Jean-Philippe Vial
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.
Logilab Technical Report 96.1,
HEC/Management Studies,
University of Geneva,
Switzerland,
May 15, 1996
Contact: [email protected]
![[PS]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)