8 ms·

Which Simplex Method Do You Like?

22 points by luu 12y ago

raverbashing 12y ago
Interesting. I don't remember the exact steps of the Simplex method (and to be fair I remember only one matrix, but yeah, if you want the Dual you solve it again) I suspect there are still several methods that are solved in an "old way" and not optimized with most modern knowledge (in algorithmic and computing efficiency - like optimizing for cache)
1971genocide 12y ago
I am revising for my exam in two weeks and have been practising the tabulaue method for a month now ! Not sure if I should read this and and get confused since I want to make sure to get good grades.
- repsilat 12y ago
  Maybe wait until after your exam :) The tableau method is in some sense the "bubble sort" of simplex algorithms. It's simple, it works and it's easy to explain, but it's not something anyone would use in practice. That said, if you're not going to actually be implementing these things (and few people are), it's more important early on to get practice reducing problems to linear and integer programs than to know exactly how they're being solved.
  - 1971genocide 12y ago
    Makes sense ! The tableau method when it was first introduced didn't seem like conventional linear algebra. I found it odd though that we learnt machine learning topics BEFORE we learnt optimization theory. You would think that optimization theory would be taught before anything in Machine Learning. I found many topics in machine learning to be really opaque and it seemed it was just "try this model" without having a deep understanding of the mathematics or the reasoning behind them. I think its because of all the media hype surrounding ML and my peers thinking its "cool". Linear, Integer, and non-linear and dynamic programming really does fill that gap between conventional linear algebra and many of the topics in ML. I wish optimization theory was taught and emphasized more widely since its such an amazing topic.
    - repsilat 12y ago
      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.
  - TeMPOraL 12y ago
    > Maybe wait until after your exam :) Probably a wise advice, though I'd personally jump right to reading :). I hate confusion, when I notice it I read and learn until it goes away. It takes time and may hurt grades in the short term, but then again I found out first-hand that really grokking things can enable you to just talk your way into good grades on labs and oral exams ;).
bjornsing 12y ago
I was taught the variant with two linear systems at each step. I don't remember the exact details, but the general concept of a "dual to the problem" made an impression on me.
deleted 12y ago
[deleted]
larrydag 12y ago
When I learned the simplex methond in my Engineering classes I had to perform it by hand for exams (only a couple steps or to get an updated matrix). The tableau method was easy to write out and learn. Yet for solution computation in the practical world it is very computationally expensive. I would solve in matrix form as the author suggests since linear algebra has come a long way since then. Another note is that the simplex method is just one aspect of solving optimization problems. Most computation solvers now use a series of heuristics to get a "close enough" solution than perform either a simplex or gradient descent approach to get a final solution. For those that want to know more about this research I highly recommend the field of Operations Research. https://www.or-exchange.org/ https://www.or-exchange.org/ is a good Q&A site for detail.

22 points by luu 12y ago

Interesting. I don't remember the exact steps of the Simplex method (and to be fair I remember only one matrix, but yeah, if you want the Dual you solve it again) I suspect there are still several methods that are solved in an "old way" and not optimized with most modern knowledge (in algorithmic and computing efficiency - like optimizing for cache)

1971genocide 12y ago

I am revising for my exam in two weeks and have been practising the tabulaue method for a month now ! Not sure if I should read this and and get confused since I want to make sure to get good grades.

repsilat 12y ago
Maybe wait until after your exam :) The tableau method is in some sense the "bubble sort" of simplex algorithms. It's simple, it works and it's easy to explain, but it's not something anyone would use in practice. That said, if you're not going to actually be implementing these things (and few people are), it's more important early on to get practice reducing problems to linear and integer programs than to know exactly how they're being solved.
- 1971genocide 12y ago
  Makes sense ! The tableau method when it was first introduced didn't seem like conventional linear algebra. I found it odd though that we learnt machine learning topics BEFORE we learnt optimization theory. You would think that optimization theory would be taught before anything in Machine Learning. I found many topics in machine learning to be really opaque and it seemed it was just "try this model" without having a deep understanding of the mathematics or the reasoning behind them. I think its because of all the media hype surrounding ML and my peers thinking its "cool". Linear, Integer, and non-linear and dynamic programming really does fill that gap between conventional linear algebra and many of the topics in ML. I wish optimization theory was taught and emphasized more widely since its such an amazing topic.
  - repsilat 12y ago
    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.
- TeMPOraL 12y ago
  > Maybe wait until after your exam :) Probably a wise advice, though I'd personally jump right to reading :). I hate confusion, when I notice it I read and learn until it goes away. It takes time and may hurt grades in the short term, but then again I found out first-hand that really grokking things can enable you to just talk your way into good grades on labs and oral exams ;).

bjornsing 12y ago

I was taught the variant with two linear systems at each step. I don't remember the exact details, but the general concept of a "dual to the problem" made an impression on me.

deleted 12y ago

[deleted]

larrydag 12y ago

When I learned the simplex methond in my Engineering classes I had to perform it by hand for exams (only a couple steps or to get an updated matrix). The tableau method was easy to write out and learn. Yet for solution computation in the practical world it is very computationally expensive. I would solve in matrix form as the author suggests since linear algebra has come a long way since then. Another note is that the simplex method is just one aspect of solving optimization problems. Most computation solvers now use a series of heuristics to get a "close enough" solution than perform either a simplex or gradient descent approach to get a final solution. For those that want to know more about this research I highly recommend the field of Operations Research. https://www.or-exchange.org/ https://www.or-exchange.org/ is a good Q&A site for detail.