1
$\begingroup$

I was revising my notes from an optimization class I did a few years ago. After reading a bit, I started questioning myself about the benefit of using Simplex over other optimization methods.

The Simplex method has an exponential or polynomial complexity in the worst case. This makes it be quite slow to solve real problems in a normal computer (as I have verified myself). Also, this method can only be applied to linear problems, which is a small subset of all the possible problems.

In the other hand, other methods like Lagrange/KKT multiplier method seems much less restrictive. At the same time, when I checked the steps to get the optimal point using this methods, they seem quite simple:

  1. Calculate the Lagrangian $\mathcal{L}(x_{1},..,x_{n},\lambda_{1},..,\lambda_{l},\mu_{1},..,\mu_{k})$
  2. Solve $\vec{\nabla \mathcal{L}} = \vec{0}$
  3. Check conditions

Now my question is, why would you use Simplex over KKT? The later seems faster and less restrictive. Is there any case where Simplex can be used and KKT not?

You could argue that it can be difficult to solve the equation system in step 2, but, is it for a computer? Considering a linear problem, it can be solved using matrices. Or, is any of the steps in KKT more difficult than solving a Simplex problem that may require millions of iterations to finish?

I have the feeling I am missing something or misunderstanding these methods but I can't find what's wrong in my reasoning.

$\endgroup$
  • 1
    $\begingroup$ Very brief answer: yes, the equation in step 2 (which comes together with some more condition in KKT) is very hard to solve, it is non-linear due to the complementary slackness condition. An alternative algorithm to Simplex is the primal-dual interior point method. It is exactly designed for solving the KKT system (the equation 2 and some more). However, there is no clear practical benefit of the latter compared to the Simplex. It may be one faster or another, depending on a problem (and implementation). $\endgroup$ – A.Γ. Nov 7 '19 at 16:53
  • 1
    $\begingroup$ Some reasons to use simplex are: 1) it returns a basic solution (a vertex) 2) it is much cheaper to warm-start and hence more efficient if you are solving zylions of problems that differ very little, like for example in a mixed-integer optimizer. $\endgroup$ – Michal Adamaszek Nov 10 '19 at 19:37
  • $\begingroup$ @A.Γ. If you consider a linear problem and a subset of active restrictions while solving KKT, then the system of equations is always linear, right? Because either the KKT multiplier or the restriction must be zero in this case, which means the system keeps being linear. I think this is not true in the interior point method because the complementary slackness condition changes from being equal to 0, to being equal to $\mu$. Am I correct? $\endgroup$ – Martín De la Fuente Nov 11 '19 at 5:59
  • 1
    $\begingroup$ @MartínDelaFuente You are right. The obstacle here is that the number of combinations of active sets grows way too fast compared to the number of constraints. Simplex is doing much better. BTW there is a method called active set method in optimization. $\endgroup$ – A.Γ. Nov 11 '19 at 8:11
2
+50
$\begingroup$

Let me restrict myself to linear problems, because for nonlinear problems you cannot choose the simplex method.

Although the simplex method has exponential complexity in the worst case, in practice it is still quite fast on most real world problems. That is mostly due to the spectacular improvements made by CPLEX and Gurobi in their simplex implementation. The paper A Brief History of Linear and Mixed-Integer Programming Computation by Robert Bixby (the last two letters in Gurobi) provides a good overview of the historic developments.

Solving $\vec{\nabla \mathcal{L}} = \vec{0}$ only works if you have equality constraints and if the variables are not restricted in sign. To solve a linear optimization problem in standard form: $$\min\{c^Tx : Ax \geq b, x\geq 0\},$$ what you need to solve are the KKT conditions: $$Ax \geq b$$ $$A^T y \leq c$$ $$y^T(Ax-b)=0$$ $$x\geq 0, y\geq 0.$$ In other words, you need to find a pair $(x,y)$ where $x$ is feasible to the primal problem, $y$ is feasible for the dual problem, and the complementary slackness (CS) condition $y^T(Ax-b)=0$ is satisfied. That is by no means easy! What interior point methods do is replace the CS condition with $y^T(Ax-b)=\mu$ and solve the problem iteratively while gradually letting $\mu \downarrow 0$. Whether that has an advantage compared to the simplex method depends on the structure of $A$. Interior point methods are fast when $AA^T$ is sparse, and the rows/columns can be permuted in a way that its Cholesky factor is also sparse.

In practice it is also important to detect infeasible or unbounded problems. To do that, interior point methods often solve the homogeneous model. The paper The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm. by Andersen & Andersen shows how solving the homogenous model reveals ill posed problems.

The running time of an interior point method is very predictable, but that of the simplex method is not. Therefore, if you run CPLEX or Gurobi with their default settings, they actually run the simplex method and the interior point method in parallel, and terminate as soon as one method finds the optimal solution.

$\endgroup$
  • $\begingroup$ Thank you very much, especially for mentioning how software implementations work. The way you present the KKT conditions are quite unfamiliar to me and that left me a bit confused. I am more used to this notation. Anyway, I was studying these methods more in depth and I think I understood the idea. Now, just to check I am getting this right.. $\endgroup$ – Martín De la Fuente Nov 8 '19 at 22:48
  • $\begingroup$ (1) In KKT worst case (with inequality contraints) you have to solve the system of equations given by every option in the power set of the restriction set (i.e. for every possible subset of active restrictions). That makes it exponential in the number of restrictions. Is this correct? (2) In the case of the lagrange method, where there are no inequality contraints, then to find the optimal value you only need to solve a single system of equations. Thus, we can say it is more convenient than Simplex in this case. Is this correct? $\endgroup$ – Martín De la Fuente Nov 8 '19 at 22:48
  • 1
    $\begingroup$ @MartínDelaFuente the KKT conditions on Wikipedia are the same. Take $f(x) = c^Tx$, $g_1(x) = b-Ax$, $g_2(x) = -x$, then the stationarity condition is $c - A^T\mu_1 - \mu_2 = 0$ which simplifies to $c - A^T\mu_1 \geq 0$ because $\mu_2 \geq 0$. To answer your questions: (1) yes, but surprisingly interior point methods converge to the optimum by decreasing $\mu$ without exploring the power set, (2) you are right, but in that case the original linear optimization problem is extremely simple already. $\endgroup$ – LinAlg Nov 9 '19 at 1:04

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.