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.

$\endgroup$
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.

$\endgroup$
  • $\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 Jun 29 '16 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 Jun 29 '16 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 Jun 29 '16 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 Jun 29 '16 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 Jun 29 '16 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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