Sensitivity analysis of semidefinite programs without strong duality
Abstract: Suppose that we are given a feasible conic program with a finite optimal value and with strong duality failing. It is known that there are small perturbations of the problem data that lead to relatively big changes in the optimal value. We quantify the notion of big change in the case of a semidefinite program (SDP). We first show that for any SDP with a finite optimal value where strong duality fails, and where there is a nonzero duality gap, then for a sufficiently small step along any feasible perturbation direction, the optimal value changes by at least a fixed constant. And next, if there is a zero duality gap, with or without dual attainment, then any sufficiently small $\epsilon>0$ feasible perturbation changes the optimal value by at most $O(\epsilon^\gamma)$ for some, to be specified, constant $\gamma\in(0,1)$. Our main tool involves the facial reduction of SDP.
Keywords: semidefinite optimization, sensitivity analysis, degeneracy, strong duality
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Citation: Department of Combinatorics and Optimization, University of Waterloo, 200 University Ave W, Waterloo, ON N2L3G1, Canada, June 2014.
Entry Submitted: 06/30/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|