Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convex Optimization (2004) [pdf]

web.stanford.edu

Post reply on HN
Print view View original

11–20 of 56 posts

Re: Convex Optimization (2004) [pdf]

#11

Post by IIAOPSW »

Solvency wrote: post #5

"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…

All this is is mathematical notation version of a data type system. Its telling you the problem search space is represented as vector x, the optimization problem is 'real f(vector x)', the problem constraint is vector b, and the meaning of b is we are going to test 'for i=0; i<m; i++' { is f(x)<=b[i] }

Re: Convex Optimization (2004) [pdf]

#12

Post by m_c_g »

vrc wrote: post #2

I 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 m…

Author 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.

Re: Convex Optimization (2004) [pdf]

#13

Post by bo1024 »

Solvency wrote: post #5

"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…

It's more some level of what they call "mathematical maturity", or just experience with math. None of this relies on math past the first or second year of college for a typical STEM degree: linear algebra and vector calculus. But most people aren't used to the notation that is taken for granted here, for example, subscripts on functions.

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!

Re: Convex Optimization (2004) [pdf]

#14

Post by cgio »

Solvency wrote: post #5

"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…

It can be a bit intimidating but try to read it not as something you need to understand as in a truth revealed but rather as something you need to understand as in these are the terms we’ll be using to represent what we explain in text. I.e. f0 for objective function, fi for constraints etc. Many otherwise approachable books have this wall of conventions in the beginning + a set of proofs that underpin the key thesis. Try to speed through these sections, picking up as many symbols, findings, as you can , but not everything, and when you reach the actual essence you can go back and revisit. The good thing is that this wall in the beginning becomes very common between books the more you read on a topic. In a sense, if you are a programmer, think of this as the schema representation for the actual message to come.

Re: Convex Optimization (2004) [pdf]

#18

Post by smiley1437 »

I 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-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

Re: Convex Optimization (2004) [pdf]

#19

Post by jcranmer »

Solvency wrote: post #5

"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…

This is one of those things where the math is actually pretty simple, but the notation is incredibly opaque (in part because things are generalized to hell) if you haven't been exposed to it before.

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.

Re: Convex Optimization (2004) [pdf]

#20

Post by fiforpg »

mvcalder wrote: post #10

Professors 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.

Come 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.

Post reply on HN