Optimization Online


Generating and Measuring Instances of Hard Semidefinite Programs, SDP

Hua Wei (h3wei***at***uwaterloo.ca)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

Abstract: Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g Slater's condition (strict feasibility) holds. And, there exist SDP problems which have a zero duality gap but no strict complementary primal-dual optimal solution. We refer to these problems as hard instances of SDP. In this paper, we introduce a procedure for generating hard instances of SDP. We then introduce two measures of hardness and illustrate empirically that these measures correlate well with the size of the gap in strict complementarity as well as with the asymptotic local convergence rate, and also with the number of iterations required to obtain optimal solutions to a specified accuracy. In addition, our numerical tests show that no correlation exists between the complementarity gaps and recently introduced geometrical measures or with Renegar's condition number. We include tests on the SDPLIB problem set.

Keywords: Semidefinite Programming, Strict Complementarity, Primal-Dual Interior-Point Methods

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Department of Combinatorics & Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada Research Report CORR 2006-01

Download: [Postscript][PDF]

Entry Submitted: 01/23/2006
Entry Accepted: 01/23/2006
Entry Last Modified: 01/23/2006

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