Various useful resources for learning optimziation and computing
This post is a collection of good resources I have used during my studies to learn topics in convex optimization and computer systems and my review of each resource. This is intended to be a living document, and I will update this list every once in a while.
Disclaimer: I am not an expert in optimization or computing, but I am writing this post because I feel like I have spent enough time learning both to be able to recommend good resources.
This section mostly focuses on convex optimization.
This textbook which can freely be found here is the classic introduction resource to convex optimization. This textbook has corresponding lectures by Stephen Boyd which can be found here. Additionally, Professor Boyd teaches this course at Stanford University and the course webpage which has all the lecture notes can be found here.
The textbook has three parts: theory, application, and algorithms. The theory part of the textbook mostly focuses on what is convexity, why is it important, and what are operations that preserve convexity. Then it covers the classical convex optimization problems such as linear programs, quadratic programs, second-order cone programs, and semidefinite programs. Finally, it covers duality and the Karush-Kuhn-Tucker (KKT) conditions.
I think this book is a good introduction to convex optimization, but it is not my favorite textbook to learn optimization algorithms from. Although part 3 of the textbook does cover optimization algorithms, it mostly focuses on primal interior point methods, which are not used much by popular convex solvers. Additionally, I do not care much for the presentation of duality, it feels quite prescriptive in my opinion and a bit unmotivated. Boyd presents duality as a “structured way to create lower bounds for optimization problems”, which although that is true, I believe the real importance of duality in convex optimization is to aid in algorithm design.
Nevertheless, I recommend any beginner to read the first part of this book before reading any other textbook on this list.
This is one of the best textbooks for learning about optimization algorithms. The beginning of the book discusses optimization algorithms for unconstrained nonconvex problems. To be honest I have not read much of that part. Chapters 12-17 are a goldmine for learning about algorithms for constrained convex optimization. I also love the presentation of duality in Chapter 12 far more than Boyd’s treatment. In this textbook duality is presented as a tool in algorithm design.
I also enjoy the historical perspective this textbook brings on optimization algorithms. First, the simplex method for linear programming is discussed, then its drawbacks (worst case exponential runtime) are presented, then interior point methods are presented. This textbook in my opinion, has the best explanation for how primal and primal-dual interior point methods work. My only complaint is that the primal-dual interior point method is only described for linear programming and quadratic programming and does not include second-order cone programming and semidefinite cone programming. The book also discusses active set methods for quadratic programming and presents the material is a very clear way.
My only complaints about this book is that primal-dual interior point methods are not described for second-order cone programming and semidefinite programming. Also operator splitting methods such as forward-backwards splitting, ADMM, and PDHG are not discussed.
This textbook can be freely found here with accompanying videos here.
This is my favorite textbook of all time by a long shot, and is the best resource I have found to understand operator-splitting methods. I have always heard about projected gradient descent, the proximal point method, ISTA, augmented Lagrangian methods, Douglas-Rachford Splitting, ADMM, PDHG etc, and always viewed them as separate concepts in my mind. However, this textbook unifies all of these algorithms as fixed-point iterations with some averaged operator. Even reading the first three chapters will be an extremely eye-opening experience to those interested in operator-splitting methods.
This set of course notes discusses the fundemental concepts in convex analysis in a rigorous way. I used these notes in my Convex Analysis class and enjoyed them.
Disclaimer: I have not read this textbook, but it has been highly praised for rigorously discussed Monotone operator theory which is fundemental for rigorously analyzing operator splitting methods.
The YouTube playlist is here. This is the best video series to learn C++. I love that he discusses not only C++ syntax, but what is happening under the hood in terms how data and the program is stored in memory.
This video series by Ben Eater is a fantastic introduction to computer architecture. He starts from simple and/or/not gates and builds an 8-bit computer on a breadboard while explaining everything you need to know along the way.
Although this series does not discuss important topics for performance such as cache and branch prediction, this is a fantastic video series for a beginner who wants to understand how a CPU works.
This video series is from the 15-213: Introduction to Computer Systems course at Carnegie Mellon University and follows this textbook.
This is my favorite resource to learn about lower level concepts in computing such as assembly, memory cache, and writing more performant code.
This course by Casey Muratori is fantastic for understanding how to write code in a performance oriented way. I am currently working through it.