An exact duality theory for semidefinite programming and its complexity implications
Ramana, Motakuri V.

Data: 1997
Resum: 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 the infeasibility of a semidefinite inequality in terms of the feasibility 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 NPBigCo-NP. .
Drets: Tots els drets reservats
Llengua: Anglès
Document: article ; recerca ; Versió publicada
Matèria: Semidefinite programming ; Strong duality ; Complexity classes ; Theorems of the alternative
Publicat a: Mathematical Programming, vol. 77 n. 2 (1997) p. 129-162, ISSN 0025-5610

34 p, 1.4 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2021-06-27

   Favorit i Compartir