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): 4995, 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. 

