Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana's dual has the following remarkable features:
i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the primal, so there is no duality gap. iii) it attains its optimal value when it is finite iv) it yields a number of complexity results in SDP, which are fundamental, and to date are still the best known. For example,
it proves that SDP feasibility in the Turing model is not NP-complete, unless NP = co-NP.
In this work we extend and simplify previous analyses of Ramana's dual.
First, we completely characterize the feasible set of Ramana's dual for inequality constrained SDPs.
Second, we similarly analyze Ramana's dual for equality constrained SDPs. We do this
by connecting it to a seemingly very different way of inducing strong duality:
reformulating the SDP using elementary row operations inherited from Gaussian eliminination.
Our characterizations yield a short and transparent derivation of Ramana's dual.
Our approach is combinatorial in the following sense: i) we use a minimum amount of continuous optimization theory ii)
we show that feasible solutions in Ramana's dual are identified with regular facial reduction sequences, i.e., essentially discrete structures.
Article
View A combinatorial approach to Ramana's exact dual for semidefinite programming