Prof. S. Boyd example failed

1

I tried next example on semidefinite programs from the Stanford course “EE363 Review Session 4: Linear Matrix Inequalities” from Professor Boyd about optimal diagonal scaling.

=============================================
% Some square matrix
M=[-1,-1;3,3];
%
[n,m]=size(M);
%
cvx_begin sdp
variable E(n,n) diagonal
variable gam
M’ * E * M >= gam^2*E
E >= eye(n)
cvx_end

The code failed and I get next error message;

Error using .* (line 173)
Disciplined convex programming error:
Cannot perform the operation: {convex} .* {real affine}

Error in * (line 36)
z = feval( oper, x, y );

Error in example_scaling_EE363_Review_Session_4 (line 8)
M’EM >= gam^2*E

Can anybody help me to rewrite the code properly, please?

2

Sorry, this is the script;
%===============================
% Some square matrix
M=[-1,-1;3,3];
%
[n,m]=size(M);
%
cvx_begin sdp
variable E(n,n) diagonal
variable gam
M’EM >= gam^2*E
E >= eye(n)
cvx_end
%
%=================================

3

In the course example https://stanford.edu/class/ee363/sessions/s4notes.pdf , gam is assigned a value in MATLAB prior to invocation of CVX. It is not a CVX variable. As you have written it, it is a non-convex Bilinear Matrix Inequality (BMI), not an LMI.

If you remove the statement variable gam , the program will become an LMI and execute without error message. Note that the course example has the inequality in the other direction.

4

True Mark, thank you very much, now I understand.
You’re right, I had mistaken the sense of inequality.
It occurs to me that to minimize the variable ‘gam’, I could create an iterative loop, where the value of ‘gam’ would decrease until reaching an accuracy set a priori, is that how gam is optimized?

5

If you want to find the minimum value of gam for which the problem is feasible, you can find a value gam_initial for which the problem is feasible. and try successively smaller values of gam until the problem is infeasible, or use bisection, starting with the interval [0,gam_initial] to systematically search for that minimum value. You can do this by calling CVX inside an iterative loop.

6

Thanks, Mark, I have tried your first approach, starting with a realizable value of ‘gam’ and decreasing the value successively until the problem is unrealizable, finding the minimum value.

One last question and do not bother anymore, I explain;
I have tried to do the same problem, without iterative loop, trying to transform the inequalities constraints, so that CVX can minimize ‘gam’ without loop interaction, I have tried this from two different approaches;

  1. The first approach is to rewrite the inequalities in a scalar way, in this way;

%======================================================================
clear;
%
M=[-1,-1;3,3];
%
cvx_begin sdp
variables ro d1 d2
%
minimize ro
% scalar afine constrains
d1*M(1,1)^2 + d2*M(2,1)^2 <= d1*ro; d1*M(1,1)*M(1,2) + d2*M(2,1)*M(2,2) <= 0; d1*M(1,1)*M(1,2) + d2*M(2,1)*M(2,2) <= 0; d1*M(1,2)^2 + d2*M(2,2)^2 <= d2*ro;
cvx_end
%
E=[d1 0; 0 d2];
gam = sqrt(ro); % %=================================================================

Unfortunately, this does not work, since I can not avoid using the square and you get the following error,

Error using .* (line 262) Disciplined convex programming error: Invalid quadratic form(s): not a square.

Error in * (line 36) z = feval( oper, x, y );

Error in example_scaling_EE363_Review_Session_4 (line 140) d1*M(1,1)^2 + d2*M(2,1)^2 <= d1*ro;

Is there any way to implement the problem from this approach, either scalar or vectorial, without disobeying DCP ruleset?

  1. And the second approach is to rewrite the inequalities in the form of LMI, but here I also have problems, I explain,

First, through Schur’s complement, I rewrite the inequalities in LMI form preserving symmetry in this way,
[-E^-1, M; M', -gam^2*E] <= 0; E > 0;

But in fact, this is a BMI due to the term (-gam ^ 2 * E) and also the inverse of a matrix contradicts DCP ruleset.
Next to eliminate the inverse operation of a matrix, pre and post-multiplying by diag(eye(n),E^-1) we obtain,

[-E^-1, M*E^-1; E^-1*M', -E^-1*gam^2] <= 0;

and with a change of variable W = E^-1, we have,

[-W, M*W; W*M', -W*gam^2] <= 0;

Now the inverse operation is not there, but it is still a BMI, the question is, is there any way to transform the original inequality into LMI and solve it with CVX?
Thank you very much for everything beforehand.
Best regards.

7

I don’t see how. If someone else does, please post.