Optimizing directly on the eigenspectrum of a matrix - MathOverflow

Optimizing directly on the eigenspectrum of a matrix

2011-06-16T19:01:14Z

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?

Answer by Brian Borchers for Optimizing directly on the eigenspectrum of a matrix

2011-06-16T20:17:39Z

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.

Answer by alex o. for Optimizing directly on the eigenspectrum of a matrix

2011-06-16T21:42:25Z

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

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$.
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).
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.
The papers Eigenvalue Optimization by Lewis and Overton and The Mathematics of Eigenvalue Optimization by Lewis.