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

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

0.00 Avg rating0 Votes
Article ID: iaor20001143
Country: Germany
Volume: 84
Issue: 1
Start Page Number: 89
End Page Number: 103
Publication Date: Jan 1999
Journal: Mathematical Programming
Authors: ,
Keywords: cutting plane algorithms
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.