A question about soving maximum eigenvalue of symatic matrix without lambda_max?


(Li Xin) #1

Hi, I’m a new user of CVX.

Recently, I wanted to solve the maximum eigenvalue of a symatric matrix X. I know there is a function called lambda_max in CVX that I could use to solve this problem directly. However, I want to program it without this m file, but I failed.

Here is my program:

X = [3,0;0,1];
cvx_begin
variable y(2);
variable t
minimize t
subject to
max(y’ * X * y) <= t
norm(y,2) <= 1
cvx_end

I kindly hope y would be [1,0]’; but actually, after optimization y is around [0,0]’; I don’t know why.

Could you help me to explain it? Sincerely thank you for your help!


(Mark L. Stone) #2

I won’t tell you how to compute the max eigenvalue as the solution of an optimization problem… Of course, you could use MATLAB’s eig or eigs to compute the maximum value of an input matrix, such as X.

However, I will tell you that (within numerical tolerance(), CVX is reporting the correct solution of the problem you specified, namely optimal t = 0, y=[0;0].

Your constraint
max(y' * X * y) <= t
is the same as
y' * X * y <= t
because
y' * X * y
is a scalar.

y' * X * y >= 0
because X is psd. Therefore, t must be >= 0. In fact, the value t = 0 can be achieved using y = [0;0]. Therefore, those are optimal values of t and y.


(Li Xin) #3

Thank you for your kind reply.

I came out this thought when I read the book of convex optimization. It says the maximum eigenvalue of the symatric matrix could be formulated as an optimization problem.

\underset{\left\| y \right\|=1}{\mathop{\sup }}\,{{y}^{T}}Xy

However, when I tried to add norm(y,2)==1 rather than norm(y,2) <=1 as the constrain into the optimization problem, I was informed

“Disciplined convex programming error:
Invalid constraint: {convex} == {real constant}”

I don’t know how to transform this optimization into CVX program without formulating sdp problem.
Looking forward to receiving your kind reply again.

Thanks a lot !


(Mark L. Stone) #4

The optimal objective value for that problem is indeed the maximum eigenvalue, but the formulation is not convex. Your optimization problem as written has the optimization variable y. The norm equality constraint is not convex, and therefore is not accepted by CVX.


(Li Xin) #6

Thank you for your help. I got it. :smile: