An exact duality theory for semidefinite programming and its complexity implications |
| |
Authors: | Motakuri V Ramana |
| |
Institution: | (1) Center for Applied Optimization, 303 Weil Hall, Department of Industrial and Systems Engineering, University of Florida, 32608 Gainesville, FL, USA |
| |
Abstract: | In this paper, an exact dual is derived for Semidefinite Programming (SDP), for which strong duality properties hold without
any regularity assumptions. Its main features are: (i) The new dual is an explicit semidefinite program with polynomially
many variables and polynomial size coefficient bitlengths. (ii) If the primal is feasible, then it is bounded if and only
if the dual is feasible. (iii) When the primal is feasible and bounded, then its optimum value equals that of the dual, or
in other words, there is no duality gap. Further, the dual attains this common optimum value. (iv) It yields a precise theorem
of the alternative for semidefinite inequality systems, i.e. a characterization of theinfeasibility of a semidefinite inequality in terms of thefeasibility of another polynomial size semidefinite inequality.
The standard duality for linear programming satisfies all of the above features, but no such explicit gap-free dual program
of polynomial size was previously known for SDP, without Slater-like conditions being assumed. The dual is then applied to
derive certain complexity results for SDP. The decision problem of Semidefinite Feasibility (SDFP), which asks to determine
if a given semidefinite inequality system is feasible, is the central problem of interest, he complexity of SDFP is unknown,
but we show the following: (i) In the Turing machine model, the membership or nonmembership of SDFP in NP and Co-NP is simultaneous;
hence SDFP is not NP-Complete unless NP=Co-NP. (ii) In the real number model of Blum, Shub and Smale, SDFP is in NP∩CoNP. |
| |
Keywords: | Semidefinite programming Strong duality Complexity classes Theorems of the alternative |
本文献已被 SpringerLink 等数据库收录! |
|