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

41–50 of 56 posts

Re: Convex Optimization (2004) [pdf]

#41

Post by twic »

jcranmer wrote: post #19
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…

> Oh, and everything involves real numbers, no fancy stuff like complex numbers or rationals or p-adic integers or Banach spaces.

Or integers! You could probably do complex convex optimisation okay, but when it's integers, you need a whole new set of techniques.

Re: Convex Optimization (2004) [pdf]

#42

Post by ant6n »

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…

> Exactly what arcane requisite elite math precursors are necessary to even remotely understand this?

Probably helps to have a bit of a background in mathematical optimization, if you, uh, pardon the recursion.

Re: Convex Optimization (2004) [pdf]

#43

Post by vrc »

m_c_g wrote: post #12
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…

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

Re: Convex Optimization (2004) [pdf]

#44

Post by FooBarBizBazz »

jcranmer wrote: post #19
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…

> This is one of those things where the math is actually pretty simple, but the notation is incredibly opaque

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.

Re: Convex Optimization (2004) [pdf]

#45

Post by bo1024 »

PartiallyTyped wrote: post #39
4gotunameagain wrote: post #35

Earlier quoted context omitted.

no 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

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

On that side, reinforcement learning bleeds over into control theory, so you're partly right.

Re: Convex Optimization (2004) [pdf]

#46

Post by IIAOPSW »

HelloNurse wrote: post #40
IIAOPSW wrote: post #11

Earlier quoted context omitted.

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] }

The mathematical entities are straightforward, and the important things to remember in this definitions package are conventions and names: x is the variable vector and its cardinality is n , minimization of a function called f0 is the objective, fi are the m constraints, and they are numbered starting from 1 to exclude "f0" and avoid the use of a different letter for the objective function.

0 for 0bjective

Re: Convex Optimization (2004) [pdf]

#47

Post by peterfirefly »

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…

Getting tripped up by this is like seeing Cyrillic letters in an intro book on Russian and believing those are the hard parts of learning Russian.

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) It's really all fairly standard and simple. The hard parts come later.

Re: Convex Optimization (2004) [pdf]

#48

Post by turtleyacht »

hinkley wrote: post #7
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…

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

SIGPLAN: Special Interest Group on Programming Languages (online)

A list of them can be found at

https://www.acm.org/special-interest-groups/join

Re: Convex Optimization (2004) [pdf]

#49

Post by Solvency »

FooBarBizBazz wrote: post #44
jcranmer wrote: post #19

Earlier quoted context omitted.

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…

> This is one of those things where the math is actually pretty simple, but the notation is incredibly opaque 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.

What do you mean by that?

Re: Convex Optimization (2004) [pdf]

#50

Post by optbuild »

fiforpg wrote: post #20
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 im…

Which book by Nocedal and Wright? Can someone link to it?
Post reply on HN