14
$\begingroup$

As I understand it, since a solution to a linear program always occurs at a vertex of its polyhedral feasible set (if a solution exists and the optimal objective function value is bounded from below, assuming a minimization problem), how can a search through the interior of the feasible region be better? Does it converge faster? Under what circumstances would it be advantageous to use simplex method over interior point methods? Is one easier to implement in a code than the other?

$\endgroup$
  • $\begingroup$ One of your statements is incorrect. The solution to a convex optimization problem does NOT always occur on the boundary. Take, for instance, $\min_{x \in [-1, 1]} x^{2}$, where the optimal solution occurs at $x = 0$, which is in the interior of the feasible region. Also, outside the context of linear programming, the simplex method generally refers to the Nelder-Mead simplex method, which may not even converge to an optimal solution in dimension greater than 1. This method is not recommended for convex programming. Please edit your question for clarity and correctness. $\endgroup$ – Geoff Oxberry Jan 15 '12 at 4:00
  • $\begingroup$ Would it be more appropriate to say "linear optimization" instead of "convex optimization"? $\endgroup$ – Paul Jan 15 '12 at 4:07
  • $\begingroup$ Yes, then your statement is correct. Thank you for editing your question. $\endgroup$ – Geoff Oxberry Jan 15 '12 at 4:11
  • $\begingroup$ The problem with the simplex method is it cannot be generalized to nonlinear problems, i.e. the majority of real world problems. $\endgroup$ – user4061 Apr 10 '13 at 0:56
17
$\begingroup$

Based on personal experience, I'd say that simplex methods are marginally easier to understand how to implement than interior point methods, based on personal experience from implementing both primal simplex and a basic interior point method in MATLAB as part of taking a linear programming class. The main obstacles in primal simplex are making sure that you implement Phase I and Phase II correctly, and also that you implement an anticycling rule correctly. The main obstacles in implementing an interior point method for linear programming tend to be more about implementing the iterative method correctly, and scaling the barrier parameter accordingly.

You can find a more complete discussion of the pros and cons of each algorithm in a textbook on linear programming, such as Introduction to Linear Optimization by Bertsimas and Tsitsiklis. (Disclaimer: I learned linear programming from this textbook, and took linear programming at MIT from Bertsimas' wife.) Here are some of the basics:

Pros of simplex:

  • Given $n$ decision variables, usually converges in $O(n)$ operations with $O(n)$ pivots.
  • Takes advantage of geometry of problem: visits vertices of feasible set and checks each visited vertex for optimality. (In primal simplex, the reduced cost can be used for this check.)
  • Good for small problems.

Cons of simplex:

  • Given $n$ decision variables, you can always find a problem instance where the algorithm requires $O(2^{n})$ operations and pivots to arrive at a solution.
  • Not so great for large problems, because pivoting operations become expensive. Cutting-plane algorithms or delayed column generation algorithms like Dantzig-Wolfe can sometimes compensate for this shortcoming.

Pros of interior point methods:

  • Have polynomial time asymptotic complexity of $O(n^{3.5}L^2\log{L}\log\log{L})$, where $L$ is the number of bits of input to the algorithm.
  • Better for large, sparse problems because the linear algebra required for the algorithm is faster.

Cons of interior point methods:

  • It's not as intuitively satisfying because you're right, these methods don't visit vertices. They wander through the interior region, converging on a solution when successful.
  • For small problems, simplex will probably be faster. (You can construct pathological cases, like the Klee-Minty cube.)
$\endgroup$
  • 2
    $\begingroup$ A good summary. Klee-Minty in fact seems to be designed to confound simplex LP methods... $\endgroup$ – J. M. Jan 15 '12 at 5:15
  • $\begingroup$ @J. M. Yes, that's exactly the point of it -- it is an explicit construction to show that simplex methods are not polynomial (although there are variants that make interior point methods cry, too). $\endgroup$ – Christian Clason May 7 '14 at 20:45
  • $\begingroup$ Thank you for this informative post. I wonder how many variables make the problem large? Dozens? Hundreds? Thousands? $\endgroup$ – KjMag Jan 8 '18 at 12:25
3
$\begingroup$

The answer is easy. They both (simplex and interior point methods) are a mature field from an algorithmic point of view. They both work very well in practice. The good reputation of I.P.M. (interior point methods) is due to its polynomial complexity in the worst case. That is not the case for simplex which has combinatorial complexity. Nevertheless, combinatorial linear programs almost never happen in practice. For very large scale problems, I.P. seems to be a bit faster, but is not necessary the rule. In my opinion I.P. can be easy to understand and implement, but for sure, someone else can disagree, and that is fine. Now, in L.P, if the solution is unique, it is definitely be in a vertex, (both I.P. and Simplex do well here as well). The solution also can be on a face of the polyhedron or on an edge in which case, the adjacent vertex is (or vertices are) also a solution (again, both I.P. and simplex do well). So they are pretty much the same.

$\endgroup$
  • $\begingroup$ I realize the example I gave was not a linear program; if you look at the revision history, an earlier version of this question asked to compare the simplex method and interior point methods for convex optimization problems. I gave a counterexample to justify the edits I made, and to encourage the original poster to correct his question, which he did. $\endgroup$ – Geoff Oxberry Jan 15 '12 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.