Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

E. Alper Yildirim and Michael J. Todd

We analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP). We obtain tight bounds on the norm of the perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, non-degenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from the simplex method. We also present explicit bounds for SDP using the AHO, H..K..M, and NT directions.

Technical Report No. 1253, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801