8 ms·
Convex Optimization (2004) [pdf]
- vrc 3y agoI had the pleasure of taking this course with Prof. Boyd when he did a semester at MIT and it really was excellent. With a basic understanding of linear algebra and proofs it opened my eyes to so many techniques and ways to look at problems. It also lowered my fear of tackling more complex coursework because it motivated my interest. The only downside is that I became far too over reliant on the MATLAB package they made to pair with the course, so trying to implement some of the techniques later on from scratch took some doing.
- m_c_g 3y agoAuthor of said MATLAB package (CVX) here. Yours is a really interesting observation! When the book was created, CVX didn't exist. Instead, Boyd & Vandenberghe wrote separate MATLAB scripts for virtually every figure (to be fair, with a lot of cut-and-paste and convenience functions). The course did hum along pretty well without CVX (or its later and now better-supported Python equivalent CVXPY), for sure. I think it is fair to say that these software packages made convex optimization far more accessible a topic. Certainly, implementing some of the solution techniques is not straightforward. But far more people can actually spend time using convex optimization in their application domains if they don't have to concern themselves with those implementation complexities. Incidentally, on the commercial side, Mosek ApS and Gurobi both offer Python-based modeling frameworks for convex optimization that do a great job of making the discipline accessible as well. They don't operate in quite the same way as CVX and CVXPY, but that's not really important: what matters is that people can readily solve their problems, not the specific approach that gets that done.
- vrc 3y agoI agree with all your points. CVX made it so that students like me spent more time learning the material and techniques and less time worrying about implementation. Great work!
- onos 3y agoI’ve heard great things but it’s longer than I could commit to reading. Can anyone recommend a similar but more concise text?
- yellowcake0 3y agoOne of my favorite math books, there's also the companion text, https://web.mit.edu/~jadbabai/www/EE605/additional_exercises.pdf https://web.mit.edu/~jadbabai/www/EE605/additional_exercises..., which contains a lot of interesting applications, presumably compiled by Boyd himself and his colleagues over the years.
- Solvency 3y ago"A mathematical optimization problem, or just optimization problem, has the form minimize f0(x) subject to fi(x) ≤ bi , i = 1, . . . , m. (1.1) Here the vector x = (x1, . . . , xn) is the optimization variable of the problem, the function f0 : R n → R is the objective function, the functions fi : R n → R, i = 1, . . . , m, are the (inequality) constraint functions, and the constants b1, . . . , bm are the limits, or bounds, for the constraints. A vector x ⋆ is called optimal, or a solution of the problem (1.1), if it has the smallest objective value among all vectors that satisfy the constraints: for any z with f1(z) ≤ b1, . . . , fm(z) ≤ bm, we have f0(z) ≥ f0(x ⋆ ). We generally consider families or classes of optimization problems, characterized by particular forms of the objective and constraint functions. As an important example, the optimization problem (1.1) is called a linear program if..." Boy, and that's just the opening paragraph of the introduction. Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?
- hinkley 3y agoOnce upon a time I mentioned in passing that I subscribed to the proceedings of SIGPLAN. My coworker shot his hand out to stop the conversation. “You can read those??” “A little more than half.” I knew exactly what he meant, and was amused that “half” satisfied his sudden suspicion that I was an alien living among humans.
- turtleyacht 3y agoSIGPLAN: Special Interest Group on Programming Languages (online) A list of them can be found at https://www.acm.org/special-interest-groups/join https://www.acm.org/special-interest-groups/join
- hinkley 3y agoThe jargon is not as dense as your typical math paper, but they sure do try sometimes.
- dfan 3y agoFrom the introduction: "The only background required of the reader is a good knowledge of advanced calculus and linear algebra. If the reader has seen basic mathematical analysis (e.g., norms, convergence, elementary topology), and basic probability theory, he or she should be able to follow every argument and discussion in the book." It's a graduate-level course. If that paragraph is arcane, the book is probably a few courses in your future.
- melling 3y agoThe videos for Boyd’s classes are on YouTube. He’s also got an edX course you can audit for free. https://www.edx.org/course/convex-optimization?index=product&queryID=9c2eb1365338c848c42b8c902f1bc587&position=6&linked_from=autocomplete&c=autocomplete https://www.edx.org/course/convex-optimization?index=product...
- mvcalder 3y agoProfessors Boyd and Vandenberghe really broke ground with this text. Prior to this, optimization algorithms and methods were very much locked up behind a metaphorical paywall: difficult to access literature with very high barriers to entry, and strictly commercial software offerings. They brought optimization to the masses and should be celebrated for it.
- fiforpg 3y agoCome on, prior to this people read Nocedal & Wright, which is still very much a standard text on nonlinear optimization, and there were well-known implementations of nonlinear optimization algorithms written by these people in Fortran. These are most likely hiding in any modern LBFGS library you are looking at, including Scipy etc. It is rather that more people understand these algorithms now and more people wrote implementations or bindings for popular languages, so you don't need to use Fortran anymore these days, but only conveniently invoke your optimization library of choice. The entire optimization ecosystem has matured; any particular good book certainly has contributed to that, but so did any other particular good book.
- blt 3y agoThey complement each other well IMO. Nocedal & Wright focus more on algorithmic details and methods that can be applied to nonconvex problems. Boyd & Vandenberghe focus more on convex analysis and showing how some non-obvious problems can be expressed in convex form. B&V might be more useful as an "extended user's manual" for convex optimization software. I would guess that most readers of N&W are writing their own solvers, or at least want to know what all the tolerances mean in their third-party solver's bewildering list of parameters.
- PartiallyTyped 3y agoCan attest, I studied Nocedal & Wright's book last year during my master's, it was my favourite course.
- optbuild 3y agoWhich book by Nocedal and Wright? Can someone link to it?
- uptownfunk 3y agoDoes this have any application to SOTA ML?
- nextos 3y agoYes, AFAIK to regularized regression which you would typically use in problems with more variables than instances, such as GWAS.
- TrackerFF 3y agoDunno if support vector machines are still considered "SOTA", but that would be one of the most obvious examples of a convex optimization problem (and probably a good starting point for students trying to tie ML and convex optimization)
- smiley1437 3y agoI remember ago Lars Blackmore of SpaceX released a paper on soft landing Falcon 9, that's the first time I'd encountered convex optimization https://www.semanticscholar.org/paper/Lossless-Convexification-of-Nonconvex-Control-Bound-A%C3%A7ikmese-Carson/9209221aa6936426627bcd39b4ad0604940a51f9?p2df https://www.semanticscholar.org/paper/Lossless-Convexificati... It blew my mind that you could convexify non-convex curves into useful-for-optimization convex curves to optimize for so many things simultaneously (physics constraints, control thruster limitations, sensor constraints, g forces, etc) and it's cool that part of the spectacular landings we get from SpaceX relies on it
- antman 3y agoNon paywalled by Lars Blackmore http://www.larsblackmore.com/iee_tcst13.pdf http://www.larsblackmore.com/iee_tcst13.pdf
- PartiallyTyped 3y agotil. For whatever reason I totally imagined it was some RL based method trained on sims. In my defense, RL is used for control problems as well, but this is so cool! Thank you for sharing.
- 4gotunameagain 3y agono serious, safety critical system uses RL (except tesla "autopilot" and we see how that went). Control theory algorithms can be validated to work within the desired envelope and produce a valid solution. The big advantage of convexifying the problem, is that when it is convex you have a guarantee it can be solved in fixed time, a major requirement for real time systems
- PartiallyTyped 3y agoI wasn't thinking of DeepRL, but more on the more classical side of things with approximators other than neural NNs; but what you describe makes sense.
- blt 3y agoMy grad school bible!
- crabmusket 3y agoEncountered this in my final year of University and audited half the online course before it went way beyond what I needed to know. Boyd was a great lecturer, and the content was fantastic. Really interesting stuff to know. I was applying it to model-predictive control, which is a super interesting set of algorithms as well.
- cpgxiii 3y agoConvex optimization can be a really amazing tool. We use optimization extensively, both on actually convex problems, and on non-convex-but-practically-solvable problems in robotics. The math surrounding optimization is great; however, the reality of optimization tools is still very poor. A competitive optimizer is a massive project, and outside of a number of mostly limited/specialized solvers, the effective tools are all proprietary and very expensive (e.g. SNOPT, Gurobi, Mosek, CPLEX, etc). How solveable and stable your problems can be depends on these tools, and effective problem formulation (e.g. what and how many constraints you use, how you compute gradients) is essentially a black art learned through hard experience. There's a great example of the complexity difference between optimization and other tools in the world of motion planning for robots: we expect that any semi-competent undergrad can implement search- and sampling-based planners (e.g. A* or RRT), implementing a good optimizer for trajectory optimization is a multi-million dollar project. The world of optimization desperately needs a MuJoCo-DeepMind moment, where a large interested company buys one of the major commercial optimization providers and makes their tools free and open source. This would really be transformative to the field.