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

Citation
Ea. Yildirim et Mj. Todd, Sensitivity analysis in linear programming and semidefinite programming using interior-point methods, MATH PROGR, 90(2), 2001, pp. 229-261
Citations number
27
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
2
Year of publication
2001
Pages
229 - 261
Database
ISI
SICI code
0025-5610(200104)90:2<229:SAILPA>2.0.ZU;2-Q
Abstract
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 method:, to recover feasible and near-optimal solutions in a single interior-point iteration. F or the unique. nondegenerate solution case in LP, we show that the bounds o btained using interior-point methods compare nicely with the hounds arising from using the optimal basis. We also present explicit bounds for SDP usin g the Monteiro-Zhang family of search directions and specialize them to the AHO, H..K..M, and NT directions.