Have we understood the limitations of the Simplex method on nonlinear programs?

Question

We are always told that the Simplex Algorithm is meant for solving linear equations with linear constraints.

But how badly would the Simplex Algorithm perform if we implemented it on a typical non-linear problem that is better suited for algorithms such as the Interior Point Method?

For instance, the Simplex Algorithm "scans" different vertices on the exterior surface made by the intersection of all equations and constraints - I am not sure if the surface made by non-linear equations and non-linear constraints would even have vertexes?

For argument sake, if someone insisted on using the Simplex Algorithm on a non-linear problem, would this fail instantly? Or could it still in theory return an acceptable answer, but it would be unlikely that this answer was the true optimal?

Answer 1

Extension of the Simplex Method to Nonlinear Programs having linear or linearized constraints is called an Active Set method. Sequential Linear Programming (SLP) and Sequential Quadratic Programming (SQP) are notable examples of such methods, which move around vertices of the constraints, rather than cutting through the interior, as Interior-Point Methods (IPM) do. Well-implemented SQP can be more numerically robust and may be faster than IPM on many problems.

Active Set methods applied to Quadratic Programming are sometimes referred to as Simplex, even though they are not exactly the same as the Simplex Algorithm applied to Linear Programs. The first such published algorithm is "The Simplex Method for Quadratic Programming", by Philip Wolfe, Econometrica, Vol. 27, No. 3, July 1959, pp. 382-398

Answer 2

There are two points to this:

• The convergence of the Simplex algorithm relies on the fact that an optimal solution can always be found in a vertex. This does not hold for non-linear problems (consider e.g. $\min x^2$ with $x \in [-1,1]$). If an algorithm cannot converge, how would this then work in practice?
• The power of simplex is based on solving sets of linear equations. But if the problem is non-linear, then you have to solve sets of non-linear equations which is problematic from a computational, algorithmic and numeric standpoint.

So in my opinion using Simplex out of the box will not work. You could argue that you can always construct a linear inner or outer McCormick relaxation such that Simplex becomes usable again, but this will not compete with a well-written Interior Point method.

Answer 3

Besides the useful answer of Richard, solving the non-linear equation/constraint by Simplex came back which non-linear terms you have faced in your problem. For example, multiplication of the variables are fallen in the non-linear class problems, but many of them can be reformulated as a MILP model which might be solved by the Simplex algorithm. I think it might be applied to the MINLP class, at least theoretically, by linear relaxation of the integer term.