Ladies and gentlemen good morning or good afternoon or good evening.
we are moving to the third part of this class which is mathematical programming.
And this lecture is going to be the first part of that third part.
And that's going to be about linear programming.
Okay. So, linear programming what we are going
to do in the lecture is first find out what is a linear program, and then talk
about convexity and geometry. Okay, so let me give you the context
here. So, linear programming was invented by
George Dantzig in 1947, and it's one of the most fundamental truths in, in
combinatorial optimization. It's one of the growing, it has been a
growing area for, for decades. And actually, people are still working
very actively in this, and I, as I will told you, you know, there are still some
very interesting open issues in that area.
But the, the really important thing for us is that this is a really fundamental
tool for doing a lot of different things in optimization.
Okay. The other thing which is very nice in
linear programming is that you have, you have these two views.
You have the geometrical views. You have the algebraic view.
And they have beautiful connection between them.
So, we'll switch typically from, you know, the algebraic view to the
geometric, to the geometry view, and so on and so forth.
And today, mostly we'll talk about the geometry.
But the next lecture is going to be about linking the two things together, okay.
So, fundamental tools, beautiful connection between, you know, visual, you
know, geometrical intuition, and then the algebraic the algebraic, you know,
expressions of, of the problem. This is what a linear program is, okay?
So, what you see at the top is basically minimizing a linear objective function.
Okay? Subject to a set of linear inequalities,
okay? Now, one of the things that you have to
see here is that the variables will have to be non-negative, all of them.
So, in this expression, okay, so the x i are the variables, okay?
Real numbers. And the ci's, the ai's, and the bi's are
the constant. Okay.
So, in this particular expression, obviously you have n variables.
You have n constraints. Okay.
the variables, as I said, are non-negative.
They have to take, you know, a non-negative, you know, value.
Okay. And all the constraints here are
inequalities. Okay.
So, that's the basic form of a linear program.
Okay. So, when we think about linear
programming, we think about this. Okay, minimizing, you know, a set of a
linear objective function subject to a set of linear inequalities.
Okay, so, here are the answer. Can I maximize?
Yes you can. Okay, so the way you would do that is
simply by replacing the maximization of your linear objective by the negation,
the, the minus of that particular objective, and you will minimize that.
Okay? So, if you minimize, you know, minus your
objective function. Okay?
So you will a sense, in a sense, maximize.
So, if you want to maximize, just minimize and negate the entire, all the
coefficients of your objective function. Now, can a variable xi take both positive
and negative values? Can you actually represent that?
You can, okay? And here is how you do it.
You take variable xi, and everywhere inside your linear program, you replace
it by a difference of two variables. xi plus and xi minus.
Okay. So, essentially you take this term here
and you replace xi everywhere by that particular term, okay?
Now, where does it work? Okay.
So, both of these variables have to take the non-negative values.
Okay, that's the, you know, that's the linear programming does.
All the variables have to take non-linear, non-negative values.
But when you look at this difference, this difference can take both positive
and negative values. You want a positive value, give it to xi
plus. Okay.
And the other terms can be zero. You want a negative value?
Give a positive value to xi minus, a zero to xi plus, and you get a negative value.
Okay? So as, in a sense, they're easy, right?
So, you have a variable, it can take both positive and negative values.
What you do is you replace them by this term everywhere inside the linear
program. Okay?
Now, what if you have an equality constraint.
Very simple as well. You take that equations, you replace it
by two inequalities. Okay.
In one smaller equal, one greater equal, the smaller equal you can, you know, you
just transform it into a smaller equal as well.
And you have, essentially, an equation at that point.
Okay. So, very simple.
Okay. Now, what if my variable can take integer
value? That you can't do it in linear program.
Okay. So, this is something that we'll talk
about later in the class. Okay.
It's going to be what we call mixed teacher program.
But this not a linear program. And you'll see, there is a fundamental
difference between these two. Okay?
Now, what about, you know, if I have a non-linear constraint?
Okay? Well, what we are talking about here is a
linear program. It's not a non-linear program.
It's called a linear program for a reason.
We only want to have linear, you know, linear constraints and a linear objective
function. And, and that give me the opportunity to
tell you a story about George Dantzig, of course.
You know, when George Dantzig presented this, he was, you know, invented, you
know, linear programming, he was a graduate student.
And, you know, when he wanted to present these results, he went to this
conference, and there were plenty of, you know, big shot in optimization there.
And so, he presented this results. Okay, and then there was this big shock
in optimization, this big German guy with the big, deep voice, right.
And so, he stood up and said Mr. Dantzig, you very well know that the
world is non-linear. Okay?
And so, Dantzig was like shaking up a little bit, how am I going to answer that
questions. And then, you know, that particular
confront, [UNKNOWN], and you know, the genius in Computer Science and Applied
Mathematics and Mathematics in general, was there and he stood up and said
mister, you know, George Dantzig stated this axioms.
Okay. He told you when you can apply, you know,
the method. If you have a problem that [UNKNOWN] use
it, if your problem doesn't, don't use it.
And I think, you know, that was really classy and I'm sure, you know, George
Dantzig appreciate that a lot. Okay, so, essentially, no linear
constraints, no variable that can take integer value, that's outside the scope
of linear programming. Okay?
The rest here, you can express essentially, you know, the way you want.
Okay? Now, let me talk about geometry.
Right? So, we saw, we just saw the algebraic
form of what a linear program is. So, I want to took a little bit what this
means from a geometrical standpoint. So, I'm going to start with convex sets,
okay. And so, I gave you a couple of sets here,
okay, set of points like, you know, the points inside a circle, inside a square.
Inside this, you know, this kind of apple, you know, square where you know
the, the, the corner are rounded right, and then the spot is the star.
Okay. So, which one of these are convex set?
Okay. So, the intuition is very simple.
Take two points, draw a line between them, okay.
If all the points between these two, if all the points in the line between them
are inside the, the set, okay, that means that the set is convex.
Okay. This is convex.
Okay, we are happy, okay. So, this is the star I'm showing.
Let's take two points. Let's draw a line between them.
What you get? You know, there are some points here
which are all aside the set. Therefore, this is not a convex set.
Okay, not happy. Okay, now this is 2D.
2D is really boring, so let's move to 3D. Okay, and this is 3D.
Okay. So, you see this this field, okay.
It's a convex set, okay. You take the two points.
You draw a line between them. And look.
You know, whatever you look at it, okay. All the point in between these, all the
points in this lines are inside the convex set.
That's what the convex set is all about, okay.
So, let's move to the next one. Okay, here is the next one, you know,
okay? So you see this thing.
It looks like a convex set, right? But look at this line.
I've selected two points, I drew the line between them, I go to zip.
Whoops. You know, you see there, you see, you can
see clearly, you know, the line goes outside the, the set.
This is not a convex set. Okay?
So, beautiful thing here. Okay?
You can look, you know, you take two points, you draw a line between them,
it's outside a set, that's not a convex set.
Okay? So, this is once again, you know, the
geometric intuition. What I want to show you now is the
algebraic expression. Okay?
So, if you set up point v1 to a set of points v1 to vn, okay.
So, we will define the convex combinations of these points.
And the way you define these convex combination, and that's essentially the
points which are on this line, right. So, so that of course, an arbitrary
dimension. Okay.
So, what you do is you multiply, you multiply every one of these by these
Lambdas. Lambda 1, Lambda 2, Lambda n, if you have
n, you know, points. And, and that's going to be your convex
combination of all these points. v1 want to be n.
Provided, of course, that the sum of these Lambda is one and they are all
greater is equal to zero. Okay.
So, if I have an expression like this okay, and I make sure that all the
Lambdas are equal to 1. And all of them greater are equal to
zero, then I have a convex combination of all the points v1 to vn.
Okay. So, this is how I can define a convex
set. Okay?
So, why? Because essentially, now a convex set can
be defined in the following fashion. So you say a convex set, okay, a set
essentially is convex. If you take points of these things and
all the convex combination of the points that you have in the set are inside the
set. Okay?
So, basically take a bunch of points, okay, these points are going to be from
convex. If whatever, you know, convex combination
you take, those points are inside the set.
Okay? So, that's a convex set.
Now, so this is an interesting result that we're going to use all the time.
Okay, so essentially, you know, the intersection of a set, of convex sets,
okay, is itself convex. Okay?
And so is the proof. Okay?
So very, very simple proof. So, so let's, you know, let's denote by
this notation here, the intersection of all the set S i, okay, from 1 to n.
Okay? So, we take this intersection of all
these sets. Okay?
And, and, of all the set S i. So right, that you see.
And so, what are we going to do is we are going to consider, okay, a bunch of
points inside this intersection. Okay?
So, let's say v v 1 to v n are in, are the points inside that intersection.
Okay? So what it follows, obviously, because
they are inside the intersection, that basically means that they are inside
every one of the sets. Okay?
So the points inside a intersection, by definitions, are inside every one of
these sets, okay? Now, what do we know about the sets, we
know that the sets are convex, okay? So, essentially what that means is that
all the convex combination of these points are also in the set i, and that's
varied if it is S1, S2, S3 for all the sets right.
So now what do I know? I know that every convex combination of
these points are in every one of the sets.
And therefore, they are in the intersection of this set.
Okay? And, of the sets, and that, and that
means what? That means that essentially, all the
convex combinations of the points in that, inside the intersection are inside
the intersection. And therefore, the intersection is
convex, okay? Now why this is interesting?
Okay, so look, when we look at linear programs we have these inequalities,
right? And these inequalities, okay, so they are
basically representing half spaces, and these half spaces are convex.
You can prove that. Take the definition that I've shown you
before, and try to prove that this is convex.
And the proof is very simple, right? Three lines.
Okay? But you can prove, essentially, that
every one of these half spaces are convex.
And so, when you look at the linear programs, and the constraints of the
linear programs, what you have is essentially a bunch of these half spaces
that are defining the feasible region of the linear program.
And so, all of them, you know, are convex, and the intersection of them is
also convex. Okay.
And so, this is, this is called a polyhedron.
Okay. The intersection of all these half space.
And if it's this finite, that means it doesn't go to infinity in one of the
dimensions, it's called a polytope. Okay?
So, big idea here is what, you know, we are dealing with convex set.
Every one of these sets is, every one of these inequalities is basically defining
your convex set which is called a half space.
You have many of them, so for having a solution you have to study by all of
them. That means you have to be in the
intersection of all of them and I told you that a intersection of a set of
convex set was convex, And therefore, we know that the intersection of these
things is going to be convex. Okay?
So, let's look at these things a little bit geometrically, right?
So, this is this is a hyperplane, okay? So, this is hyperplane, and that define,
you know, a half space. And let's assume that, you know, we are
looking at the solution on this side. That's part of our feasible region.
Then, I can take another one. Right?
So I take another half space. Okay?
And I, you know, refine my feasible region, and the little guy over there,
that's called a vertex. Okay?
And you're going to see today, I'm going to really be obsessed with these
vertices. Okay?
But that's another one. I can take another one, and then the
colors are getting uglier and uglier, and uglier, but I'm getting those
intersection of the set. Actually I don't really know in there,
you know, ugly because I'm colorblind, I don't see anything here, but anyway I was
told that they are really ugly. So we are not going to represent them,
we're going to represent the feasible region like this.
So this is essentially all of my upper planes.
They are defining half place, half space everywhere okay, think of them as
inequalities. And then, this is the visible regions of
the linear program. Okay?
You see the algebraic version of every one of the inequalities that I have been
mentioning here. Okay?
So this is in 2D, right, so it's boring, so we're going to see 3D as well in a
moment, right. But before that what I want to do is
telling you a little bit more definitions here, so a face okay we'll talk about
face and facets. So, face is basically the intersection of
finitely hyperplanes, okay. And so, if we are in dimension n minus 1,
we'll call, we'll call up, you know, we'll talk about facets.
And this, you know, you'll see later on why this facet are important, not right
now, not really for linear program, but later on they will become very important.
And then, of course, when you are in dimension 0, you will have what, you
know, what we call vertices okay. And your, your going to see I'm
completely obsessed, today I'm going to be completely obsessed with these
vertices, okay? So, this is in 3D.
Okay, so this is the first hyperplane we see here.
Okay, a single hyperplane. And we're going to increase the number of
hyperplanes there, but you see the first one over there, right, in three
dimensional. Okay, and now look at this.
This is two hyperplanes, okay, so you see.
You know, the top, and the, you know, the, mostly vertical and mostly
horizontal hyperplanes. You see now that these two hyperplanes
intersect, the intersection of these two hyperplanes is a line.
Okay? You see the line clearly over here.
Okay? And notice this is a really beautiful
fort. Okay?
So, you see these three hyperplanes now. Okay?
So, two, when two of them meet here at these lines that you can see, okay, here
or there. And, of course, when the, the, all three
of them meets, you get this unique point that you see at the back of the picture
there. Okay, so that's essentially what you get
when you have a finite intersection of this hyperplane.
Okay, in 2D, when you have two, you have a line.
When you have three, you have a vertex, well you have a point, okay.
Okay, so what you see on the screen now is a huge number, not a huge number, a
nice number of hyperplanes. And you get a very nice polytope that you
see over there, okay. So, you can see all the facets, you can
see all the vertices. You can see, you know, this entire
polytope. and that's essentially the kind of
objects that, you know, we are going to manipulate inside, you know, linear
programming. Okay?
So, we have this polytope, okay, nice polytope, and we add a new hyperplane.
Okay? So you can see the new hyperplane.
So, intersect with that polytope. Okay?
So, that's what we want to look at, here. Okay?
So, we have the polytope, we have a new hyperplane, okay, that's a new
constraints in your problem, right? And so, what's going to happen?
And this is what happens. Look at these new polytopes, now.
We have a new facet, okay? And a bunch of new vertices here that you
can see. You know, this is from the top, this is
from the side, okay? So, all these, so that what this
hyperplane did was cutting through the polytopes, and then adding a new facet,
okay? And then, adding of a couple of new
vertices as well, okay? Once again, what you see there is
basically what all these you know hyperplanes are creating.
And they are creating this beautiful polytopes with a bunch of facets and a
number of vertices here. Okay.
Now, this is a very important result. Okay.
So, every point, okay, in aside a polytopes, the polytope that I've just
shown you which are defined by these hyperplanes and housespaces is a convex
combination of the vertices. Okay.
So, that's a very interesting result. The basic thing is that every point
inside this polytope, right, can be expressed as a combination of the
vertices. I have this point here, okay it's a
combination of these two vertices, I have this point, it's a combination of these
three vertices here. Okay.
So, that's a very interesting result. And we're going to use it for, you know,
actually proving some very interesting results in, in the theory of linear
programs. Okay.
Now why, why am I so obsessed with these vertices?
And this is the reason why. If you have a nice linear program that I,
as I, as I, as I have shown you so far, okay.
What you know, okay, is that at least one of the point, where the objective value,
this guy here, right, is minimal. Okay, is going to be at the vertex.
It doesn't mean that, you know, there are no other points where the solution is
optimal. Okay?
But there will be at least one of them which is located at a vertex, okay?
So, in a sense, that's why we are obsessed with these vertices, right?
So, because we know that one, at least one of the optimal solutions, okay, is
going to be at one of these vertices. Okay and I'm going to show you the proof.
Okay, but essentially what so, so lets, first let's look at it in a, in a, in a
geometry in a geometry equate right? So, this is a hyperplane right?
So, I'm basically saying, you know, I have the, I, I take the objective
function, and I assume that it's equal to a positive value B.
Okay, that defines an hyperplane and you see this hyperplane here, right?
So, what I'm trying to do in a sense is minimize is minimize that b, right?
So, in a sense I'm trying to take this hyper plane okay and bring it down, okay?
And so, this is what this is what we going to do okay so when we optimize
[SOUND]. We get to a particle point with this
hyper, this value for B is going to be minimal.
And so, this is a point that you see over there.
And that point is on a vertex. Okay.
And we're going to call it B star. And so, you'll see optimal solutions, I
always going to have a little star, in, in, in these lectures.
Okay. So, in a sense, once again we took, we
took that, that hyperplace and we tried to minimize the value of b because that's
the value of the objective function. And so, we move that hyperplane, and when
it's minimal you can be sure that at least one of these points is a vertex.
So, once again, you know, we take this thing, [SOUND], we bring it down.
It's beautiful. Okay.
And we have the optimal solution there. Now this is boring.
Okay. So let's do it in 3D.
And now, ladies and gentlemen, the 3D version right?
So, what you see there is more beautiful polytopes.
And you see this hyperplane there, which is defining the objective function, okay?
And what you are trying to do in this one is maximize, okay?
So, we're going to take his hyperplane and do exactly what we did in 2D's,
right? So this point, it is equal to a constant,
and we are going to try to drive it towards one of the vertices of this
polytope. And this is the result, right.
So, you see this hyperplane now and you see it intersecting finally with this
polytope, okay. And this is probably the best angle here,
right. So, you see that?
It's intersecting with that vertices, okay.
Everywhere else it doesn't touch the polytope, okay.
And so this is, ooh, this is also very nice, okay?
So, you can see that now, this object, it has been maximized, and it's basically a
topological vertex of this polytope. So, I told you, you know, that at least
one of the optimal solution is located on a vertex, and this is the proof, okay?
So, it's a beautiful proof, very simple proof, okay?
And that's why I want to go into, you know, it's something that you can
understand inside the lecture. Okay?
So, let's talk about x star, which is the minimum value.
That's where, you know, the, the, the, that's where the linear program is
optimal. Okay?
This is the point somewhere, okay, and we assume that this, you know, that, that,
we basically, you know, this is the optimal value.
This is one of the optimal solution. Okay?
Now, we know, we don't know where this point is.
Right? So, we want to show that it's on a
vertex. Right?
So, we, we take that point, okay, and we know that every point inside a polytope
can be expressed as a convex combination of the vertices.
Okay? So, let's assume that these vertices are
v1 to vt. We can reexpress x star, okay, this
optimal point, as a convex combination of these vertices.
And we have this, you know, these Lambda 1, Lambda 2, Lambda n, Lambda t, and we
know that some of these Lambdas has to be equal to 1.
And we're going to to use that information later on.
Okay? So now, the objective value at optimality
is c times, you know, x star of the optimal solution.
And therefore, you know, we can reexpress it in terms of the vertices and the
Lambdas by, by simply multiplying that, you know right inside by c.
Okay? So, we basically have at that point that
cx star is equal Lambda 1 times, you know, c1, c times by v1 plus, you know,
the same thing for the other vertices. Okay.
And so, at this point, you know, we just have done, you know, some very simple,
you know algebraic manipulation, you know, knowing that every point inside
the, every point inside the polytope is the convex combination of the, the
vertices. So, what I'm going to do now is assume
that this point, you know, this x star is not on the vertex, okay.
And I'm going to assume that, it's, it's not a vertex, so what I'm assuming is
essentially that cx star is always smaller than c times Vi.
Okay, with Vi is one of the verticies, it's going to be smaller than all of the
vertices. Okay?
And what I'm going to do is derive a contradiction of course.
Okay? And that will prove that it'll actually,
it has to be at least on one of these vertices.
Okay? And how do we get the contradiction?
Well, let's start, let's start with cx star.
So, we start with cx star. Okay?
And then, we simply rewrite, you know, the formula that is shown before, but
know at this point you see c, c v 1. What do we do?
We, we made the hypothesis that cx star was smaller than c Vi.
So, if we can replace every one of these c Vi, okay, by cx star, and we all know
that cx star is going to be greater than that, because I'm replacing every one of
these component by something which is smaller.
Okay? Now, I factorize the cx star, okay, and I
get the sum of the Lambdas and cx star. I know that because this is a convex
combination that the sum of the Lambdas are equal to 1, so I get cx star.
So, what I get is the formula, well, well, it's basically the contradiction
here. I have that cx star is greater than cx
star which is really difficult to do. Right.
And therefore, you know, one of the hypothesis that I took, you know, was
wrong, and this is the hypothesis that the value of the objective was, you know,
smaller then all the vertices. So, I know that essentially, you know,
the optimal solution has to be on a vertex, okay, very simple proof right.
So, at this point still, so we know we have a lot of information, right?
So, we know that the, the solution of a linear program is located to one of these
vertices. Okay, so now, I have a geometry
categorism to do that, right? I can solve the linear program
geometrically. I just draw this polytope, okay, and then
I inumerate all the vertices for every one of them, I compute a value of the
objective function. And that's going to be giving me the
optimal solution. Okay, so that's the algebraic view, okay.
So, what we're going to do next time is to show how this algebraic, this
geometrical view, can be, you know, can be translated to an algebraic view which
we will be able to solve in a little bit, you know, in a little bit easier fashion.
Okay, thank you.