Cvx SDP maximizing lambda_2


(Sarah Brown) #1

Hi, I’m new with CVX and have some optimization problems. I am trying to optimize the algebraic connectivity of a graph by adding new edges. The SDP problem is formulated as following:

maximize lambda_2
s.t. L_0 + sum(x_e h_eh_e’) >= lambda_2I - miueye(n)

0<= x <= 1
1’x=k

I dont know how to transform this problem in to matlab cvx code.
e is a candidate edges to be added to the graph. L_0 is the original Laplacian matrix of the graph.


(Mark L. Stone) #2

Does I in lambda_2*I mean eye(n)? I don’t understand how x, which appears in the constraints, has any relevance to the problem, unless it is involved with x_e. You need to clarify. Your sum(x_e h_eh_e’) term needs to evaluate to a square (symmetric) matrix, so are you summing over indexed matrices? So the program below doesn’t really make sense, but is an outline of a program which you need to fix up. You need to clarify how x manifests itself in your problem other than through “irrelevant” constraints which are not tied to the rest of the problem.

Please read the CVX Uses’ Guide, and of course, make sure all operations follow the usual MATLAB rules to be conforming dimensions, etc.

cvx_begin
variables lambda_2 x(n,1)
maximize(lambda_2)
L_0 + sum(x_e *h_e*h_e') - (lambda_2*eye(n) - miu*eye(n))  == semidefinite(n)
0 <= x <= 1
sum(x) == k
cvx_end