World's most popular travel blog for travel bloggers.

[Solved]: Why would this Semidefinite Program be Dual Infeasible?

, , No Comments
Problem Detail: 

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 `

Asked By : Mark

Answered By : Brian Borchers

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33478

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback