World's most popular travel blog for travel bloggers.

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

, ,
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` `

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