A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems

In recent years, a body of research into condition numbers for convex optimization has been developed, aimed at capturing the intuitive notion of problem behavior. This research has been shown to be relevant in studying the efficiency of algorithms ( including interior-point algorithms) for convex optimization as well as other behavioral characteristics of these problems such as problem geometry, deformation under data perturbation, etc. This paper studies measures of conditioning for a conic linear system of the form (FPd) : Ax=b, x is an element of C-X, whose data is d=(A,b). We present a new measure of conditioning, denoted mu(d), and we show implications of mu(d) for problem geometry and algorithm complexity and demonstrate that the value of mu=mu(d) is independent of the specific data representation of (FPd). We then prove certain relations among a variety of condition measures for (FPd), including mu(d), sigma(d), (chi) over bar (d), and C(d). We discuss some drawbacks of using the condition number C (d) as the sole measure of conditioning of a conic linear system, and we introduce the notion of a preconditioner for (FPd), which results in an equivalent formulation (FP(d) over bar) of (FPd) with a better condition number C((d) over tilde). We characterize the best such preconditioner and provide an algorithm and complexity analysis for constructing an equivalent data instance (d) over tilde whose condition number C ((d) over tilde) is within a known factor of the best possible.