The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's say now that the objective function is not linear, but monotonically increasing in all the input variables. Let's take an example:

Minimize: $$e^x+e^y$$

s.t. $$A\vec{x} \leq \vec{b}$$

Where $\vec{x} = (x,y)$ and $A$ is a $n \times 2$ matrix.

Can we not say that the optima must still lie on one of the vertices?


No, we can't. Consider minimizing $e^x + e^y$ subject to $x+y=1$, $x, y \ge 0$. The minimum is at $(1/2,1/2)$ which is not a vertex.

The condition you want (for a minimization problem) is that the objective is a concave function.

  • $\begingroup$ Okay, so if we have a general concave objective function (not just linear), we can say that the optima must lie on one of the vertices of the simplex (assuming we have a bounded simplex)? And does this mean we can use the simplex method for such problems? $\endgroup$ – Rohit Pandey Mar 14 at 21:22
  • $\begingroup$ Yes and no. The reason there isn't a simplex method is basically that local information at one vertex (shadow prices etc) doesn't tell you what will happen at a neighbouring vertex. $\endgroup$ – Robert Israel Mar 15 at 1:11
  • $\begingroup$ In fact this kind of problem with a concave quadratic objective is known to be NP-complete, in contrast to linear programming which can be solved in polynomial time (though not by the simplex method). $\endgroup$ – Robert Israel Mar 15 at 1:24

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.