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.