Exact duality for optimization over symmetric cones

We present a strong duality theory for optimization problems over symmetric cones without assuming any constraint qualification. We show important complexity implications of the result to semidefinite and second order conic optimization. The result is an application of Borwein and Wolkowicz's facial reduction procedure to express the minimal cone. We use Pataki's simplified analysis and provide an explicit formulation for the minimal cone of a symmetric cone optimization problem. In the special case of semidefinite optimization our dual has better complexity than Ramana's strong semidefinite dual. We also specialize the dual for second order cone optimization and argue that new software for homogeneous cone optimization problems should be developed.


AdvOL Report 2007/10, Advanced Optimization Lab, McMaster University, Hamilon, ON, Canada, August 2007



View Exact duality for optimization over symmetric cones