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

21–30 of 56 posts

Re: Convex Optimization (2004) [pdf]

#21

Post by quantum_state »

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…

If one reads a few serious introductory math books, starting from set theory, etc., one would get used to this “math” language and find it natural, precise, and effective.

Re: Convex Optimization (2004) [pdf]

#22

Post by nextos »

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

If one reads a few serious introductory math books, starting from set theory, etc., one would get used to this “math” language and find it natural, precise, and effective.

Also, really important to refer to Boyd's prequel book, which is much simpler and can be read by anyone here without any prior background: https://web.stanford.edu/~boyd/vmls

It has tons of code and exercises in Julia and Python. Start here, excellent to get a taste of linear algebra and its applications.

Re: Convex Optimization (2004) [pdf]

#24

Post by crabmusket »

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

Re: Convex Optimization (2004) [pdf]

#25

Post by Blammar »

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

Nicely put!

Re: Convex Optimization (2004) [pdf]

#26

Post by donkeybeer »

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

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.

Re: Convex Optimization (2004) [pdf]

#27

Post by donkeybeer »

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…

Its saying a very simple thing with somewhat convoluted language. First of all for full generality they are treating functions of Rn -> R (if the output is also a vector then it becomes a different type of problem, I believe its called multimodal optimisation).

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

Re: Convex Optimization (2004) [pdf]

#28

Post by blt »

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…

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

Re: Convex Optimization (2004) [pdf]

#29

Post by bjornsing »

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

I still remember the formal prerequisite for one of the more advanced math courses I took at uni: “The mathematical maturity that several years of study in mathematics typically gives” (roughly translated from Swedish). I thought it was kind if pretentious at the time (most other courses listed other courses as prerequisites), but now I think it makes sense.

Re: Convex Optimization (2004) [pdf]

#30

Post by PartiallyTyped »

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