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?
Naturally, the answer very much depends on the function you'd like to optimize. I recommend looking at:
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.
Vandenberghe and Boyd also have a textbook on convex optimization- you can read the .pdf online for free. See
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.