3 ms·
It’s great result but probably not useful. Similarly to how interior point methods have better theoretical complexity than simplex for LPs, but fine tuned simp
by whatever1 3y ago
It’s great result but probably not useful. Similarly to how interior point methods have better theoretical complexity than simplex for LPs, but fine tuned simplex in reality almost always wins.
- geysersam 3y agoI never really understood that. Is there a commonly understood "reason" why IP methods are typically slower in practice? Seems going through the interior you'd quicker approach a good solution than when being confined to the boundary. But maybe that difference is less important in high dimensions.
- whatever1 3y agoCalculating derivatives is the most expensive and numerically challenging operation you do in optimization. Simplex circumvents these issues by traversing the edges of the polytope. Pivoting is very cheap and from practice we see that you are afforded a LOT of iterations before even start thinking about interior point methods.