Why would this Semidefinite Program be Dual Infeasible?

Question

My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is positive semidefinite. I see no way that this program would be infeasible, because just setting every variable to 0 would satisfy all the constraints.

I have written the semidefinite program according to SPDA format. In this format, my SDP is the dual program. When I solve it with the software csdp, it tells me that the "dual program is infeasible."

Here is the particular SDP:

2
1
11
0.0 0.0
0 1 1 10 1.0
1 1 1 10 .25
1 1 3 10 .25
1 1 6 10 -.25
1 1 8 10 -.25
1 1 9 10 -.5
2 1 2 11 -3.0
2 1 3 11 -4.0
2 1 4 11 1.0
2 1 5 11 1.0
2 1 6 11 -4.0
2 1 7 11 3.0
2 1 9 11 1.0

csdp outputs This is a pure dual feasibility problem. Iter: 0 Ap: 0.00e+000 Pobj: 0.0000000e+000 Ad: 0.00e+000 Dobj: 0.0000000e+000 Iter: 1 Ap: 1.00e+000 Pobj: 5.6521881e+000 Ad: 9.00e-001 Dobj: 0.0000000e+000 Declaring dual infeasibility. Success: SDP is dual infeasible Certificate of dual infeasibility: tr(CX)=1.00000e+000, ||A(X)||=1.38778e-017 `

Answer 1

The original poster seems to misunderstand the distinction between "primal infeasible" and "dual infeasible."

The output from CSDP shows that the problem is primal feasible ($X=0$ is a primal feasible solution) but that the primal problem is unbounded. By weak duality, the corresponding dual problem is infeasible.

If you just want a primal feasible solution and don't care about the primal objective value, then you can get this in a couple of ways:

1. You can use the "certificate" returned by CSDP. This is a matrix $X$ such that $X$ is positive semidefinite and $A(X)=0$. Any positive multiple of this matrix is a primal feasible solution to your SDP.

2. You can add an additional constraint that causes the objective function to be bounded. A simple choice would be trace(X)=100.

By the way, it's easy to confirm this using another SDP solver such as SeDuMi or SDPT3 or SDPA.