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

The authors analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP) problems. They obtain tight bounds on the perturbations so that the result of a single interior-point iteration would yield feasible solutions to the perturbed problem and its dual. For the (LP) case where the solution is unique and nondegenerate, they also show that the bounds arising from the interior-point method asymptotically coincide with the bounds that keep the current basis optimal (after symmetrization with respect to the origin). In the (SDP) case the bounds are obtained by using the general family of R. D. C. Monteiro and Y. Zhang search directions as well as by using three specific search directions.