Condition Numbers for Optimization Problems

The condition number of a matrix plays a central role in numerical linear algebra. The condition number of a matrix can be seen as a measure of well-posedness. It provides a natural tool to estimate the effects of data perturbations, the performance of iterative algorithms, and the effects of finite precision computation in the solution of linear systems of equations.

We show that the above traditional concept of conditioning for matrices naturally extends to linear programming, and to more general optimization problems in conic programming form. In particular, we discuss several theoretical properties of a canonical measure of well-posedness of a conic program. We also show how this measure of well-posedness is an appropriate parameter for analyzing the performance of various types optimization algorithms, such as the ellipsoid method, interior-point methods, and the perceptron algorithm.