Strong Duality for Semidefinite Programming

Motakuri Ramana, Henry Wolkowicz, and Levent Tuncel

It is well known that the duality theory for linear programming (LP) is powerful and elegant and lies behind algorithms such as simplex and interior-point methods. However, the standard Lagrangian for nonlinear programs requires constraint qualifications to avoid duality gaps.

Semidefinite linear programming (SDP) is a generalization of LP where the non-negativity constraints are replaced by a semidefiniteness constraint on the matrix variables. There are many applications, e.g. in systems and control theory and in combinatorial optimization. However, the Lagrangian dual for SDP can have a duality gap. We discuss the relationships among various duals and give a unified treatment for strong duality in semidefinite programming. These duals guarantee strong duality, i.e. a zero duality gap and dual attainment. This paper is motivated by the recent paper by Ramana where one of these duals is introduced.

CORR 95-12, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, June 1995.

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]