Table of Contents

1. Bridging continuous and discrete optimization; 2. Preliminaries; 3. Convexity; 4. Convex optimization and efficiency; 5. Duality and optimality; 6. Gradient descent; 7. Mirror descent and multiplicative weights update; 8. Accelerated gradient descent; 9. Newton's method; 10. An interior point method for linear programming; 11. Variants of the interior point method and self-concordance; 12. Ellipsoid method for linear programming; 13. Ellipsoid method for convex optimization.

Promotional Information

A concise, accessible guide to the modern optimization methods that are transforming computer science, data science, and machine learning.

About the Author

Nisheeth K. Vishnoi is a Professor of Computer Science at Yale University. His research areas include theoretical computer science, optimization, and machine learning. He is a recipient of the Best Paper Award at IEEE FOCS in 2005, the IBM Research Pat Goldberg Memorial Award in 2006, the Indian National Science Academy Young Scientist Award in 2011, and the Best Paper award at ACM FAccT in 2019. He was elected an ACM Fellow in 2019. He obtained a bachelor degree in Computer Science and Engineering from IIT Bombay and a Ph.D. in Algorithms, Combinatorics and Optimization from Georgia Institute of Technology.

Reviews

'The field of mathematical programming has two major themes: linear programming and convex programming. The far-reaching impact of the first theory in computer science, game theory and engineering is well known. We are now witnessing the growth of the second theory as it finds its way into diverse fields such as machine learning, mathematical economics and quantum computing. This much-awaited book with its unique approach, steeped in the modern theory of algorithms, will go a long way in making this happen.' Vijay V. Vazirani, Distinguished Professor at University of California, Irvine

'I had thought that there is no need for new books about convex optimization but this book proves me wrong. It treats both classic and cutting-edge topics with an unparalleled mix of clarity and rigor, building intuitions about key ideas and algorithms driving the field. A must read for anyone interested in optimization!' Aleksander Madry, Massachusetts Institute of Technology

'Vishnoi's book provides an exceptionally good introduction to convex optimization for students and researchers in computer science, operations research, and discrete optimization. The book gives a comprehensive introduction to classical results as well as to some of the most recent developments. Concepts and ideas are introduced from first principles, conveying helpful intuitions. There is significant emphasis on bridging continuous and discrete optimization, in particular, on recent breakthroughs on flow problems using convex optimization methods; the book starts with an enlightening overview of the interplay between these areas.' László Végh, LSE

'Recommended.' M. Bona, Choice Connect