Ellipsoidal approximations of convex sets based on the volumetric barrier

• 成果类型: Article
• 署名作者: Anstreicher, KM
• 署名单位: University of Iowa
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.24.1.193
• 发表日期: 1999
• 页码: 193-203
• 关键词: algorithms

摘要

Let C subset of R-n be a convex set. We assume that \\x\\(infinity) less than or equal to 1 for all x is an element of C, and that C contains a ball of radius 1/R. For x is an element of R-n, r is an element of R, and B an n X n symmetric positive definite matrix, let E(x, B, r) = {y\(y - x)B-T(y - x) less than or equal to r(2)}. A beta-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/beta) subset of C subset of 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.