Exact duality for optimization over symmetric cones

Imre Pólik (imre.polikgmail.com)
Tamás Terlaky (terlakymcmaster.ca)

Abstract: 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.

Keywords: Ramana-dual, symmetric cone optimization, exact duality, minimal cone, homogeneous cones

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

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

Download: [PDF]

Entry Submitted: 08/17/2007
Entry Accepted: 08/17/2007
Entry Last Modified: 08/22/2007

Modify/Update this entry