##
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

Contact: rfreund@mit.edu