Article ID: | iaor20002362 |
Country: | Germany |
Volume: | 85 |
Issue: | 3 |
Start Page Number: | 525 |
End Page Number: | 540 |
Publication Date: | Jan 1999 |
Journal: | Mathematical Programming |
Authors: | Overton M.L., Nayakkankuppam M.V. |
Keywords: | programming: linear |
This paper studies the conditioning of semidefinite programs by analyzing the effect of small perturbations in problem data on the solution. Under the assumptions of strict complementarity and non-degeneracy, an explicit bound on the change in the solution is derived in a primal–dual framework, using tools from the Kantorovič theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case.