Eigenvalue Optimization in an Integer Problem

[vschmidtke]

Hello, I am trying to solve the following simple problem (from graph theory) using Yalmip:

I got a simple Topology with 3 Systems which can be represented by L = [1 -1 0; -1 2 -1; 0 -1 1];
Now a fourth System want to join the network and has the possibility to couple to each of the 3 systems from the network leading to:

b1=binvar(1,1)
b2=binvar(1,1)
b3=binvar(1,1)

L = [1, -1, 0, 0; ...
-1, 2, -1, 0;...
0, -1, 1, 0;...
0, 0, 0, 0];
B1 = [1 0 0 -1; 0 0 0 0; 0 0 0 0; -1 0 0 1];
B2 = [0 0 0 0; 0 1 0 -1; 0 0 0 0; 0 -1 0 1];
B3= [0 0 0 0; 0 0 0 0; 0 0 1 -1; 0 0 -1 1];

with the following set of constraints:
constraints = [L+B1b1+B2b2+B3*b3 >= 0] %the outcome has to be positive semidefinit
constraints = [constraints, b1+b2+b3 >=1] %at least one bin value needs to be active

A typical objective is to maximize the second smallest eigenvalue of L+B1b1+B2b2+B3b3 or the maximal eigenvalue of L+B1b1+B2b2+B3b3.
The only option I found was to use sumk to address at the largest eigenvalue. With objective = sumk(L+B1b1+B2b2+B3*b3,1) the largest eigenvalue seems to be minimized instead of being maximized.

Any suggestions to solve this problem ?

Greetings
Vincents

[vschmidtke]

some multiplications in the constraints and objective are missing:
The first constraint is : constraints = [L+B1b1+B2b2+B3b3 >= 0]
and the objective is : objective = sumk(L+B1b1+B2b2+B3b3,1)

[johanlofberg]

Maximizing the second largest eigenvalue, in the case of a Laplacian where the smallest eigenvalue is 0, does have a convex formulation if I recall it correctly (it was actually a project which initiated the whole MISDP framework in YALMIP. Is that what you are working with?

Maximizing the largest eigenvalue sounds harder as it is an intrinsically nonconvex problem. I believe there is a weird nonconvex formulation although I cannot remember it at the moment

[vschmidtke]

Thanks for your fast reply!
I am indeed working with a Laplacian which has the smallest eigenvalue 0. So how can I formulate the objective in order to account for the maximization of specific eigenvalues?

[johanlofberg]

I belive the special case for Graph Laplacians are here
https://web.stanford.edu/~boyd/papers/pdf/cvx_opt_graph_lapl_eigs.pdf

In general, targeting specific eigenvalues, except max of smallest or min of largest, or sum-k variants, is nonconvex and hard to even represent in an optimization framework