Ellipsoidal approximations of convex sets based on the volumetric barrier

Kurt M. Anstreicher
Additional contact information
Kurt M. Anstreicher: Department of Management Sciences, University of Iowa

No 1997045, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Let C [included] R[exp.n] be a convex set. We assume that [norm.x][infinity]≤1for all x [belong] C; and that C contains a ball of radius 1/R. For x [belong] R[exp.n] , r [belong] R, and B an nxn positive definite matrix, let E (x,B,r) ={y|(y - x) [exp.t] B(y - x) ≤ r[exp.2]}. A [bêta] -rounding of C is an ellipsoid E(x, B, r/[bêta][included]C[included]E(x, B, r).In the case that C is characterized by a separation oracle, it is well known that an O(n[exp.3/2] ) -rounding of C can be obtained using the shallow cut ellipsoid method in O(n[exp.3] ln(nR)) oracle calls. We show that a modification of the volumetric cutting plane method obtains an O(n[exp.3/2]) -rounding of C in O(n2 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.

Date: 1997-06-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1997.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1997045

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().