1
$\begingroup$

I am trying to plot the feasible region of a rank constrained semidefinite program shown below:

Rank Constrained SDP

The Mathematica code that I am using is the following:

FeasibleRegionRanksdp =
  RegionPlot[
    Tr[{{0.09, 0}, {0, 7}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
    Tr[{{7, 0}, {0, 0.09}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
    Tr[{{1.05, -0.95}, {-0.95, 1.05}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
    Tr[{{1.05, 0.95}, {0.95, 1.05}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
    MatrixRank[{{x1^2, x1*x2}, {x1*x2, x2^2}}, Tolerance -> 0] ==1 && 
    Min[Eigenvalues[{{x1^2, x1*x2}, {x1*x2, x2^2}}]] >= 0,
    {x1, -0.5, 0.5}, {x2, -0.5, 0.5}]

The result that I am obtaining is the following non-convex region:

Rank Constrained SDP Feasible Region

My questions is:

1) Is the rank constraint imposed correctly in Mathematica?

2) Is the positive semidefiniteness constraint also correct in the code?

based on my understanding, the rank constraint is the only non-convex constraint and so the region should be non convex. But once I remove the rank constraint, the non convexity should be removed and the region should be convex which is not the case as could be checked by removing the rank constraint and plotting.

I would really appreciate any help with this.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Consider pre-evaluating your region descriptor conditions:

regiondescriptor = 
 Tr[{{0.09, 0}, {0, 7}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
 Tr[{{7, 0}, {0, 0.09}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 && 
 Tr[{{1.05, -0.95}, {-0.95, 1.05}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 &&
 Tr[{{1.05, 0.95}, {0.95, 1.05}}.{{x1^2, x1*x2}, {x1*x2, x2^2}}] <= 1 &&
 MatrixRank[{{x1^2, x1*x2}, {x1*x2, x2^2}}, Tolerance -> 0] == 1 && 
 Min[Eigenvalues[{{x1^2, x1*x2}, {x1*x2, x2^2}}]] >= 0

(* Out: 0.09 x1^2 + 7 x2^2 <= 1 && 
        7 x1^2 + 0.09 x2^2 <= 1 && 
        1.05 x1^2 - 1.9 x1 x2 + 1.05 x2^2 <= 1 && 
        1.05 x1^2 + 1.9 x1 x2 + 1.05 x2^2 <= 1 && 
        Min[0, x1^2 + x2^2] >= 0 *)

Then use the evaluated version in RegionPlot: 

RegionPlot[regiondescriptor, {x1, -0.5, 0.5}, {x2, -0.5, 0.5}]

Mathematica graphics

I cannot guarantee that this is a correct representation of your problem, since your problem is presented in a symbolic form that I do not completely understand, so I will leave it to you or others to determine whether this is an appropriate answer to your problem. Perhaps you could reformulate the problem in a less terse form.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks a lot for your reply. Based on the output from the regiondescriptor (included as a comment), it seems that the MatrixRank is not being evaluated since it is not showing up in the output. Maybe the problem is in the rank constraint. $\endgroup$
    – Abdulrahman Kalbat
    Commented Jun 29, 2016 at 18:33
  • $\begingroup$ @AbdulrahmanKalbat The MatrixRank is actually being evaluated, but it identically evaluates to True no matter the values of x1 and x2 (check MatrixRank[{{x1^2, x1*x2}, {x1*x2, x2^2}}, Tolerance -> 0] == 1, or Det[{{x1^2, x1*x2}, {x1*x2, x2^2}}], which is zero), so it is simplified out of the logical expression. $\endgroup$
    – MarcoB
    Commented Jun 29, 2016 at 19:46
  • $\begingroup$ you are right. The formulation is not correct and the rank will always be equal to one. Instead of the rank constraint and the positive semidefinitness contraints, I could replace them by introducing a new matrix variable X that is defined as follows: X = x * x^T where the vector x=[x1 x2]. After defining this matrix variable, all other constraints should defined in terms of this matrix variable. New code is following but not working: $\endgroup$
    – Abdulrahman Kalbat
    Commented Jun 29, 2016 at 21:51
  • $\begingroup$ regiondescriptor = Tr[{{0.09, 0}, {0, 7}}.X] <= 1 && Tr[{{7, 0}, {0, 0.09}}.X] <= 1 && Tr[{{1.05, -0.95}, {-0.95, 1.05}}.X] <= 1 && Tr[{{1.05, 0.95}, {0.95, 1.05}}.X] <= 1 && X == Transpose[{x1, x2}].{x1, x2} RegionPlot[regiondescriptor, {x1, -10, 10}, {x2, -10, 10}, BoundaryStyle -> Black] $\endgroup$
    – Abdulrahman Kalbat
    Commented Jun 29, 2016 at 21:51
  • $\begingroup$ @AbdulrahmanKalbat Mathematica does not distinguish between row and column vectors, so start by defining X = {x1, x2}.{x1, x2} instead, then use that in your regiondescriptor. I am still confused though: what did you think the explicit form of X would be in your code? X seems to be defined as the scalar x1^2 + x2^2. $\endgroup$
    – MarcoB
    Commented Jun 29, 2016 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.