Abnormal result of lambda_max function


#1

Hi everyone, I met a very bizarre situation when I use lambda_max function. It seems that the result of lambda_max is totally different from the result of max(eig()). The code I used is as following

A1 = [-10 2;1 -14];
A2 = [-8 1;3 -20];

cvx_begin sdp 
cvx_precision high
variable P(2,2) symmetric
P*A1+A1'*P <= -1e-3*eye(2,2)
P*A2+A2'*P <= -1e-3*eye(2,2)
P >= 1e-3*eye(2,2)
beta = max([lambda_max(P*A1 + A1'*P)  lambda_max(P*A2+A2'*P)])
cvx_end

disp(beta);
disp( max([max(eig(P*A1 + A1'*P))  max(eig(P*A2 + A2'*P))]) );

I have tried all the solvers I have, which are SDPT2, SeDuMi, Mosek and Mosek_2. All the results seem abnormal, which means that “lambda_max” get a different result from “max(eig())”.

The two results I get by using Mosek_2 solver are

-0.181116022322137
-0.600782145203803

Thanks for any help in advance!


The return value in the process of cvx is Incorrect
(Mark L. Stone) #2

lambda_max(matrix) = max(eig(matrix)) as advertised in the documentation and help for lambda_max. You will see this if you move the statement
beta = max([lambda_max(P*A1 + A1'*P) lambda_max(P*A2+A2'*P)])
to after cvx_end. When you do that, the “discrepancy” you described will go away, because the same value of P, i.e., the value returned by CVX, will be used in both cases.

In your program, beta is a CVX expression, which depends on the CVX variable P. I don’t know what value of P is used to evaluate the expression, beta, when the program is executed (it appears to be undocumented behavior, as it is something you shouldn’t be doing), but it winds up not being the “optimal” P returned by CVX, meaning in your case because there is no objective function, whatever feasible value of P is returned by the solver/CVX.

Or to put it more clearly, the value of a CVX expression after CVX has completed, appears to be undocumented behavior. And the value of that expression after CVX has completed is not necessarily the same as the value of that expression when evaluated using the values of CVX variables returned by CVX. Perhaps that could be made clearer in the CVX User’s Guide. But the Users’ Guide does state “An expression object, on the other hand, is initialized to zero, and should be thought of as a temporary place to store CVX expressions; it can be assigned to, freely re-assigned, and overwritten in a CVX specification.”


Optimal value (cvx_optval) cvx obtained is not the same as the result obtained by the optimal solution
(Michael C. Grant) #3

Mark is right. CVX isn’t designed to compute arbitrary additional expressions that don’t have anything to do with the model. Its only purpose is to solve the optimization model. Just re-do the computation you want after the model is complete.


(Michael C. Grant) #4

In other words, move your beta expression to after cvx_end.


#5

Hi Mark, thank you for your detailed and timely reply. I am not sure if I understand you correctly and here is my understanding. What you mean is > beta = max([lambda_max(P*A1 + A1’P) lambda_max(PA2+A2’*P)])
is an undocumented statement, and it is not clear what P is used to evaluate this statement because this statement is not put after cvx_end.

So I try to change my code, make the statement documented and have the following new example

A1 = [-10 2;1 -14];
A2 = [-8 1;3 -20];

cvx_begin sdp
cvx_precision high
variable P(2,2) symmetric
PA1 + A1’P <= -1e-3eye(2,2)
P
A2 + A2’P <= -1e-3eye(2,2)
P >= 1e-3eye(2,2)
beta_1 = max( [lambda_max(-1
(PA1 + A1’P)) lambda_max(-1(PA2+A2’P))] )
alpha_1 = min( [lambda_min(-1
(PA1 + A1’P)) lambda_min(-1(PA2+A2’P))] )
beta_1 - 100
alpha_1 <= 0
cvx_end

beta_2 = max([lambda_max(-1*(PA1 + A1’P)) lambda_max(-1(PA2+A2’P))]);
alpha_2 = min([lambda_min(-1
(PA1 + A1’P)) lambda_min(-1(PA2+A2’*P))]);

disp(beta_1 - 100alpha_1);
disp(beta_2 - 100
alpha_2);

In this new example, beta_1 and alpha_1 are variables used for optimization constraints, so I think they are documented. However, beta_1 is not equal beta_2, and alpha_1 is not equal to alpha_2, which means the optimal P is not used to evaluate beta_1 and alpha_1.

Perhaps some intermediate P is used to evaluate beta_1 and alpha_1, which is not a problem. What I am not sure about is if the optimal P satisfies the constraint when the values of beta_1 and alpha_1 are not corresponding to the optimal P.

Thank you again for your patient reply.


#6

Hi Michael, thank you for further explanation. I think I understand your point. I changed my code and made the undocumented statement be part of the model. The code is in my reply to Mark’s post.

However, it seems that some intermediate P instead of optimal P is used to evaluated beta_1 and alpha_1. What worries me is how can I be confident about the result if the final values of beta_1 and alpha_1 are not corresponding to the optimal value? I can verify if the optimal P satisfies the constraints after the optimization is finished, which however will require much more computation time if the project involves solving a sequences of optimization problems.

Thanks again for you help!!


(Mark L. Stone) #7

In your latest program, beta_1 and alpha_1 are (CVX) expressions which are used in a CVX constraint. Presuming an optimal solution is returned, as indicated by the solver and CVX, the constraint will be satisfied within solver tolerance at the optimal values of CVX variables returned by CVX… That is what happens in this case.

You should not rely on the numerical values of any expressions after CVX executes; however, if they are used in the objective function and/or constraints, they will be used properly in formulating and solving the optimization problem. When CVX execution ends with an optimal solution, the optimal values of the CVX variables will be in those variables, available to you in your MATLAB session. However, you can not rely on CVX expressions available in your MATLAB session after CVX execution being based on optimal values of CVX variables. Therefore, if you want their “optimal” values, you need to evaluate them in MATLAB after CVX execution ends, as you have done with beta_2 and alpha_2.

Regarding your question to Michael, yes you can be confident, presuming CVX reports an optimal solution was found. the only exception would be if your problem has some terrible numerical properties, or there is a solver or CVX bug. CVX and the solvers I tried appear to be correctly solving your problem.


(Michael C. Grant) #8

I’m really not sure what to tell you. Either you trust CVX to do with it is designed to do, or you don’t. And what it is not designed to do is to accurately maintain the optimal values of intermediate expressions that are not involved in the optimization process. The beta expression is used nowhere in the optimization model itself, so frankly what CVX does with it is undefined.


#9

Thanks Mark for your patient replay. I just wanna double check and make sure the CVX expressions are based on the intermediate values of the optimal variables. Thanks again for your support and answer.


(Mark L. Stone) #10

CVX expressions used in objective function or constraints are used correctly by CVX and the solver. You should not use their values outside CVX unless you reevaluate them using the optimal values of the CVX variables.


#11

Hi Michael, like what I told Mark, I just wanna make sure that the CVX expressions are based on the intermediate values and it does not imply that the optimal value does not satisfy the constraints. I have no attention of offending you and CVX. CVX is truly a great tool, and I really appreciate it! Now my doubts are resolved. Thanks again for your help.


#12

Got it. thank you!! :grin:


(Michael C. Grant) #13

Fair enough, liki. Sorry to come off harsher than I should. But I would go further and say that you should not depend on the individual expressions inside CVX evaluating to what you think they should, even if they are actively involved in constraints. The reasons for this are technical in nature. You should always recompute the quantities you are interested in from the numeric values of the variables.


#14

Thanks Michael for your advice. Appreciate it!