Undergrad Mathematics for OptimisationWatch
I'm looking for some advice from someone who has studied Optimisation as an undergrad or postgrad, and who has a good understanding of the underpinning mathematical concepts.
I'm starting an MSc in September, and perhaps unlike many people who will start the course, my maths knowledge does not extend beyond my A-Levels.
The MSc is in Business Analysis, so I don't think that the maths will be too rigorous, not like a pure Operations Research course might be. It will be more about understanding the concepts and being able to implement the techniques using software packages.
Still, I'm conscious I've missed out on undergraduate maths and I'd like to further my knowledge (to the extent that I can in the next three months!) and try and improve my understanding in some key areas.
What would be the best areas to focus on do you think? I was considering the MIT opencourseware lectures on linear algebra: http://ocw.mit.edu/courses/mathemati...ideo-lectures/
Differential equations perhaps?
Any advice would be really appreciated, particularly if you can explain why the suggested skills are useful from an Optimisation perspective.
Thanks for you thoughts.
If you're in doubt, buy a (used) copy of Numerical Recipes and have a read. The prose is very good and will become an excellent resource for the future. It gives you some more practical discussion of optimisation.
I think a large part of the optimisation course is developing an understanding of linear programming, which I previously thought was synonymous with optimisation. I can see now that regression would be considered an optimisation technique, in that you're trying to minimise the error.
My hunch was that the linear algebra course would be pretty useful, so I'm glad you have confirmed that.
That's a pretty cool example, but more often you will see objectives that are nonlinear functions of the arguments. The most obvious is y = x^2. What's the minimum? What about z = x^2 + y^2? What about z = (1 - x)^2 + 100*(y - x^2)^2? That last one is an interesting one (can you guess it from inspection?). You notice things get more interesting when you've got to minimise something like that rather than a standard linear function. Also, bounds no longer become strictly necessary (e.g. min of y = x^2 vs. min of y = x subject to x > -2).
Curve-fitting is quadratic optimisation because you're often looking for a curve that minimises the sum of the residuals squared. The residuals are the distances between the curve and the data points, and once you square them they all become positive anyway. If the curve hits them all, your objective is zero, otherwise it's some positive number that's hopefully not too large.
Finding a general solution to this sort of problem is still called "linear algebra", but the objective function isn't strictly linear. So the field of matrices and vectors extends far beyond linear programming.
If you hadn't noticed, it's something I'm interested in quite a lot!
I have found the minimum values of your functions, but not by inspection I'm afraid! (honestly, how would you do that with the last one? haha). I found a nice 3d function grapher.
So would it be correct to say:
If all constraints are linear, then it's a linear programming problem.
For linear constraints that are convex the objective function is easily minimised.
For linear constraints that are not convex, then we have increased complexity and clever algorithms are required to find a solution, if indeed the problem is soluble.
If constraints are non-linear, then we are no longer talking about linear programming, but perhaps we are now talking about 'convex optimisation of non-linear functions'.
I just watched an introductory Standford lecture on Convex Optimisation. Fascinating stuff. The professor suggested that linear programming was a nice follow-on topic after studying least squares regression and singular value decomposition. Going back to your original post, I think the starting point for all of these techniques is learning some linear algebra. Would you agree?
Thanks again for your enthusiasm and willingness to engage on this. It's great to develop a little knowledge.
Of course we're always talking about 2D functions here, but in reality your objective might depend on 20 or 5000 variables. That's why the geometry thought process is a good intro, but linear algebra is the right thing to take you forward.