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

31–40 of 56 posts

Re: Convex Optimization (2004) [pdf]

#31

Post by PartiallyTyped »

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…

Can attest, I studied Nocedal & Wright's book last year during my master's, it was my favourite course.

Re: Convex Optimization (2004) [pdf]

#32

Post by aleph_minus_one »

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…

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

Re: Convex Optimization (2004) [pdf]

#33

Post by antman »

smiley1437 wrote: post #18

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

Non paywalled by Lars Blackmore http://www.larsblackmore.com/iee_tcst13.pdf

Re: Convex Optimization (2004) [pdf]

#34

Post by wiz21c »

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

From 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 f…

A someone who followed courses in num op, I can say that yes, indeed, the math concepts are rather basic and not that hard to learn. BUT you have to be at ease with mathematical reasoning because many of the proofs are not that easy to understand, they involve quite a lot of small insights here and there. Nothing really hard, but your brain will definitely have to work to understand these.

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

Re: Convex Optimization (2004) [pdf]

#35

Post by 4gotunameagain »

PartiallyTyped wrote: post #30
smiley1437 wrote: post #18

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

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

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

Re: Convex Optimization (2004) [pdf]

#36

Post by yxhuvud »

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…

Huh? This is quite straightforward and is simply establishing what terms are used for describing the problem. The problem formulation itself seems to be the same as in any lower level course on optimization that is taught to regular masters students, so it is expected that anyone reading the paper will already know it.

Re: Convex Optimization (2004) [pdf]

#37

Post by gigatexal »

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…

I'm probably the most junior math person here. I got to Advanced Algebra and then Calc 1 and realized I peaked in Advanced Algebra. That being said, judging from just the paragraph one might need an understanding of number theory (sets to be exact), vectors, ...

I always tend to get tripped up in the terminology and the symbols.

Re: Convex Optimization (2004) [pdf]

#38

Post by IIAOPSW »

donkeybeer wrote: post #26
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] }

I must clarify, the function to optimize is f0(x), and the constraints are a set of functions fi that should each be <= bi. You have used a single function for the constraints in your pseudocode.

oops

Re: Convex Optimization (2004) [pdf]

#39

Post by PartiallyTyped »

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

Earlier quoted context omitted.

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

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.

Re: Convex Optimization (2004) [pdf]

#40

Post by HelloNurse »

IIAOPSW wrote: post #11
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] }

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.
Post reply on HN