Show that $\alpha_{1}x+\alpha_{2}y\geq \beta$ holds true for all points in $P\Longleftrightarrow$ the inequality is true for all extreme points in $P$

Question

Given a polyhedron, $P\subset \mathbb{R}^2$, I am to show that the inequality $\alpha_{1}x+\alpha_{2}y\geq \beta$ holds true for all $\binom{x}{y}\in P$, if and only if the inequality holds true for all extreme points in $P$.

The first part is rather simple, since the extreme points are part of the polyhedron, and therefore part of "all points in $P$", thus the inequality holds for the extremes aswell.

I am having trouble showing the other way around, that if the inequality holds true for all extreme points in $P$, it implies that it holds true for all points in $P$.

Bear in mind that it is still early on in the course, so we haven't learned many theorems and such to apply yet.

One of the things we have learned however, is that any bounded polyhedron is the convex hull of its extreme points, which I am unsure of whether I can use in this context.

Any help is appreciated.

score 1 · Answer 1 · answered Aug 30 '18 at 14:33

1

The inequality $\alpha_1x+\alpha_2y\geq\beta$ describes geometrically all points in the plane that lie on one side of the line $\alpha_1x+\alpha_2y=\beta$. If all extreme points lie on that same side, then since that side is a convex half plane, it follows that their convex hull also lies in that same half-space.

answered Aug 30 '18 at 14:33

uniquesolution

18,541

why not prove it by writing any point as a convex combination of extreme points? – LinAlg Aug 30 '18 at 19:58
One way or another you will need the convexity of the function $\alpha_1x+\alpha_2y$. I just prefer the geometric picture. – uniquesolution Aug 31 '18 at 05:37

Show that $\alpha_{1}x+\alpha_{2}y\geq \beta$ holds true for all points in $P\Longleftrightarrow$ the inequality is true for all extreme points in $P$

1 Answers1