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

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 perturbations that allow interior-point methods to recover feasible and near-optimal solutions in a single interior-point iteration. For the unique, nondegenerate solution case in LP, we show that the bounds obtained using interior-point methods compare nicely with the bounds arising from using the optimal basis. We also present explicit bounds for SDP using the Monteiro–Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions.