This is an idea called extreme points, of which is important. That's first rigorously defined extreme points. Previously our ideas about extreme points is that, well, it's something like a corner, but the mathematically we need a formal definition. It's Here. If I give you a set S, which may be in the n-dimensional space, a point or a vector is an extreme point if there does not exist a three tuple x_1, x_2 and the lambda such that your x_1 is in the set, x_2 is in the set, and x may be combined by x_1 and x_2. Here, the combination is pretty much some linear combination. You multiply your x_1 by lambda and x_2 by one minus lambda. Then because we restrict your lambda to be within 0-1, so we say this is a convex combination. Is a special type of linear combination, is a convex combination. If your x may be the convex combination of two other points that is also in S and of course x_1 and x_2 should not be x. Then we say x is not an extreme point. That would be weird, so let's take a look at examples immediately. This point here looks like a corner and then this is an extreme point. Why is that? Because there's no way for you to find two points such that the line segment covers your target points. If you want to do that, your two points must lie outside your set. At least one of them must do that, must be outside the set, so that's impossible. But if you take a look at any point inside your set, then you may find two other points in the set such that the line segment covers your original target point. For any point lead these on edge but not a corner. This is also possible. All those edge points, they are not extreme points, only those corner points are extreme points, that's example one. For example two here, this point, that point, of course they are all corner points. If you take a look at the definition, they are all extreme points. The interesting thing is that if you take a look at any point that lies on the boundary of the circle, you may also realize that its impossible for you to find two points such that they are in the set and the lie sigma may touch your original target point. Again, this is impossible in this example. All those edge points or boundary points along this half-circle is also an extreme points. In the last example here we have four extreme points. I hope that makes sense, and the one thing we want to remind you is that this point, this one also looked like a corner. But because you may find two points that their line segment touch your original point, so this green point is also not an extreme point. I hope that is clear. The reason to talk about extreme points is the following. For any linear program, we actually may prove that if there is an optimal solution, then there is an extreme point optimal solution. The intuition was mentioned in the past. If you have a linear program, something like this, then once you want to solve it with your graphical approach, you would keep pushing until you hit some boundary or corners. That's the definition of that extreme point. That is how the definition may help us. We now may say this particular thing is true in the n-dimensional space, and whatever the linear program you have, we are able to show you that we only need to focus on extreme points. One thing to remind you is that this is not saying that if a solution is optimal, then it is an extreme point. That's not always true. Because if you look at this linear program, and then suppose all the points here are feasible and optimal. That's possible, if you are moving towards this direction, then along that particular edge, this point is optimal. This point's optimal, but it is not an extreme point. When you state proposition one, you need to be careful. The way to state it is that for any linear program, if there is an optimal solution, there is the extreme point optimal solution. This property is important and the last simplex method will be built according to this important finding. We will see that we will focus on extreme points, and what's really useful and what's really clever, is that for the simplex method, there is a way to describe extreme points just with algebras and equations. The definition of extreme point is geometric. But later we will show you how to algebraically, express extreme points. Then we will be able to have the foundation for simplex method.
