Journal article
Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier
Mathematics of operations research, Vol.24(1), pp.193-203
02/01/1999
DOI: 10.1287/moor.24.1.193
Abstract
Let C ⊂R
n
be a convex set. We assume that ‖x‖
∞
≤ 1 for all x ∈ C, and that C contains a ball of radius 1/R. For x ∈ R
n
, r ∈ R, and B and n × n symmetric positive definite matrix, let E(x, B, r) = {y|(y − x)
T
B(y − x) ≤ r
2
}. A β-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/β) ⊂ C ⊂ E(x, B, r). In the case that C is characterized by a separation oracle, it is well known that an O(n
3/2
)-rounding of C can be obtained using the shallow cut ellipsoid method in O(n
3
ln(nR)) oracle calls. We show that a modification of the volumetric cutting plane method obtains an O(n
3/2
)-rounding of C in O(n
2
ln(nR)) oracle calls. We also consider the problem of obtaining an O(n)-rounding of C when C has an explicit polyhedral description. Our analysis uses a new characterization of circumscribing ellipsoids centered at, or near, the volumetric center of a polyhedral set.
Details
- Title: Subtitle
- Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier
- Creators
- K. M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematics of operations research, Vol.24(1), pp.193-203
- DOI
- 10.1287/moor.24.1.193
- ISSN
- 0364-765X
- eISSN
- 1526-5471
- Language
- English
- Date published
- 02/01/1999
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380388102771
Metrics
1 Record Views