- Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method Olivier Péton (petonhec.unige.ch) Jean-Philippe Vial (vialhec.unige.ch) Abstract: This paper analyzes the introduction of multiple central cuts in a conic formulation of the analytic center cutting plane method (in short ACCPM). This work extends earlier work on the homogeneous ACCPM, and parallels the analysis of the multiple cut process in the standard ACCPM. The main issue is the calculation of a direction that restores feasibility after introducing p new cutting planes at the query point. We prove that the new analytic center can be recovered in O(plog wp) damped Newton iterations, where w is a parameter depending of the data. We also present two special cases where the complexity can be decreased to O(p log p). Finally, we show that the number of calls to the oracle is the same as in the single cut case, up to a factor $\sqrt p$. Keywords: Cutting planes, analytic center, conic formulation, multiple cuts Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: HEC/Logilab Technical Report 2001.1 40, bd du Pont d'Arve CH-1211 Geneva 4, Switzerland Download: [Postscript]Entry Submitted: 05/25/2001Entry Accepted: 05/30/2001Entry Last Modified: 05/25/2001Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.