3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ So because semidefinite programming is conic programming also, then we consider a PSD matrix as a vector of $n^2$ element? because we should have a cone( it means a subset of $\mathbb R^n$ which is a cone). $\endgroup$
    – GhD
    Commented May 8, 2018 at 22:04
  • $\begingroup$ @GhD the (real) semidefinite cone is isomorphic with a vector with $n(n+1)/2$ elements. As Brian correctly said, you can store it with $n^2$ elements, but there is redundancy there due to symmetry, and you need to be careful to take that into account. $\endgroup$ Commented May 8, 2018 at 23:23
  • $\begingroup$ Really useful answer, thanks a lot. If I may ask, in cases where the solution is given by a singular matrix, is it still possible for the Slater condition to be satisfied? For instance, by definining $X = \frac{1}{d} (X_1 + .. + X_d) \in\mathcal{S}^{d}$ where each $X_i$ is a feasible rank-1 matrix, then if we are able to achieve a non-singular matrix I believe that we would be satisfying part of the Slater condition. $\endgroup$
    – Javier TG
    Commented Jan 5 at 23:38
  • 1
    $\begingroup$ It's certainly possible for the Slater condition to be satisfied but the optimal solution (or all optimal solutions) is (are) singular. $\endgroup$ Commented Jan 5 at 23:58
  • $\begingroup$ Thank you for your response. $\endgroup$
    – Javier TG
    Commented Jan 6 at 11:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .