Journal article
On Vaidya's Volumetric Cutting Plane Method for Convex Programming
Mathematics of operations research, Vol.22(1), pp.63-89
02/01/1997
DOI: 10.1287/moor.22.1.63
Abstract
We describe a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set ⊂ R
n
. At each step the algorithm has a system of linear inequality constraints which defines a polyhedron ⊃ , and an interior point x ∈ . The algorithm then either drops one constraint, or calls an oracle to check if x ∈ , and, if not, obtain a new constraint that separates x from . Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier V(·). Progress of the algorithm is measured in terms of changes in V(·). The algorithm is terminated when either it is discovered that x ∈ , or V(·) becomes large enough to demonstrate that the volume of must be below some prescribed amount. The complexity of the algorithm compares favorably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the total number of Newton steps required for termination by a factor of about 1.3 million, while at the same time decreasing the maximum number of constraints used to define from 10
7
n to 200n.
Details
- Title: Subtitle
- On Vaidya's Volumetric Cutting Plane Method for Convex Programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematics of operations research, Vol.22(1), pp.63-89
- DOI
- 10.1287/moor.22.1.63
- ISSN
- 0364-765X
- eISSN
- 1526-5471
- Language
- English
- Date published
- 02/01/1997
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380529502771
Metrics
6 Record Views