4
$\begingroup$

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?

$\endgroup$

3 Answers 3

11
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Hmm, would you really call SLP a Simplex method? Plus, as you said, SLP works based off of linear constraints, which is something to keep in mind. $\endgroup$
    – Richard
    Commented Feb 4, 2022 at 14:31
  • $\begingroup$ @Richard I am not calling SLP a Simplex method. But as an Active-Set method, it is an extension of the Simplex method to Nonlinear Programs. BTW, I'm not a fan of SLP, because linear objective functions can't very well capture behavior of nonlinear objective functions relative to optimization. I am a fan of SQP, having used it successfully on many problems. and as building block for higher level algorithms. $\endgroup$ Commented Feb 4, 2022 at 14:51
  • $\begingroup$ I agree with your assessment regarding SLP and SQP, I have made similar experiences. $\endgroup$
    – Richard
    Commented Feb 14, 2022 at 14:07
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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