1
$\begingroup$

I have an application where I want to the eigenvalues of the graph to be involved in the objective and constraints in a flexible way (moreso than just the nuclear or frobenius norm). Whats a good survey or intro source to this sort of optimization?

$\endgroup$

2 Answers 2

4
$\begingroup$

Naturally, the answer very much depends on the function you'd like to optimize. I recommend looking at:

  1. Proposition 4.2.1 in Lectures on Modern Convex Optimization by Ben-Tal and Nemirovski. It describes a large set of eigenvalue optimization problems which can be written as semidefinite programs. Specifically, if $g(x_1,\ldots,x_n)$ is a symmetric function such the set $t \geq g(x_1,\ldots,x_n)$ has a semidefinite representation, then so does the set $t \geq g(\lambda(X))$, where $\lambda(X)$ is a vector of eigenvalues of a symmetric matrix $X$.

  2. Section 4.2 in the same book, which gives some other examples of functions of eigenvalues that can be written in this way (for example, sums of $k$ largest eigenvalues of a symmetric matrix).

  3. On the other hand, these types of problems can quickly become NP-hard. The paper Maximum algebraic connectivity augmentation is NP-hard by Damon Mosk-Aoyama shows that the problem of adding a prespecified number of edges to the graph to maximize the second-smallest eigenvalue of the Laplacian is NP-hard.

  4. The papers Eigenvalue Optimization by Lewis and Overton and The Mathematics of Eigenvalue Optimization by Lewis.

$\endgroup$
3
$\begingroup$

Many (but not all) problems involving the eigenvalues of a graph are convex optimization problems that can be formulated as semidefinite programming problems. There are a number of "tricks" that you need to learn in order to formulate problems as SDP's. Once you've got an SDP, there are a number of software packages that can be used to solve the SDP.

You should check out the SIAM Review paper on semidefinite programming by Vandenberghe and Boyd:

L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review, 38(1): 49-95, March 1996.

http://stanford.edu/~boyd/papers/sdp.html

Vandenberghe and Boyd also have a textbook on convex optimization- you can read the .pdf online for free. See

http://www.stanford.edu/~boyd/cvxbook/

Unfortunately, there are lots of eigenvalue optimization problems that cannot be formulated as convex optimization problems. These are much harder (if not practically impossible) to solve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.