Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 ? –  AnkurVijay Jun 28 '11 at 6:47
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. –  trutheality Jun 28 '11 at 7:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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