Hello everybody. Welcome back to our Linear Programming unit. Today, we're going to talk about convex polytope. In particular, we're going to try to understand what the solution set to the system of linear inequalities that we need to deal with actually looks like. So remember, in a Linear Program we're trying to Optimize a linear function subject to a bunch of linear inequality constraints. Today, we're going to ask the question, what does the region of points defined by these inequalities actually look like? For example, this factory example that we looked at way back at the beginning. If you look at the set of solutions to these five inequalities, you got this nice trapezoid here. So the question is, what did things look like in general? Well, another example, if you look at the system were x, y and z and three dimensions were all between zero and one. You've got the unit cube. And in general, you get much more complicated looking regions. But you'll always get what's called convex polytope. And don’t worry will unrule these meaning as we go. So the first thing to know is what is a single linear equation? Well if you look at the linear equality, it defines a Hyperplane, infinite flat surface. Now, if instead you want an inequality it gives you what you call a halfspace. It gives you a Hyperplane and everything on one side of that Hyperplane. So if we want the solutions to a system of linear inequalities, we have a thing defined by a bunch of halfspaces, we want the intersection of all these of halfspaces. We want everything that's inside of all them. We want to solve all of the equations. And so, we sort of get a thing that's defined by these Hyperplanes. In fact, what we'll always get is a Polytope, that's a region in Rn that's bounded by finitely many flat surfaces. But, in fact, Polytopes have a little bit more structure than that. If you think about the cube, not only do we have the six faces but these faces intersect at edges and those intersect at vertices. And so, a polytope in general will have these, surfaces may intersect at lower dimensional facets like edges but perhaps some other dimensions, with the zero dimensional facets are called vertices. But it turns out that not every polytope is actually possible as a solution, a set of solutions to such a system of linear inequalities. For example, the donut pictured here is a polytope. But it's not a system solution to one of these systems. Because if you look at some of these inward pointing faces. Well, these faces lie in a Hyperplane. But you've got portions of your region on both sides of that Hyperplane. Whereas, if you have a polytope defined by one of these systems of linear inequalities. Each bounding Hyperplane is actually coming from one of those linear inequalities. And you can only have points on one side of that Hyperplane or the other. So you have this extra condition that everything must be on only one side of each face. And that leads us to the condition of Convexity. A region C and Rn is called convex, if for each pair points x and y and C. The line segment connecting x and y is entirely contained in their regions. So the Lemma is that any intersection of halfspaces or site of solution to this systems is convex. And the Proof is not that hard. Our system is defined by Ax at least b. We need to show that if two points, x and y, are in this set, then everything on the segment contained between them is also in the set. Well, the lines that way you can parameterize is points of the form (tx + (1- t)y) where t is a real number between 0 and 1. So the fast of that point is in our set, we take A (tx + (1- t) y) = tAx + (1- t) Ay, since x and y are in the set, that's at least tb + (1- t) b which is b. And so, every point in the line segment is in our set so the set is convex, great. So the Theorem is the region defined by a system of linear inequalities is always a convex polytope which is nice. So to reveal, we've got three pictures here. Which of these three regions, A, B, C is a convex polytope? Well, it turns out only B is. So A is not convex because we have these line segments here with the end points are in A but some of the points the middle arc. C is not a convex polytope because there's this region of the boundary here that sort of a curved region whereas if were a polytope, all that bound your regions would have to be straight lines. B on the other hand, is actually a convex polytope. Okay, so to conclude this lecture, we're going to actually prove a couple of important Lemmas about convex polytopes. So the first one is Separation. If you have C to be, in fact, any convex region, and x is a point not in C. Then it turns out there's always a hyperplane H that separates x from C, where x is on one side and C is on the other. Now, if C is given by a system of liner inequalities. This is actually easy to prove because if x isn't in C violates one of these defining inequalities, and that inequality gives you a hyperplane where C is on one side and x is on the other. But in general, you can prove this as well, you start with x, we're going to let y be the closest point in C to x. And it turns out you can just take the perpendicular bisector of xy or the hyperplane of points equidistant between x and y. Now, this is clearly a hyperplane to show that it separates x from C. Well, suppose that there were some point z and C that were on the wrong side of this hyperplane. Well, z and y are both in C, so everything on line segment between z and y is also in C. But you can show that there's actually always a point on this segment zy, that's closer to x than y was. And this is a contradiction because by assumption y was the closest point in z to x, and we just found a closer one. So that completes it. Okay, so the other Lemma is about polytopes. Suppose, that you have a polytope and there's a linear function on this that you're trying to minimize or maximize. The claim is that it takes its minimum or maximum values on vertices. This is clearly relevant to our linear program because we're exactly trying to minimize and maximize linear functions on this convex polytopes. So, we saw this in it's original factor example with the maximum was at this vertex and turns out that happens in general. Now, to maybe get some intuition for why this is true. We've got our polytope and it's, this polytope is sort of spanned by the corners, it's got corners and like things in between these corners. But because we have linear functions like the things in between the corners are never as good as the extreme points and so the optimum must be at the corners. Now, to actually prove this the thing to note is that you have a linear function to find on a line segment. It always takes extreme values at the two end points. And we're going to use to sort of push our points toward the corners and let the values get bigger and bigger. So we start at any point in our polytope and what you do is you draw a line through it. And you'll note, that the biggest value that our linear function takes on this line comes all the way over to that line hits an end of the polytope. So it takes an extreme point at the endpoint of that line which is on the face of your polytope. Now, once you're on the face or some facet, you can repeat this. You draw a line through that point and what you know is that the extreme values will be at the end points of this line and that lets you push it to a lower dimensional facet. And you keep doing this until you end up at a vertex. And so, we start at any point and we kept going until we hit a vertex. And that vertex has at least as large a value as the point we started. And so, the maximum values must be attained at some vertex. So in summary, the Region defined by a linear program is always convex. The Optimum of this linear program is always attained at a vertex. And finally, if you have a point that's not in the region, you Can always separate it from points on the inside by an appropriate hyperplane. So these are some basic facts about linear programs and their solution sets. Come back next time, we'll talk about another interesting property of linear programs called duality.