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