An interior-point perspective on sensitivity analysis in semidefinite programming

EA Yıldırım - Mathematics of Operations Research, 2003 - pubsonline.informs.org
Mathematics of Operations Research, 2003pubsonline.informs.org
We study the asymptotic behavior of the interior-point bounds arising from the work of
Yıldırım and Todd on sensitivity analysis in semidefinite programming in comparison with the
optimal partition bounds. We introduce a weaker notion of nondegeneracy and discuss its
implications. For perturbations of the right-hand-side vector or the cost matrix, we show that
the interior-point bounds evaluated on the central path using the Monteiro-Zhang family of
search directions converge (as the duality gap tends to zero) to the symmetrized version of …
We study the asymptotic behavior of the interior-point bounds arising from the work of Yıldırım and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. We introduce a weaker notion of nondegeneracy and discuss its implications. For perturbations of the right-hand-side vector or the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang family of search directions converge (as the duality gap tends to zero) to the symmetrized version of the optimal partition bounds under mild nondegeneracy assumptions. Furthermore, our 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. We extend our results to the case of simultaneous perturbations of the right-hand-side vector and the cost matrix. We also provide examples illustrating that our assumptions, in general, cannot be weakened.
INFORMS
以上显示的是最相近的搜索结果。 查看全部搜索结果