Consider a linear programming problem. Is it possible for an optimal solution to exist, but not at an extreme point? According to Bertsimas & Tsitsikalis ("Introduction to Linear Optimization", Athena Scientific, 1997), yes... and no. I'd appreciate help in reconciling the contradiction and resolving the matter.

On the one hand, on page 75, we find that

If the feasible set is unbounded, there are the following possibilities:

(i) There exists an optimal solution which is an extreme point.

(ii) There exists an optimal solution, but no optimal solution is an extreme point. (This can only happen if the feasible set has no extreme points; it never happens when the problem is in standard form.)

(iii) The optimal cost is $-\infty$.

So if the feasible set is unbounded, it is possible for a non extreme point to be an optimal solution. The answer to my question is therefore: Yes. But... this is only possible as long as the problem is not in standard form. However, on page 5 we learned that

A general linear programming problem can be transformed into an equivalent problem in standard form.

So it must be that after transforming the problem into an equivalent one in standard form, the non extreme, optimal point becomes an extreme point. But this is impossible, since, according to page 75,

An interesting aspect of the material in this chapter is the distinction between geometric (representation independent) properties of a polyhedron and those properties that depend on a particular representation. In that respect, we have established the following:

(a) Whether or not a point is an extreme point (equivalently, a vertex, or basic feasible solution) is a geometric property.

Confused? So am I!

  • 1
    $\begingroup$ I would offer you the example $$\min_x f(x) := 0.$$ There are plenty of non-extremal optimal points for that objective. $\endgroup$ – Jeff Snider Mar 12 '14 at 18:22
  • $\begingroup$ @JeffSnider: What is the standard form of this problem? $\endgroup$ – Evan Aad Mar 12 '14 at 18:46
  • 1
    $\begingroup$ let $c=0$. Then the standard form is $$\max_x \{ c^\top x \mid x \ge 0 \}.$$ $\endgroup$ – Jeff Snider Mar 13 '14 at 14:45
  • $\begingroup$ @JeffSnider: Thank you very much. Your answers helped me a lot! $\endgroup$ – Evan Aad Mar 13 '14 at 17:52

What I remember is that if the objective function is parallel to any part of the boundary that contains an extreme point, then any number on that boundary is also an extreme point.

Admittedly it has been a long time since I looked a linear programming though.

  • $\begingroup$ I'd still like to understand which one of the propositions I cited from the book fails. Is it the case that such problems, where the objective function is parallel to the boundary, can't be converted to standard form? Or, if they can, is the standard form lacking any extreme points? $\endgroup$ – Evan Aad Mar 12 '14 at 19:21

As per Jeff Snider's comment, $$ \min_{x \in \mathbb{R}} f(x) := 0 $$ is an example of an LP problem that has an optimal value, namely $0$, which is obtained at every point of its feasible set $\mathbb{R}$, but no feasible point is an extreme point.

The standard form LP problem $$ \max_{x \geq 0} 0x $$ is equivalent to the original problem. However, now the optimal value is obtained at an extreme point, namely $0$.

There is no contradiction between the three quotes OP (=me) cited in the original post, because saying that two LP problems are equivalent does not mean they have the same feasible set, it just means they have the same optimal value, if any (in particular, if one problem is feasible, so is the other one).

An extreme point is independent of the representation of the feasible set as long as it's the same feasible set, but if an equivalent problem has a different feasible set, then the problems may have different extreme points.


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.