0
$\begingroup$

Is it necessary that the linear program

max { $w^Tx$ subject to : $x$ is a point on a given polyhedron }

attain its maximum at an extreme point of the polyhedron for any arbitrary w ?

Let $c$ = max $w^Tx$. The idea is that $w^Tx$ = c is a line in the hyperspace that touches the polyhedron at an extreme point

  • 0
    @joriki yes, thats what i mean2011-06-28

1 Answers 1

2

Yes. If you relax the constraint to be on or in the polyhedron it becomes a convex optimization problem, moreover the solution is always on the boundary, which means that it's on the polyhedron.

Some special cases are where an entire face of the polyhedron optimizes the function. There's also a degenerate case ($w=0$) where any point optimizes the function.

The Wikipedia article on linear programming briefly mentions this. It's one of the properties that the Simplex algorithm for solving linear programs relies on.

  • 1
    A convex optimization of a linear function implies that the solution will be on the boundary of the (convex) region described by the constraints. For polyhedrons it means that the solution will be an extreme point (or will contain an extreme point when the solution contains more than one point). It does follow from the fact that they are independent.2011-06-28