# Does max { $w^Tx$ subject to $x$ is a point on a given polyhedron } optimize at an extreme point?

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

• 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

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.