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!
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.
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
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.