Optimization Online


An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming

Alper Yildirim (yildirim***at***ams.sunysb.edu)

Abstract: We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang family of search directions converge to the symmetrized version of the optimal partition bounds under appropriate nondegeneracy assumptions, which can be weaker than the usual notion of nondegeneracy. Furthermore, the analysis does not assume strict complementarity as long as the central path converges to the analytic center in a relatively controlled manner. We also show that the same convergence results carry over to iterates lying in an appropriate (very narrow) central path neighborhood if the Nesterov-Todd direction is used to evaluate the interior-point bounds.

Keywords: semidefinite programming, sensitivity analysis, interior-point methods

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Mathematics of Operations Research, 28 (4), pp. 649 -- 676 (2003).


Entry Submitted: 06/05/2001
Entry Accepted: 06/06/2001
Entry Last Modified: 11/24/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society