In semidefinite programming what is the cone and what does interior for strong duality mean?

258 Views Asked by At

In conic programming we should have a cone that is a subset of $\mathbb R^n$; then strong duality holds if this conic program has a strictly feasible solution, i.e., the primal should have a feasible solution which is an interior point of the cone.

We know that semidefinite programming is a type of conic programming. My doubts are:

  • What exactly does strictly feasible solution mean? If the primal has a strictly feasible solution then it means the dual also has a feasible solution and then their optimum values are equal?

  • Also how do we consider a semidefinite program as a conic program? Does it means that we should take positive semidefinite matrices of order $n$ as vectors with $n^2$ elements?

I will appreciate it if you clarify these thing for me.

1

There are 1 best solutions below

5
On

Here, strictly feasible means that the matrix $X$ is positive definite (not just positive semidefinite) and that $X$ satisfies the linear equality constraints $A(X)=b$.

It's quite common to have SDP's that don't satisfy this Slater condition. In this case, the SDP might be feasible, but the only matrices that satisfy $A(X)=b$ and are positive semidefinite happen to be singular matrices.

If an SDP is primal feasible and satisfies the Slater condition and the SDP is not unbounded, then the dual SDP will have an optimal solution with the same optimal objective value as the primal SDP.

The set of symmetric and positive semidefinite matrices is a self-dual cone with respect to the trace inner product. Although some software chooses to store $X$ as an $n^2$ element long vector, that's not generally the best way to handle the theory.