• Home
  1. Home
  2. Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method
Report
OA Policy
English

Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method

Contributors

Peton, Olivier; Vial, Jean-Philippe

Collection

  • Cahiers de recherche; 2001.03

Publication date

2001

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 cuts 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 (p log 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

UNIGE affiliation entities

Citation (ISO format)

PETON, Olivier, VIAL, Jean-Philippe. Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method. 2001

Main files (1)

Report

Identifiers

  • PID : unige:5844
571views
641downloads

Technical informations

Creation

15/04/2010 12:20:39

First validation

15/04/2010 12:20:39

Update

14/03/2023 15:26:49

Status update

14/03/2023 15:26:48

Last indexation

29/10/2024 14:24:25
All rights reserved by Archive ouverte UNIGE and the University of Geneva
OpenAIRE Indexed & Validated