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

  • $\begingroup$ What is $c$? Do you mean $w^Tx=\max w^Tx$? $\endgroup$ – joriki Jun 28 '11 at 4:58
  • $\begingroup$ @joriki yes, thats what i mean $\endgroup$ – AnkurVijay Jun 28 '11 at 5:00

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.

  • $\begingroup$ Does a convex optimization problem imply that the solution will be on one of the extreme point of the polyhedron ? Are you also suggesting that the solution is same irrespective of the relaxation ? Can this somehow be explained by the fact that extreme points are independent i.e. they cannot be described as a convex combination of other points from the polyhedron ? $\endgroup$ – AnkurVijay Jun 28 '11 at 6:47
  • 1
    $\begingroup$ 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. $\endgroup$ – trutheality Jun 28 '11 at 7:17

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.