Learning about convex optimisation

Question

I'm interested in learning a bit about convex optimisation. The wikipedia article contains the following paragraph:

The convexity of $f$ makes the powerful tools of convex analysis applicable. In finite-dimensional normed spaces, the Hahn–Banach theorem and the existence of subgradients lead to a particularly satisfying theory of necessary and sufficient conditions for optimality, a duality theory generalizing that for linear programming, and effective computational methods.

which I find fascinating. It's telling me that I can use advanced mathematical tools to study optimisation, much like the article explaining how Lagrange multipliers come from manifolds.

I'm looking for a book gives rigorous proofs of the mathematical statements in the quote.

People recommended Boyd and Vandenberghe, but it's not the hi-tech exposition I'm looking for.

Answer 1

I think you want Convex Optimization Theory by Dimitri P. Bertsekas, and Convex Analysis and Optimization by Bertsekas, Nedić, and Ozdaglar.

These are a product of an theoretical, east-coast (i.e., MIT) approach to convex optimization, as opposed to the more practical, west-coast (i.e., Stanford) approach offered by Boyd & Vandenberghe. (And you thought rappers were the only ones that had the whole "east coast/west coast" thing.) I've got both coasts on my bookshelf and they complement each other well.

Do check out the supplemental materials at the bottom of both web pages. These books have been used in MIT OpenCourseware courses, which means there is quite a bit of supplemental material readily available.

Answer 2

I highly recommend the following book:

Hiriart-Urruty, Jean-Baptiste, and Claude Lemaréchal. Fundamentals of convex analysis.

It is a rigorous book on the mathematical foundations on convex analysis, and is designed for learning the topic from the ground up. I can't comment on how the book compares to Bersekas' Convex Optimization Theory, since I haven't read his book. Probably both would be good choices, Bertsekas is a great author.

For algorithms, a (very) new option is "Convex Optimization Algorithms," also by Bertsekas. I've only read part of it so far, but I've enjoyed it a lot.