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.
Citation
Department of Combinatorics and Optimization, University of Waterloo, 200 University Ave W, Waterloo, ON N2L3G1, Canada, June 2014.