Linear Programming 37: Interior point methods

[@leesweets4110]

Why are boundary solutions less desirable methods? Im not quite clear on that. Surely they can be solved in linear or quadratic time given that they can be written in matrix form and solved, such as with the tableau simplex method. Shouldnt it be easier to find sophisticated ways of dealing with degeneracy than to find interior paths? I see value in interior path methods (of polygonal feasible regions) only when the optimization function is itself non-linear.

[@HenryAdamsMath]

You are right, the standard methods to solve linear programming problems is to search for solutions on the boundary! For example, this is what the simplex method does. I am not an expert on this, but apparently there are some potential advantages of using interior point methods for large problems? Not sure. Also, interior point methods can be used to prove that linear programming problems can be solved in polynomial time, whereas the simplex method is exponential in the worst case. But, you are right, I think typically the fastest methods look for boundary solutions!

[@liujianlong-id9jp]

i like your style

[@HenryAdamsMath]

Thanks!