Optimizing directly on the eigenspectrum of a matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:11:25Z http://mathoverflow.net/feeds/question/67989 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67989/optimizing-directly-on-the-eigenspectrum-of-a-matrix Optimizing directly on the eigenspectrum of a matrix DoubleJay 2011-06-16T19:01:14Z 2011-06-16T21:42:25Z <p>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?</p> http://mathoverflow.net/questions/67989/optimizing-directly-on-the-eigenspectrum-of-a-matrix/67996#67996 Answer by Brian Borchers for Optimizing directly on the eigenspectrum of a matrix Brian Borchers 2011-06-16T20:17:39Z 2011-06-16T20:17:39Z <p>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. </p> <p>You should check out the SIAM Review paper on semidefinite programming by Vandenberghe and Boyd:</p> <p>L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review, 38(1): 49-95, March 1996.</p> <p><a href="http://stanford.edu/~boyd/papers/sdp.html" rel="nofollow">http://stanford.edu/~boyd/papers/sdp.html</a></p> <p>Vandenberghe and Boyd also have a textbook on convex optimization- you can read the .pdf online for free. See</p> <p><a href="http://www.stanford.edu/~boyd/cvxbook/" rel="nofollow">http://www.stanford.edu/~boyd/cvxbook/</a></p> <p>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. </p> http://mathoverflow.net/questions/67989/optimizing-directly-on-the-eigenspectrum-of-a-matrix/68007#68007 Answer by alex o. for Optimizing directly on the eigenspectrum of a matrix alex o. 2011-06-16T21:42:25Z 2011-06-16T21:42:25Z <p>Naturally, the answer very much depends on the function you'd like to optimize. I recommend looking at:</p> <ol> <li><p>Proposition 4.2.1 in <a href="http://www.amazon.com/Lectures-Modern-Convex-Optimization-Applications/dp/0898714915" rel="nofollow">Lectures on Modern Convex Optimization</a> 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$. </p></li> <li><p>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).</p></li> <li><p>On the other hand, these types of problems can quickly become NP-hard. The paper <a href="http://www.sciencedirect.com/science/article/pii/S0167637708001077" rel="nofollow">Maximum algebraic connectivity augmentation is NP-hard</a> 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.</p></li> <li><p>The papers <a href="http://www.cs.nyu.edu/overton/papers/pdffiles/acta.pdf" rel="nofollow">Eigenvalue Optimization</a> by Lewis and Overton and <a href="http://www.optimization-online.org/DB_HTML/2003/04/640.html" rel="nofollow">The Mathematics of Eigenvalue Optimization</a> by Lewis. </p></li> </ol>