I am excited to announce that a pre-publication draft of my book Algorithms for Convex Optimization (to be published by Cambridge University Press) is now available for download here:

Algorithms for Convex Optimization Book

The goal of this book is to enable a reader to gain an in-depth understanding of algorithms for convex optimization. The emphasis is to derive key algorithms for convex optimization from first principles and to establish precise running time bounds in terms of the input length.

The intended audience includes advanced undergraduate students, graduate students and researches from theoretical computer science, discrete optimization, and machine learning.

1. Chapters 3,4, and 5: Introduction to convexity, models of computation and notions of efficiency in convex optimization, Lagrangian duality, Legendre-Fenchel duality, and KKT conditions.
2. Chapters 6,7, and 8: First-order methods such as gradient descent, mirror descent and the multiplicative weights update method, and accelerated gradient descent.
3. Chapters 9,10, and 11: Newton’s method, path-following interior point methods for linear programming, and self-concordant barrier functions.
4. Chapter 11 and 12: Cutting plane methods such as the ellipsoid method for linear and general convex programs.

Chapter 1 summarizes the book via a brief history of the interplay between continuous and discrete optimization: how the search for fast algorithms for discrete problems is leading to improvements in algorithms for convex optimization.

Many chapters contain applications ranging from finding maximum flows, minimum cuts, and perfect matchings in graphs, to linear optimization over 0-1-polytopes, to submodular function minimization, to computing maximum entropy distributions over combinatorial polytopes.

The book is self-contained and starts with a review of calculus, linear algebra, geometry, dynamical systems, and graph theory in Chapter 2. Exercises posed in this book not only play an important role in checking one’s understanding, but sometimes important methods and concepts are introduced and developed entirely through them. Examples include the Frank-Wolfe method, coordinate descent, stochastic gradient descent, online convex optimization, the min-max theorem for zero-sum games, the Winnow algorithm for classification, the conjugate gradient method, primal-dual interior point method, and matrix scaling.

Feedback, corrections, and comments are welcome.