5 ms·

A lot of people are suspicious of integer programming because it's NP-hard, and there can a bit of wizardry involved in formulating a problem well. It doesn't h

A lot of people are suspicious of integer programming because it's NP-hard, and there can a bit of wizardry involved in formulating a problem well. It doesn't help that the mainstream solvers are black-boxes packed to the brim with their own peculiar heuristics. I definitely agree that it's undersold, though. Nonlinear programming I'm a bit more suspicious of, but mostly because I have a lot less experience with it. Dynamic programming, on the other hand, I don't think should be taught in the same way at all -- to me it's something in the algorithmic toolbox, slightly less vague than "divide and conquer", mostly just a way of thinking and approaching problems. It's incredibly useful once you "get it", but I don't trust anyone who tries to systematize it by trying to reduce it all down to Markov decision processes and the Bellman equation. Maybe I can get behind someone saying "Dynamic programming is upside-down memoization," though. In some sense all of these should "come before" machine learning because they're often used in particular machine learning algorithms. On the other hand, most ML pedagogy is at a higher level than all that, so maybe it's not needed so much.

1971genocide 12y ago
The we are learning is seems like a natural extension of multi-variable calculus and PDEs. As if what happens when you have hundreds of variables ? What tools do we turn towards ? The thing is for example in ML the standard solution is to use gradient decent, but what I learnt is depends highly on the type of equations you are dealing with. The first tool should never be a hammer. We used stochastic gradient decent on linear machine tasks ! Now after learning optimization theory it seems like madness. The thing is whenever you introduce unnecessary complexity you pay technical debt. Occam's razor is really important when you are dealing with modelling.
jules 12y ago
Convex optimization is very robust and the algorithms are easy. In fact it is far easier to implement a good interior point method for linear programming than implementing a good simplex method. Sadly in most schools they only let students solve tons of linear programming problems by hand by the tableau method. It's incredibly boring and frustrating and students don't learn anything.
- wolfgke 12y ago
  Interior point methods become ugly if the feasible region is not full-dimensional. Then you have to find the affine hull, find a base of the affine hull, project down etc. For all these steps you have to pay attention to the numerics etc. Not nice. So I think (working in mathematical optimization, but not on interior point methods) implementing a good interior point method is only considered easy because you usually don't care about these ugly parts. The simplex algorithm is less problematic since the only ugly situation that (you could imagine) occur here is that the polyhedron has a non-trivial lineality space (thus has no vertices). But this can't happen since at the beginning the simplex algorithm converts the polyhedron into A x = b, x >= 0^n form and this class of polyedra is pointed as you can prove easily. Even in the nice case interior point methods are only nice as long as you are interested in the optimum value. As soon as you also want properties from polyhedral combinatorics for your solution (say: a feasible base), interior point methods become really ugly, especially if the face where the optimum value is attained is not just a vertex. Disclaimer: I'm working in mathematical optimization, but not on interior point methods.
  - jules 12y ago
    What do you mean by a not full dimensional feasible region? Interior point methods can handle equality constraints just fine, so do you mean two inequality constraints that conspire to be an equality? I think any method that uses inexact arithmetic will have trouble with that. The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. That's why in my opinion courses that teach simplex but not interior point are outdated. With interior point you simply get far more usefulness in fewer lectures, so if you have to make a choice, make it interior point.
    - wolfgke 12y ago
      > so do you mean two inequality constraints that conspire to be an equality? Exactly. This can be solved by the described method (but there are probably better ones). > The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. I would not argue with broader applicability, if adding a constraint after finding an optimal solution requires a complete new fresh start (the dual simplex algorithm doesn't have this problem). This is very important for cutting plane algorithms for solving (mixed-)integer linear programs.

1971genocide 12y ago

The we are learning is seems like a natural extension of multi-variable calculus and PDEs. As if what happens when you have hundreds of variables ? What tools do we turn towards ? The thing is for example in ML the standard solution is to use gradient decent, but what I learnt is depends highly on the type of equations you are dealing with. The first tool should never be a hammer. We used stochastic gradient decent on linear machine tasks ! Now after learning optimization theory it seems like madness. The thing is whenever you introduce unnecessary complexity you pay technical debt. Occam's razor is really important when you are dealing with modelling.

jules 12y ago

Convex optimization is very robust and the algorithms are easy. In fact it is far easier to implement a good interior point method for linear programming than implementing a good simplex method. Sadly in most schools they only let students solve tons of linear programming problems by hand by the tableau method. It's incredibly boring and frustrating and students don't learn anything.

wolfgke 12y ago
Interior point methods become ugly if the feasible region is not full-dimensional. Then you have to find the affine hull, find a base of the affine hull, project down etc. For all these steps you have to pay attention to the numerics etc. Not nice. So I think (working in mathematical optimization, but not on interior point methods) implementing a good interior point method is only considered easy because you usually don't care about these ugly parts. The simplex algorithm is less problematic since the only ugly situation that (you could imagine) occur here is that the polyhedron has a non-trivial lineality space (thus has no vertices). But this can't happen since at the beginning the simplex algorithm converts the polyhedron into A x = b, x >= 0^n form and this class of polyedra is pointed as you can prove easily. Even in the nice case interior point methods are only nice as long as you are interested in the optimum value. As soon as you also want properties from polyhedral combinatorics for your solution (say: a feasible base), interior point methods become really ugly, especially if the face where the optimum value is attained is not just a vertex. Disclaimer: I'm working in mathematical optimization, but not on interior point methods.
- jules 12y ago
  What do you mean by a not full dimensional feasible region? Interior point methods can handle equality constraints just fine, so do you mean two inequality constraints that conspire to be an equality? I think any method that uses inexact arithmetic will have trouble with that. The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. That's why in my opinion courses that teach simplex but not interior point are outdated. With interior point you simply get far more usefulness in fewer lectures, so if you have to make a choice, make it interior point.
  - wolfgke 12y ago
    > so do you mean two inequality constraints that conspire to be an equality? Exactly. This can be solved by the described method (but there are probably better ones). > The very nice feature of interior point methods is that they also work for non-linear optimization, which has far broader applicability. I would not argue with broader applicability, if adding a constraint after finding an optimal solution requires a complete new fresh start (the dual simplex algorithm doesn't have this problem). This is very important for cutting plane algorithms for solving (mixed-)integer linear programs.