Convex Optimization (2004) [pdf]
web.stanford.edu
web.stanford.edu
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
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
He’s also got an edX course you can audit for free.
https://www.edx.org/course/convex-optimization?index=product...
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.
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.
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?
“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.
A list of them can be found at
It's a graduate-level course. If that paragraph is arcane, the book is probably a few courses in your future.
So yeah, the necessary concepts to study that course are not much but you have to have a strong habit of thinking in maths to apply them. And that habit comes with a lot of practice...
I know it looks scary if you aren't used to it, but it just takes some practice to pick up. This is far from arcane and elite in the math world!
In layman's terms: you have a set of n variables, a set of m constraints on those variables (like x + y ≤ 3, or x² + y² ≥ 1), and some function you're trying to minimize. Oh, and everything involves real numbers, no fancy stuff like complex numbers or rationals or p-adic integers or Banach spaces.
The book itself gives you a taste of what you need to know to fully understand the material:
> 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.
Or integers! You could probably do complex convex optimisation okay, but when it's integers, you need a whole new set of techniques.
If you're not used to it, this kind of notation looks like hieroglyphics.
If you are used to it, every vague English-language technical document you see floating around your workplace just reads like a bunch of flailing-arm hand-waving.
Or maybe you were really asking. That's the thing about the Internet. Only the FBI knows you're a dog, and nobody knows what the dog really means.
But if it really was a question, gms7777's sibling reply is good.
It has tons of code and exercises in Julia and Python. Start here, excellent to get a taste of linear algebra and its applications.
And the f1, f2, ... fm are simply the (inequality) constraints that all candidate solutions must satisfy.
For example, you might want to maximize the volume of something you want to build from sheet metal, then f0 could be the expression for the volume of body and the constraint could be one inequality ie area(x) <= your_maximum_budget_for_sheet_metal etc
> Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?
You don't have a degree in some STEM area (or even economics)? To me, this rather looks like the kind of basic mathematical notation that you learn and get become perfectly used to in the first two years of your degree course.
I always tend to get tripped up in the terminology and the symbols.
Probably helps to have a bit of a background in mathematical optimization, if you, uh, pardon the recursion.
As others have said: it's actually fairly straightforward and clear. That paragraph states exactly what they mean by "a mathematical optimization problem".
A simpler version that you might have seen in Calculus for Jocks is one where you are supposed to find the optimum of a single-variate function with no further constraints -- just find the largest or smallest value. You would look for places where the tangent is horizontal (by differentiating) + you would look at the "ends" (by looking at limits).
"Here the vector x..." tells us that this cost function is a bit more complicated: you are not looking for a single input value but a vector of many input values.
"subject to fi(x) <= bi" tells us that there are constraints and what language the authors will use to describe those constraints.
It's really all fairly standard and simple. The hard parts come later.
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.
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.