##
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.