patternMinor
Why would this Semidefinite Program be Dual Infeasible?
Viewed 0 times
thiswhysemidefiniteprogramwoulddualinfeasible
Problem
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:
csdp outputs
`
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.0csdp 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`
Solution
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:
-
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.
-
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.
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:
-
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.
-
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.
Context
StackExchange Computer Science Q#33478, answer score: 7
Revisions (0)
No revisions yet.