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.
Contact: [email protected]