Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm

Robert M. Freund and Jorge Vera

We study the complexity of solving a convex optimization problem in conic linear form, namely: CP(d): maximize $cx$ subject ot $b - Ax \in C_Y, x \in C_X$, where $C_X$ and $C_Y$ are closed convex cones in n and m dimensions, 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 $\epsilon$-optimal solution of CP(d) in at most $O (n^2 ln(C(d)||d||/(\epsilon))$ iterations of the ellipsoid algorithm. The quantity C(d) is the ``condition number" of the program CP(d) originally developed by Renegar, and essentially is a scale invariant reciprocal of the smallest data perturbation for which the perturbed problem becomes either infeasible or unbounded.

MIT Operations Research Center Technical Report