DIMACS TR: 95-02
An Exact Duality Theory for Semidefinite Programming and it's
Complexity Implications
Author: Motakuri Ramana
ABSTRACT
In this paper, we present a new and more complete duality for
Semidefinite Programming (SDP), with the following features:
\begin{itemize}
\item This dual is an explicit semidefinite program, whose number of
variables and the coefficient bitlengths are polynomial in those of
the primal.
\item If the Primal is feasible, then it is bounded if and only if the
dual is feasible.
\item The duality gap, \ie the difference between the primal and the
dual objective function values, is zero whenever the primal is
feasible and bounded. Also, in this case, the dual attains its
optimum
\item It yields a precise Farkas Lemma for semidefinite feasibility
systems, \ie characterization of the {\it infeasibility} of a
semidefinite inequality in terms of the {\it feasibility} of another
polynomial size semidefinite inequality.
\end{itemize}
Note that the standard duality for Linear Programming satisfies all of
the above features, but no such duality theory was previously known
for SDP, without Slater-like conditions being assumed.
Then we apply the dual to derive certain complexity results for
Semidefinite Programming Problems. The decision problem of
Semidefinite Feasibility (SDFP), \ie that of determining if a given
semidefinite inequality system is feasible, is the central problem of
interest. The complexity of SDFP is unknown, but we show the
following: 1) In the Turing machine model, SDFP is not NP-Complete
unless NP=Co-NP; 2) In the real number model of Blum, Shub and
Smale\cite{bss}, SDFP is in NP$\cap$Co-NP. We then give polynomial
reductions from the following problems to SDFP: 1) Checking whether an
SDP is bounded; 2) Checking whether a feasible and bounded SDP attains
the optimum; 3) Checking the optimality of a feasible solution.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-02.ps.gz
DIMACS Home Page