- Sensitivity analysis of semidefinite programs without strong duality Yuen-Lam Cheung(yl2cheunuwaterloo.ca) Henry Wolkowicz(hwolkowiczuwaterloo.ca) 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. Download: [PDF]Entry Submitted: 06/30/2014Entry Accepted: 06/30/2014Entry Last Modified: 06/30/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.