I am not sure how to solve error Invalid constraint: {convex} >= {real affine}


(damonsun) #1

Hi guys:
I want to find the optimal complex vector a(4,1) in the following case:
cvx_begin
variable d;
variable a(4,1) complex;

  maximize (d);
  subject to 
  sum_square_abs(a)>=d;
  sum_square_abs(a)<=4;

cvx_end

but I will get error:
Disciplined convex programming error:
Invalid constraint: {convex} >= {real affine}

is any modificiation I can make to avoid it?
Thank you!


(Mark L. Stone) #2

That is a non-convex constraint.

But isn’t your model equivalent to

cvx_begin
variable d;
maximize (d);
subject to 
d<=4;
cvx_end

which has optimal solution d=4? Unless you have removed some portions of your problem in order to simplify the exposition.


(damonsun) #3

Thank you for the quick reply. Yes.I have removed some parts here.
The complete question is:

maximize d
subject to
trace(C*X)>=d
trace(X)<=4

with the additional condition that X is a positive semidefinite matrix and X=aa’. a is a 41 complex vector. As I know that aa’ is not allowed in cvx, and trace(aa’)=sum_square_abs(a). I change the original question into the one shown above. By the way, C is a 4*4 complex matrix(diagonal elements have 0 imaginary part). Is there anything I can do here?


(Mark L. Stone) #4

I’m confused as to what problem you are trying to solve, and how a comes into play.

If you wish to keep this convex, perhaps the best you can do is a convex relaxation [X a';a 1] == hermitian_semidefinite(n+1) rather than X==a*a' , and enter the constraints you have above

trace(C*X)>=d
trace(X)<=4

(damonsun) #5

Oh. I really thank you for your help! I will try to fix it.


(damonsun) #6

By the way, I checked ‘Semidefinite programming mode’ of cvx users’ guide for the last hour. I have no idea why it should be ‘n+1’ instead of ‘n’ for hermitian_semidefinite . Also, I get an error
’Error using reshape
To RESHAPE the number of elements must not change.’ which I never met before. Do you have any ideas?


(Mark L. Stone) #7

In your case, that would be [X a’;a 1] == hermitian_semidefinite(5) . I was implicitly referring to n as being the dimension of X - sorry for confusing you on that.

After that, let me know if you’re still having a reshape error, in which case you should show your complete code for context.


(damonsun) #8

I am sorry that the error still exists (I tried n=5 and also n=4). The whole code is the following:

c=[0.5836 0.2749+0.2644j 0 0;0.2749-0.2644j 1.4384 0 0;0 0 0 0;0 0 0 0];
cvx_begin
variable d;
variable X(4,4) complex hermitian;
variable a(4,1) complex;
[X a’;a 1] == hermitian_semidefinite(5);

  maximize (d);
  subject to
  real(trace(c*X))>=d;
  trace(X)<=4;

cvx_end


(Mark L. Stone) #9

Sorry. That was a typo by me. Should be [X a;a' 1] == hermitian_semidefinite(5) . Believe it or not, I had it correct, posted it, re-read it, decided somehow it was wrong, and quickly edited to the wrong thing.

It doesn’t matter to CVX, but for program consistency, this should be part of the subject to block. But it doesn’t matter because the subject to statement s ignored by CVX, and any CVX constraint is treated is such in whatever order it occurs.

Unfortunately for you. the optimal X is not equal to a*a'. So all you have achieved with this convex relaxation formulation is an upper bound on the true optimal objective. The optimal objective value of the convex relaxation, which winds up being 6.3354, is therefore an upper bound on the optimal objective of your original problem. If that is not adequate for your purposes, I leave any further approaches to benefit from a convex solver to you. Otherwise you may have to deal with this a a non-convex SDP using another solver, such as perhaps PENLAB, which will take you beyond this forum’s scope.


(damonsun) #10

I really appreciate for your patient explanation.It does help me a lot! Unfortunately, the value of ‘a’ which can give me the maximum ‘d’ is the most important thing in my project. Is there any method that I can get ‘a’ which will give the maximum ‘d’ even I will not know what is the value of d. To make it more clear, I only need to know what ‘a’ will give me the maximum value, the value of d is in fact not that vital. If there is no way, I will try to have a look at PENLAB.
Thank you!


(Mark L. Stone) #11

I don’t know a way. That doesn’t mean no one else does.


(damonsun) #12

thank you all the same!


(damonsun) #13

Oh, one final question is: you said the optimal X is not equal to a*a’, but is the X shown in the result the one which will give the maximum d? If so, I may try a method to decompose the matrix to find a.


(Mark L. Stone) #14

The solution to the convex relaxation does not necessarily provide the optimal d. It may be too optimistic (high).

To get a usable solution from the convex relaxation, you need X to be rank 1, i.e., of the form a*a’. The optimal X I got for the convex relaxation has rank 4 i.e., full (rank). The convex relaxation omits the non-convex rank constraint and then prays it will be satisfied anyway. The prayer didn’t come true in this case.


(damonsun) #15

Yes.That is the problem. By the way, rank constraint is not convex so is not allowed in cvx. I may need to think about another way. Thank you !


(damonsun) #16

Hi. I have found a way to get ‘a’ from ‘X’. (I can use randomization follows N~(0,X) ). However, I feel confused that, although I have defined X to be hermitian(complex) and semidefinite, the X found by cvx is the following:


you can see that elements which are not in the diagonal are quite small. Do you have any ideas about what is the cause of that?
my code is the following:

cvx_begin
variable dd;
variable X(4,4) hermitian semidefinite;

  maximize (dd);
  subject to
     for i=1:60
        real(trace(C(:,:,i)*X))>=dd;
     end
     real(trace(s1*X))*2>=dd;
     real(trace(s2*X))*2>=dd;
     real(trace(s3*X))*2>=dd;
     real(trace(s4*X))*2>=dd;
     trace(X)<=4;
  
cvx_end

C(:,:,i) , s1,s2,s3,s4 are all 4*4 complex matrixes.


(Mark L. Stone) #17

I have no idea what your way to get a from X is. What are you doing with randomization? Are you drawing a from a 4D Normal with mean 0 and covariance X? If so, I have no idea why that makes any sense.

I don’t see any relation between X and a in your new code. Your matrix X is within tolerance of being a real diagonal positive definite matrix; in any event, it is within tolerance of being hermitian semidefinite, if not exactly so.


(damonsun) #18

In the new approach, I will find ‘a’ without cvx. All I need is ‘X’. The method is shown in the paper"semidefinite relaxation of quadratic optimization problems" which is a very good paper for this problem. I believe you will be interested in it. The paper gives two methods, ‘randomization’ is the second method proposed. As it is complicated, forgive me not explain it in detail here. What I want to do here is trying to get ‘X’ which is similar to


where I can have a much reasonable value for all elements. I do not know if it is possible.


(Mark L. Stone) #19

At this point, I think you’ve exhausted the forum’s help. If you need further assistance, you could consider contacting the paper authors. Good luck.