Conditioning of semidefinite programs

Citation
Mv. Nayakkankuppam et Ml. Overton, Conditioning of semidefinite programs, MATH PROGR, 85(3), 1999, pp. 525-540
Citations number
14
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
85
Issue
3
Year of publication
1999
Pages
525 - 540
Database
ISI
SICI code
0025-5610(199908)85:3<525:COSP>2.0.ZU;2-Y
Abstract
This paper studies the conditioning of semidefinite programs by analyzing t he effect of small perturbations in problem data on the solution. Under the assumptions of strict complementarity and nondegeneracy, an explicit bound on the change in the solution is derived in a primal-dual framework, using tools from the Kantorovic theory. This approach also quantifies the size o f permissible perturbations. We include a discussion of these results for b lock diagonal semidefinite programs, of which linear programming is a speci al case.