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.