The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a...

Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the...

For a conic linear system of the form Ax ∈ K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar's condition number C(A) is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry,...

The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax 0. A natural condition measure associated with this algorithm is the Euclidean width T of the cone of feasible solutions, and the iteration complexity of the...

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model's behavior are precisely controlled independent of the problem instance: (i) the sizes of E-optimal solutions, and...

We evaluate the practical relevance of two measures of conic convex problem complexity as applied to second-order cone problems solved using the homogeneous self-dual (HSD) embedding model in the software SeDuMi. The first measure we evaluate is Renegar's data-based condition measure C(d), and...