## Optimizing directly on the eigenspectrum of a matrix

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

## 2 Answers

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.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 6, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.892545223236084, "perplexity_flag": "head"}