Convex Optimization Notes
During my sabbatical, one of the book that I want to finish is this beauty by stephen boyd and Lieven Vandenberghe :-
source: carousell.com
and I gotta tell you that this was one of the toughest book I have read but at the same time, this was one of the most rewarding… that’s why I have compiled some of my notes, resources and interactive notebooks which might ease your pain a little bit while going through this beautiful book yourself.
Disclaimer: Here, I have only created notes on part I of this book, mainly because I feel like the rest of the parts doesn’t really need them and the reason for that is, in part II we only focus on the application of the methods (which we have learned in part I) in different domains and part III focus on the implementation details and the algorithms used to solve our optimization problem(also, most of the distillation is been done by those great lectures by stanford which i refer down below )… but at the same time, I also think that I should give a brief overview of each of the parts. which is exactly the kind of format I chose to proceed with… but I might be completely wrong( please let me know what you guys think! )
Also, If you are new to optimization and don’t want to read the entire book then I recommend you to first go through this blog post(#shameless plug) then quickly head over to the Chapter 4 interactive notebook which will get 60% of the job done when it comes to effectively using Convex optimization.
Ok, enough fooling around, let’s dive straight into the notes…
Part 1: Theory
Part I gives you an introduction to the fascinating world of convex optimization, it first goes over what are convex sets and how to tell the difference between convex and non-convex using Jensen’s inequality then it go over-generalized inequality which essentially generalizes all the concepts regarding the 1-d convex optimization into multiple dimensions by defining them with respect to a proper cone. in chapter 3 we will first formulate convex optimization problems and understand what are convex functions and what are some of the operations which when applied to these functions would still give us a convex function for example if we take the summation of 2 convex-function is also convex. we also looked at another import concept called conjugate functions which gives us the lower bound over our original convex functions we will also touch this concept of lower bound in the last chapter of part I in which, we will talk about the dual function and duality. chapter 4 introduces us the different types of convex optimization problems like Second-order cone programming(LP), linear programming (LP), geometric programming (GP), some of which may not be convex in its natural formulation but can be cast to convex optimization problems which can then be solved using different convex optimization package, one of which is the CVXPY which we will use it in our interactive notebook…
Chapter 2: Convex Sets:-
-
Personally I like this one a bit more
- Practice Problems (by Stanford)
Chapter 3: Convex Functions:-
Chapter 4: Convex Optimization Problems \
Chapter 5: Duality
Part 2 : Application
Part II focuses on the Application of all the theories we have read in Part I of this book. here, we first look at how to use convex optimization to solve curve fitting/ regression problems (in some sense), one of the techniques that intrigue me is the concept of Huber-penalty function which we will use to define many robust approximation models in the next chapter we will go through MLE and MAP estimation from the perspective of statistics as well as convex optimization we also looked at the hypothesis testing and how to formulate our assumptions into CVX problem lastly we looked at 2 of the most important bounds in statistical estimation Chebyshev and Chernoff bounds. in chapter 8 we looked at different geometric problems like analytic centric ( which is used in almost every field), classification (we will also look at QDE and even SVM!) lastly, we will look at the problem of floor planning which essentially finds best dimensions of each of the rooms given the maximum dimension of the land, this technique is also being used in VLSI design(circuit design) in which we have to design the circuit using the resources as optimally as possible…
Chapter 6: Approximatation and Fitting
Chapter 7: Statistical Estimation
Chapter 8: Geometric problems
Part 3 : Algorithms
Part III go over some of the most important algorithm which are the workhorses behind these covex optimization packages like CVXOPT, CVXPY, APOPT etc in chapter 9 we looked at several gradient based methods to solve unconstrained minimiztion problems like our good o’l gradient descent and also looked at methods which uses second order methods like newton’s methods etc. we also looked at the theory of self concordence which helps us to analyse newton’s method also the method we will look at in later chapters, in chpater 10 we again use newton’s method to solve equality constaint minimization problem we also looked at some of the implementation details which might prove useful if you are using this to create your own library or wanna understand how other library implements these concepts… lastly, in the final chapter we looked at on of the most important method in the modern convex optimization litrature is the concept of interior point method which helps us to solve the inequality constriant minimization problem by recursively solving the equaltiy constraint problem using the method called ‘barrier method’ although one might agruge that the explaination of interior-point methods isn’t complete enough in this book but more like an introduction and that would be correct so please don’t take this chapter as end all be all of this methods (if you want to dive deep into this concept then I really like this book by Nocedal & Wright. by the way, there is also a video about it which you might find useful while going through that book ) also, one more thing, I bet by the end of this chapter you will start respecting the least-squares methods again.. :D
Chapter 9: Unconstrained Minimization
Chapter 10: Equality constrained minimization
Chapter 11: Interior-point methods
Appendices:
Also, I really liked the Playlist by Ahemed Bazzi:- https://www.youtube.com/watch?v=SHJuGASZwlE&list=PL-DDW8QIRjNOVxrU2efygBw0xADVOgpmw
and this course by CMU (ryan tibshirani is awesome! ) which also, covers a bit more then this book as to offer :- https://www.youtube.com/playlist?list=PLRPU00LaonXQ27RBcq6jFJnyIbGw5azOI
Anyways, thats it from my side, I hope these resource was somewhat helpful to you, if you have any questions, suggestions regarding any of these notes or wanted share some awesome resource yourself then please feel to let me and others know about them in the comments below, I would really love to hear your thoughts.
Untill next time, Have a great day!
References:-
- convex optimization book (https://web.stanford.edu/~boyd/cvxbook/)
- The unlisted stanford video is taken from now closed stanford lagunita course(https://lagunita.stanford.edu/courses/Engineering/CVX101/Winter2014/about)
