Pre-Conditioners and Relations between Different Measures of Conditioning for Conic Linear Systems

Marina Epelman and Robert M. Freund

This paper studies measures of conditioning for a conic linear system of the FPd: Ax=b, x \in C, where C is a convex cone, and whose data is d=(A,b). We present a new measure of conditioning for FPd, denoted \mu, and we show implications of \mu for problem geometry and algorithm complexity, and demonstrate that the value of \mu is independent of the specific data representation of FPd. We then prove certain relations among a variety of condition measures for FPd, including \mu, \sigma, 'chi bar', and C(d). We then introduce the notion of a `pre-conditioner' for FPd which results in an equivalent formulation with a better condition number. We characterize the best such pre-conditioner and provide an algorithm for constructing an equivalent data instance whose condition number is within a known factor of the best possible.

MIT Operations Research Center Working Paper OR344-00.