Abstract

A convex optimization problem in conic linear form is an optimization problem of the form CP(d): maximize cTx s.t. b - Ax ? CY, x ? CX, where CX and CY are closed convex cones in n-and m-dimensional spaces X and Y, respectively, and the data for the system is d = (A, b, c). We show that there is a version of the ellipsoid algorithm that can be applied to find an ?-optimal solution of CP(d) in at most O(n2 ln(C(d)?c?*/c1?)) iterations of the ellipsoid algorithm, where each iteration must either perform a separation cut on one of the cones CX or CY or perform a related optimality cut. The quantity C(d) is the "condition number" of the program CP(d) originally developed by Renegar and is essentially a scale-invariant reciprocal of the smallest data perturbation ?d = (?A, ?b, ?c) for which the system CP(d + ?d) becomes either infeasible or unbounded. The scalar quantity c1 is a constant that depends only on the simple notion of the "width" of the cones and is independent of the problem data d = (A, b, c) but may depend on the dimensions m and/or n. grant from CONICYT within the FONDAP program in applied mathematics.