Optimization Online


Sensitivity analysis of semidefinite programs without strong duality

Yuen-Lam Cheung(yl2cheun***at***uwaterloo.ca)
Henry Wolkowicz(hwolkowicz***at***uwaterloo.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/2014
Entry Accepted: 06/30/2014
Entry Last Modified: 06/30/2014

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 Optimization Society