24. Linear Programming and Two-Person Games
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...This lecture focuses on several topics that are specific parts of optimization. These include linear programming (LP), the max-flow min-cut theorem, two-person zero-sum games, and duality. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT OpenCourseWare
00:07
continue to offer high-quality educational resources for free.
00:11
To make a donation or to view additional materials
00:14
from hundreds of MIT courses, visit MIT OpenCourseWare
00:18
at ocw.mit.edu.
00:19
00:26
GILBERT STRANG: OK.
00:27
Let me just say our next topic, moving really
00:31
toward machine learning, would be
00:35
the last section of chapter 6 about
00:38
stochastic gradient descent.
00:40
00:43
I think Professor Sra from computer science,
00:49
if he is able, he will take the class Friday and tell us
00:54
about SGDs, Stochastic Gradient Descent, critical algorithm.
01:01
I mean that, at a quick look, stochastic gradient descent
01:07
does smaller batches at a time, so it's computationally faster
01:11
than pure gradient descent.
01:14
But also, stochastic gradient descent
01:17
is able to solve probabilistic problems where
01:20
you're trying to minimize an expected value instead
01:24
of a function.
01:25
Anyway, it's an important thing.
01:30
Actually, there is a lecture at 2:00
01:35
in neuroscience about the gradient descent algorithms.
01:42
And then Professor Boyd is speaking here at 4:30
01:45
this afternoon.
01:46
It's overwhelming.
01:49
So I'm going to talk today about several topics that are
01:57
specific parts of optimization.
02:01
Linear programming is a very famous part of optimization.
02:04
I don't know if you've met it.
02:07
I think it's worth knowing what the inputs are
02:13
and what's the key fact about linear programming.
02:17
And, of course, also, what are the algorithms.
02:20
That's usually what we want to know.
02:23
What's the problem?
02:25
What are the results, the mathematical results?
02:27
And what are the computational tools?
02:30
Yes, so that's very established.
02:33
Max-flow min-cut is one specific linear programming
02:37
that I think maybe would serve as the best example.
02:41
And then two-person games, have you met those?
02:46
So would you know what the rules are
02:48
in a two-person zero-sum game?
02:53
In game theory, those are the ones that are clear--
02:57
everything's well-established there.
03:04
And, in fact, they're equivalent to a linear program.
03:07
So that's why those two are coming in today.
03:10
And then the key fact about two-person games and about
03:15
linear programming is duality.
03:17
So if there's any word on that board,
03:20
it's the one in capital letters that has math content.
03:25
I'm just going to start with linear programming
03:28
and then move on.
03:35
So what's a linear program?
03:37
It's we're optimizing a linear cost function.
03:41
So we're minimizing the cost c transpose x.
03:46
So that vector x is the unknown that we're looking for,
03:50
and this vector c is the cost vector.
03:53
So that is c1 x1 plus, plus cn xn.
03:59
So you can see why it's called linear programming.
04:02
The cost is linear.
04:04
The constraints are also linear.
04:06
So the constraints on x are a set of linear equations.
04:19
Of course, I'm not thinking of A as being a square invertible
04:23
matrix.
04:24
No way.
04:25
If it were, that would tell us what x had to be
04:27
and our problem would be over.
04:29
04:33
We have n unknowns.
04:36
This is m by n, of course.
04:39
x is n by 1.
04:41
That's our unknown vector.
04:44
And I'm thinking that m would be smaller than n.
04:49
But we do have constraints, and now comes
04:52
the thing that makes linear programming not actually
04:56
linear.
04:58
And that's the constraint x greater or equal to 0.
05:03
And I've written that as a vector
05:05
but that means x1 greater or equal to 0, on to xn
05:14
greater or equal to 0.
05:16
So it's a vector inequality.
05:19
So we have minimizing a very simple function
05:24
with pretty straightforward constraints but inequality
05:28
constraints.
05:29
So the set of--
05:32
these two together are the constraints.
05:36
And in linear algebra--
05:38
in linear programming language this is called a feasible set
05:45
of x's.
05:48
It's the constraint set, capital K in the notes.
05:54
So let me draw a picture to show--
06:01
or maybe I'll just ask.
06:03
How many of you are already familiar
06:06
with linear programming?
06:08
Oh, quite a lot.
06:09
So I won't belabor the point.
06:11
But let me just draw a picture.
06:16
So my picture will be just here.
06:22
So that's n equals 3.
06:25
So this is the x1, x2, x3 space.
06:30
And x greater or equal to 0 means what?
06:34
It means that I'm in this 1/8 of this space, right?
06:40
It's the non-negative-- well, I would say quadrant
06:44
but I really should say octant because it's
06:48
1/8 of the full 3D space.
06:51
So I'm in here.
06:53
And then maybe I have m as maybe just one constraint.
06:59
So let me take the cost to be, say, x1 plus 2 x2 plus 5 x3,
07:08
say.
07:10
And the constraint, I'm just going to have one equation--
07:14
x1 plus x2.
07:16
Let me make it easy, make that constraint an easy one to--
07:22
so this is what we want to minimize.
07:27
And that's what we have to satisfy, as well
07:33
as x greater or equal to 0.
07:35
So that's a plane.
07:38
One equation gives us a plane in R3.
07:41
The plane would go through--
07:43
07:47
would hit the axes at 3, 0, 0.
07:57
And so the min--
07:59
the point has to lie on that plane.
08:02
And it has to lie in the octant, so that plane is chopped off
08:07
to be a triangle.
08:08
This is a good visualization of linear programming.
08:13
And what's the conclusion?
08:15
Well, our cost is linear.
08:17
08:19
So the result is that one of these three corners
08:24
is the winner.
08:27
It could happen.
08:29
It could happen that maybe I have equal values on those two
08:32
corners, and therefore all the way along
08:35
would be also winners.
08:37
But when I have a linear function,
08:39
it's a maximum at the ends.
08:41
And these are the ends, those three corners.
08:46
So 3, 0, 0, 0, 3, 0, or 0, 0, 3 are the three corners,
08:56
and one of those is the winner and the problem is solved.
08:59
And, in fact, for this case, since I'm minimizing,
09:03
I guess it would be that corner that wins.
09:06
So let me give it a star, not an x.
09:09
Yes.
09:10
3, 0, 0 because that--
09:12
oh.
09:13
No, that's 3.
09:16
So the value turned out to be 3 at the point 3, 0, 0.
09:24
And that's x star.
09:26
09:30
Good.
09:30
Good, good, good.
09:33
What more do I want to do, I said?
09:36
Yes.
09:37
AUDIENCE: Shouldn't it be at point 0, 0, 3?
09:39
09:41
GILBERT STRANG: Should it be--
09:43
oh, no.
09:44
0, 0, 3 would have x3 is 3.
09:47
That's fine.
09:48
It gives us a chance, I think.
09:49
That would give me a cost of 15.
09:52
This would give me a cost of 6, and that
09:53
would give me a cost of 3.
09:55
Yes.
09:55
09:58
It's obvious that if we could enumerate all the corners,
10:02
we would have a super fast way to get the answer.
10:09
But the trouble is, of course, that for large values of m
10:14
and n, there are exponentially many corners,
10:17
and we don't want to see them all.
10:21
So that's what makes linear programming take time and need
10:30
ideas.
10:31
So, for algorithms, there are two types
10:33
of algorithms, two types of codes that solve these.
10:39
The older, well-established ones are the--
10:45
so one way is the simplex method, which finds a corner.
10:56
We know the optimum one of the corners.
11:00
So it will find one corner, and it will go to the next corner.
11:07
11:09
So if it starts at one of these corners,
11:15
it will travel along an edge that lowers the cost.
11:21
And it has to stop at the end because it's linear.
11:25
The cost will keep going down and going down
11:27
until it bumps into the end point,
11:32
and then it can't go further.
11:33
And then we would, from that next corner, we
11:36
would go to the next corner.
11:38
11:42
Each time, it's like steepest descent on the edges.
11:49
From the first corner, we go the steepest way
11:52
till we can't go further, we've hit another corner.
11:56
And we recompute the linear algebra,
11:59
find which direction is steepest from there.
12:03
So that's the idea of the simplex method,
12:06
which was invented by Dantzig.
12:09
12:15
And the algebra is not going to be in today's lecture
12:20
but it's straightforward.
12:23
Well, people have to optimize it because that's
12:25
a highly frequently used method.
12:28
Yes.
12:29
But then, about 20 years later maybe, or 30, I
12:35
remember going to a lecture in downtown Boston by Karmarkar.
12:40
So I have to put his name down--
12:44
Karmarkar.
12:44
12:50
And he was in The New York Times, all the newspapers,
12:55
so it was a big deal.
12:58
He had an alternative algorithm.
13:04
And the exact algorithm he proposed
13:09
hasn't survived until today but the idea has.
13:15
And the idea was to go to travel inside the feasible set and not
13:21
around the edges.
13:23
So his idea-- because in here, would maybe
13:27
travel down near that edge, start again, travel again.
13:31
So it's steepest descent in the constraint set, the feasible
13:38
set.
13:39
And you can use calculus and this idea.
13:46
So this is interior point method.
13:51
So I'll just use the word interior.
13:54
That's telling us that we're inside the feasible set.
14:01
We don't hit, come all the way to the boundary
14:04
intentionally, because we want room
14:06
to move, and to find derivatives, and to use
14:10
Newton's method to minimize.
14:13
You choose a search direction, just as all of optimization
14:17
does.
14:18
And in that search direction, you
14:20
track it and you stop before you bump
14:25
into the edge of the feasible set.
14:27
And then you compute derivatives again.
14:30
So you can use calculus.
14:32
And it's a method that--
14:35
it's an idea that--
14:37
the interior idea came before Karmarkar.
14:40
But he got super publicity, so it really got attention,
14:46
got new thinking.
14:48
And new ideas came partly from people at MIT.
14:52
14:56
And these two are now still locked in competition.
15:01
One hasn't beaten the other in all problems.
15:06
So linear programming is here.
15:11
But then, for nonlinear programming,
15:13
quadratic programming, where the cost is quadratic,
15:17
nonlinear programming, semi-definite programming--
15:21
that's where you have a matrix unknown and matrix
15:24
constraints--
15:27
those are all-- the more complicated you get,
15:31
the more it tends to be interior point methods.
15:35
That's a summary of linear programming.
15:39
15:41
Now I'd like to give an example.
15:44
And then I haven't told you the main--
15:46
well, let me tell you the main fact about duality.
15:48
15:51
This is really-- and I'll write that maybe here next to it.
15:55
15:58
So duality is there's a dual program, a dual LP.
16:05
And that dual is going to do a maximum instead of a minimum
16:12
And the cost is going to involve the b from the primal problem.
16:20
So this is now called the primal problem, and this is its dual.
16:24
So they're twin problems.
16:27
They use the same data but quite differently.
16:30
It's like transposing things.
16:33
So let's call it the unknown y.
16:36
So for y1 to ym, I guess, because b, the right-hand side
16:47
over here, is m by 1.
16:49
16:53
So that's maximize that subject to-- what are the constraints?
16:59
Well, the cost function over here, c, the cost vector,
17:03
goes into the constraints.
17:06
And I think the greater or equal sign probably becomes
17:10
a less or equal to sign.
17:12
The A gets transposed.
17:15
I think that's probably the constraint in the dual.
17:20
And it happens it doesn't need y.
17:23
We don't have y greater or equal to 0 over here.
17:26
So that's a dual problem.
17:28
It has a linear cost.
17:31
It has linear inequality constraints.
17:35
It can be solved by the simplex method.
17:38
You could choose whether you solve that one or this one,
17:41
because if you solve one, you solve the other.
17:45
The two are closely connected and that's
17:48
the key idea of duality.
17:51
So maybe I'll put the idea of, first of all, a weak duality.
17:56
18:03
Which says that this quantity that we're trying to maximize--
18:08
we're getting it as large as possible--
18:11
is always less or equal to any c transpose x.
18:18
This is for any feasible, allowed--
18:28
any x and y that satisfy the constraints.
18:32
Remember, feasible means satisfies the constraints.
18:35
So, in other words, this problem, this maximization
18:39
problem, you're trying to push this up.
18:42
The minimization problem, you're trying to pull this down.
18:46
And it's easier to show that the one, the b
18:49
transpose-- it's easier to show that inequality.
18:52
Let's do that.
18:54
So b transpose y proof.
18:56
18:58
It should be a one-line proof.
19:01
So b transpose y--
19:04
19:06
what do I do?
19:07
So b transpose y well, I look over here.
19:11
That's where b shows up.
19:14
That's x transpose A transpose y, because b is Ax.
19:24
I'm feasible, so my b is Ax.
19:29
And for any x-- this is for this is for any
19:32
x that b is going to be Ax.
19:35
So am I good so far?
19:38
And now what do I do?
19:40
Now I look here.
19:43
I see A transpose y sitting right in front of me.
19:46
So I say, well, OK, less or equal to.
19:50
And I guess I'm done.
19:52
A transpose y is less or equal to c.
19:54
So I have x transpose c, c transpose x.
19:59
So this equals this, less or equal that.
20:04
I've got it.
20:05
Weak duality is just put together the requirements
20:11
on x and y and you have it.
20:13
But was this important?
20:19
20:22
If the mathematics is right, everything
20:24
has to have its place, play its role.
20:27
And so what's the role of x greater or equal to 0 there?
20:32
Why do we need x--
20:34
If we just even think of n equal 1, just a number,
20:40
where do we use the fact that x is greater or equal to 0?
20:43
Do we use it?
20:45
This looks so smooth, because A transpose y--
20:52
I'll write that as x transpose c for the moment,
20:58
just so your eye says that's the same x transpose,
21:03
and the A transpose y is less or equal to c.
21:06
Where is x greater or equal to 0 coming in?
21:08
AUDIENCE: [INAUDIBLE].
21:10
GILBERT STRANG: Yes.
21:11
AUDIENCE: Like above.
21:12
It's from the that.
21:12
GILBERT STRANG: Yes, that's true.
21:14
But I want to see--
21:17
so here's my point.
21:19
The fact that A transpose y is less
21:21
or equal to c, that's fine.
21:23
Highly important.
21:25
But if x was negative, it would be the other way.
21:30
You would go the other way and you
21:31
wouldn't have what you want.
21:33
So we really do use the fact that x is greater or equal to 0
21:38
to say that I have this less or equal this.
21:41
And then I multiply by something positive
21:44
and then I still have less or equal.
21:46
OK, good.
21:47
So the math is right.
21:50
Everything does its part.
21:53
And then, of course, the beautiful result,
21:56
the important result is that there
21:59
is strong duality, just called duality,
22:03
which is that at the maximum--
22:06
now this is not for any x and y but this is for--
22:10
this is going to be for x y star, the winner,
22:14
and x star, the winner--
22:16
equality holds.
22:18
So that's duality.
22:19
22:22
The maximum in the dual problem is
22:24
the same as the minimum in the primal problem.
22:27
The two have met.
22:29
There is no duality gap.
22:32
In some cooked up nonlinear problems,
22:36
there could be a gap between the maximum and the minimum,
22:41
but you hope not.
22:43
And here the big theorem is not.
22:48
They're equal.
22:49
You push this up, push that down.
22:53
Another way to say that duality is that this is
22:59
pushing that up at some max--
23:01
I could write that as a maximum of a minimum equaling a minimum
23:06
of a maximum, if I wanted.
23:08
23:12
So the duality in linear programming
23:16
was the same as von Neumann's minimax theorem.
23:20
And his theorem applied to two-person games.
23:25
So the key math result is duality for linear programming,
23:34
and it's going to be-- you'll see the same thing happening
23:38
for two-person games.
23:41
And it's a minimax theorem, or a saddle point.
23:44
Or it's just things come out right.
23:50
Yes.
23:51
So just to mention that mathematical programming,
23:58
of course, includes much more difficult problems.
24:03
This is linear programming.
24:05
That problem, as you see, has a beautiful, simple theory.
24:10
And the paying attention is paying attention
24:16
to the algorithm, because you've got two important choices
24:19
and they both get highly developed.
24:21
24:24
Now, OK.
24:25
So for game, now I'm going to turn to--
24:28
well, I'll do an example of max flow equal min cut,
24:33
just see what--
24:35
and then go to two-person game.
24:38
So here's an example of a--
24:42
24:52
so I start with a graph.
24:56
Let me just imagine.
24:58
25:04
So this is the source.
25:06
25:09
This is the sink.
25:11
And I'm sending flow through the network.
25:15
So it's a network that I'm sending flow through.
25:19
So my job is to maximize--
25:21
25:24
I'll set x at the source to be 0.
25:27
25:32
And then the flow, the total flow will come into the sink.
25:36
So I want to maximize x at the sink.
25:42
So it's a linear programming and there are constraints.
25:45
So what are the constraints?
25:47
Every edge has a capacity.
25:50
So let's see.
25:51
Suppose that edge has capacity 5.
25:57
Let me put capacities on all these edges.
26:01
2, 1, 3, 4.
26:07
I'm just stabbing around here.
26:09
26:12
1,000.
26:15
And let me say 2 and 4.
26:22
I have no idea what's happening here.
26:25
But if we see the problem, we'll probably be able to solve it.
26:31
So these constraints are that the flow variable,
26:36
which would be the y that I'm trying to maximize, cannot--
26:42
the amount of flow, just in ordinary words,
26:45
the amount of flow on the edges can't go higher
26:50
than the capacity.
26:51
I could send 11 along this edge, but then I've got nowhere
26:54
to send it after that.
26:57
I could send, well, 900 on that edge.
27:00
but, obviously, it would get stuck there.
27:04
So the question is, what's the maximum I
27:09
can send through that network?
27:11
It's a classical problem.
27:15
And, in fact, it's an integer programming problem.
27:20
These are all integer capacities.
27:22
I could insist on integer flow.
27:27
But it's a very remarkable integer problem
27:32
because I could allow fractions and the answer
27:37
would not be a-- would not involve fractions.
27:40
In other words, if I keep it as an integer problem,
27:44
then the mathematics is definitely
27:49
harder for an integer problem.
27:51
What's different?
27:53
So the x's could be integers or they could be real numbers.
28:02
28:07
Over here, they were real numbers.
28:11
I happened to get an integer for this,
28:13
but if I had 10 crossing planes in 15 dimensions,
28:20
the integers would be totally lost.
28:24
But the point is, here, that if I allow real numbers,
28:32
it doesn't get me any more flow, that the winning
28:36
flow is an integer anyway.
28:38
So it's an integer problem which can be safely relaxed,
28:43
and you can safely use simplex method, or Karmarkar's method,
28:48
or any interior point method with non-integers,
28:53
because in the interior here you're not starting or ending
28:57
at integers.
28:59
You can do it because the integer answer
29:04
will be, in the end, better.
29:07
And what is that answer?
29:09
I think I've made those capacities too easy to--
29:16
oh, I didn't do this one.
29:17
29:24
So what shall I-- shall I make it large, like 9?
29:27
I don't know.
29:29
What's the best we can do through that network?
29:40
Can you-- I can't see it from here yet?
29:42
29:45
What should I do?
29:47
Obviously, in this simple problem
29:49
I can get anything I want pretty much that far.
29:54
But then what can I do?
29:56
29:58
Let me even make that 19.
30:00
30:05
So I'm not imposing much of a limit on that edge either.
30:10
But these edges are quite tight limits,
30:12
and these are sort of intermediate limits.
30:15
What do you think is the most I can send through?
30:22
And how would you show me that I couldn't send more?
30:25
That's the key question.
30:28
I want to get a bound on the--
30:31
an upper bound on this maximum.
30:34
This maximum getting into the sink
30:36
is less or equal to-- and what number would you propose?
30:41
Could I get 1,000 through?
30:44
I could start, but of course it would pile up there.
30:49
I couldn't get further.
30:50
30:54
What do you think is the best I can do?
30:57
AUDIENCE: 10?
30:58
GILBERT STRANG: 10?
30:59
I can't do more than 10?
31:01
How could I do 10?
31:04
AUDIENCE: So you go 12--
31:07
GILBERT STRANG: 12 this way?
31:08
AUDIENCE: Yes.
31:09
19.
31:10
GILBERT STRANG: Oh, OK.
31:11
AUDIENCE: And then split the 8 and 2.
31:13
Can you split?
31:14
GILBERT STRANG: I see.
31:15
10 that way, 10 this-- yes, absolutely you can split.
31:19
And then this could go here, and that would be able to go there.
31:23
So I can get 10 through.
31:25
Correct.
31:27
AUDIENCE: [INAUDIBLE].
31:29
GILBERT STRANG: Can I do anything better?
31:31
Oh, I could be sending some up this way at the same time.
31:35
So I could get 3 along the top.
31:38
So this is like an auction.
31:41
We can get up to 13.
31:43
Can we get-- so that was 3 going this way and 10 going this way.
31:53
Is 13 an-- can I not exceed 13?
31:58
AUDIENCE: 14?
31:58
AUDIENCE: 14.
32:00
GILBERT STRANG: Do I hear 14?
32:04
Oh, I've got a lot of room for one more.
32:06
So, OK.
32:07
So 14 in any case.
32:10
All right.
32:10
Do I hear 15?
32:12
AUDIENCE: Can you do two more on the bottom,
32:14
like 12 instead of 10?
32:15
GILBERT STRANG: If I did 12, then what would I do?
32:18
AUDIENCE: Split the other two up.
32:20
GILBERT STRANG: I'd send two up here.
32:23
What am I going to do with them from here?
32:24
AUDIENCE: [INAUDIBLE].
32:26
GILBERT STRANG: Send them?
32:27
AUDIENCE: Up again.
32:28
GILBERT STRANG: Up again, and along.
32:30
But then the 3 that I had right now would be cut back to 1.
32:37
32:41
It's a lot of fun, this max flow problem.
32:46
And I'm looking for a bound to know
32:49
when to quit, to know when I've optimized.
32:51
That's the whole idea of duality,
32:53
is to find some upper thing that I'm trying to push down
33:00
but I can't go beyond it.
33:03
So I don't think I could get more than--
33:06
you see, everything has to cross this middle.
33:09
So 3 and 4.
33:10
And I don't think I could beat 23.
33:13
If somebody said more than 23, I would be very doubtful,
33:18
because I couldn't get it across the middle.
33:21
But then, can I get 23?
33:24
I doubt it.
33:25
Maybe 14 is the best possible.
33:28
So how would we show that 14 is the best possible?
33:31
33:35
I think if I could find--
33:37
so this is called a cut, a cut in this network.
33:43
Oh, yes, I see a cut.
33:45
A cut like there.
33:46
33:50
You see that?
33:51
Every bit of flow has got to cross that cut.
33:58
And the total capacity crossing is the 3 and the 1 and the 2
34:03
and the 8, which is 14.
34:06
So I can't get more than 14 through.
34:08
And somehow that cut is loaded to capacity.
34:13
Probably those edges all have to be fully up
34:19
to capacity that cross the cut.
34:23
So the cut is a separation of edges
34:27
that go with the source and--
34:29
sorry-- nodes that go with the source, nodes
34:32
that go with the sink.
34:33
Yes.
34:34
34:37
And then it's the edges across the cut.
34:39
34:42
Is that OK for an example?
34:45
So that's the duality.
34:47
The maximum flow turned out to be 14,
34:51
and the minimum cut turned out to be 14.
34:54
And when those match, 14 equal 14, I know I'm through.
34:58
I know I'm through because I'm able to get 14 through
35:00
and I could never get more.
35:02
Yes.
35:03
3 and 4 and 6 and 8.
35:04
Yes.
35:06
And, of course, in a big network,
35:11
the maximum cut is not going to be visible.
35:15
Well, you couldn't-- it would have thousands of edges.
35:18
You couldn't see what you were doing,
35:21
But you could solve this problem fast, actually fast.
35:26
And it's an important--
35:28
in practice, it's an important example.
35:31
A lot of other things fit into the max flow min cut example.
35:36
And therefore solving it in faster than-- oh,
35:40
I didn't even say about speed.
35:44
So the simplex method, almost always it's average case.
35:49
Dan Spielman, who was on the faculty
35:51
here, who's just terrific in this area,
35:58
was maybe among the first to study the average case.
36:03
So for an average choice of A and b and c,
36:08
instead of making the worst choice--
36:11
for the worst choice, you can create a feasible set
36:15
that it has to go corner, corner, corner,
36:17
corner to get to the end, so the simplex method would
36:22
take exponentially long.
36:24
But that's extremely rare.
36:27
It doesn't happen in practice, I think.
36:30
And the average one is a polynomial,
36:33
so it's a fast method on average.
36:40
And we can show-- actually, that was a famous result that
36:43
came from Russia, that linear programming is in the big P
36:51
versus LP world, linear programming
36:55
goes with P. Linear programming is
36:57
a problem that can be solved in polynomial time.
37:01
The simplex method won't always do it but it can be done.
37:05
Yes.
37:06
There came into the world, the ellipsoid methods,
37:10
and it was an exciting time to decide that linear programming
37:15
was actually P and not LP.
37:18
37:22
So this is a case of duality where you can understand
37:27
duality by the statement that the flow cannot exceed
37:32
the capacity of the cut.
37:34
So that's what duality is, that any flow has
37:42
to be less or equal the capacity of any cut,
37:51
the capacity being the sum of the ones.
37:56
So, of course, there are other cuts.
37:58
That cut has to be crossed, but that's
38:01
gone 3, 7, 14, 22 capacity.
38:05
So the 14 capacity was the minimum,
38:11
and that gave the maximum.
38:12
Nice.
38:13
Isn't it nice?
38:14
Yes.
38:14
38:17
So there is another world here of two-person games
38:22
that also has duality and could be expressed.
38:26
So let me just talk finally today about two-person games.
38:31
So the two persons are x and y of course.
38:35
What other names could they have?
38:37
And there is a matrix involved.
38:44
This is the payoff matrix.
38:47
38:51
So let me take a very simple game first.
38:53
38:56
So x is going to choose one of these rows,
39:01
and y is going to choose one of these columns.
39:05
And let's say payoff from x to y.
39:07
39:11
I like it that way because, then, x, who's paying,
39:16
is going to be minimizing, as x was up here.
39:21
And y, who's collecting, is going
39:24
to be maximizing, as in the dual.
39:28
So the payoff-- well, let's see.
39:30
I think maybe 1, 4, 2, 8 would be probably a fairly easy game
39:37
to play.
39:39
So it's a two-person game, a zero-sum game.
39:43
Zero sum means-- that means all pay--
39:54
what x pays goes to y.
39:58
y gets all that x pays.
40:03
There's no third party here.
40:08
No lawyers involved.
40:09
40:13
And y is going to choose a column,
40:16
and x is going to choose a row.
40:18
And x wants to make it small, and y wants to make it big.
40:23
So what happens in this game?
40:26
What does y choose to make it big?
40:28
The second column.
40:29
What does x choose to make it small?
40:31
The first row.
40:33
So it's going to be focused in on that 2,
40:37
because if y keeps choosing that column, 2 is the best--
40:42
the least that-- x is going to have to pay 2,
40:46
and he achieves that by choosing the first row.
40:50
So it's a simple game.
40:52
That's a saddle point.
40:54
It's a minimum for y in its column,
40:59
and it's a maximum for x in its row.
41:03
But, of course, a matrix, another matrix
41:05
might not have such a saddle point.
41:08
So let me-- do you see--
41:09
OK with this game?
41:12
That would be a sort of straightforward game
41:15
where simple strategy--
41:17
column 2 every time, row 1 every time is the optimal.
41:22
But now let me just exchange that.
41:24
41:29
So, again, x1 and x2.
41:33
y1 and y2 are the two columns.
41:36
What happens now?
41:37
41:40
Well, y kind of likes the big number 8 there.
41:43
41:46
So it goes for the second.
41:48
The second column still has the bigger numbers.
41:51
So y aims for column 2.
41:55
But then what does x do?
41:58
What row does x choose if y is in the column 2?
42:03
AUDIENCE: Second.
42:04
GILBERT STRANG: The second.
42:05
OK.
42:06
So have I found a saddle point?
42:09
Where y chooses this column, x chooses this row,
42:14
is that a saddle point?
42:16
No.
42:17
Because what will y do now?
42:20
He sees x choosing the second row all the time,
42:24
and y sees a 4, a very tempting 4, in that row.
42:29
So y is going to choose y1, the first column, pretty often.
42:35
Not all the time, because what happens if he just--
42:38
if y chooses this column all the time,
42:42
then x will choose this row and the payoff
42:45
would only be 1, so that things went downhill for y there.
42:50
So this is not a saddle point.
42:53
And what do we do?
42:54
43:00
Mixed strategy, which is y will choose the two columns
43:07
with some probabilities that add to 1.
43:10
So there will be a third possibility, that p x1 and 1--
43:19
I'm sorry-- p y1.
43:22
p times this column and 1 minus p times the second column.
43:28
So that will be p plus 1 minus p times 8, and 4p plus 1
43:38
minus p times 2.
43:41
That's this mixed column.
43:44
By mixing his strategy, we have a strategy
43:51
like a third person, y3.
43:53
43:55
And, of course, the x is going to notice after a while what
44:03
the strategy is.
44:06
This is an open competition.
44:09
You're not hiding-- you're not able to hide anything.
44:13
You might think, well, maybe y will jump around,
44:16
but that's foolishness.
44:19
y is going to end up finding the best
44:24
choice of p between 0 and 1.
44:26
44:29
And it will actually be between 0 and 1
44:32
because the extreme strategies of column 1 and column 2
44:38
were not winners.
44:39
But now x is going to do the same thing.
44:42
p x1-- he's going to--
44:44
he or she is going to combine those rows.
44:51
So this would be p1 for the first row, and 1--
44:58
sorry-- p-- oh, I better choose another number.
45:03
What's another letter than p?
45:05
AUDIENCE: q.
45:06
GILBERT STRANG: q?
45:08
OK, q.
45:09
45:14
So this row is a combination of those rows, so it's q plus 1
45:21
minus q times 4 in the first position, and p times 8 and 1
45:32
minus p-- q times 8.
45:35
q times 8 and 1 minus q times 2.
45:39
I'm sorry that I've written this too small.
45:44
But what's going to happen?
45:46
45:50
What's going to determine p and q and solve the game?
45:54
45:57
Well, if these are equal, then what happens?
46:04
Then x is OK with either one.
46:08
46:10
x has nothing to choose if those are equal
46:14
and y is staying with his mixed strategy, which gives him
46:18
this third combination column.
46:22
Then x is good.
46:24
Now, you might say, well, then x could do what it wanted.
46:28
But x couldn't do what it wanted.
46:31
If x doesn't stick with the optimal strategy q for x,
46:37
then y will take advantage.
46:40
So, really, the game settles down to once--
46:45
so these should be equal.
46:47
So when those are equal, what do I get?
46:51
I have p-- it looks like I have 8 minus 7p
46:57
there for the first one.
46:59
And here, I have 4p minus 2p.
47:01
That's 2p plus 1.
47:04
Did I get that possibly right?
47:07
AUDIENCE: Plus 2.
47:08
47:11
GILBERT STRANG: 2, 4p minus 2p is the 2p.
47:15
Oh, it's 2.
47:16
Yes.
47:17
OK.
47:19
So those are equal.
47:20
And that tells me that 9p is 6, and p is 2/3.
47:25
47:29
So it turned out that the best strategy for y
47:33
is 2/3 on the first column which didn't look so promising,
47:39
and 1/3 on the second column.
47:42
And by creating that strategy, what do these numbers come out
47:48
to be?
47:48
And they're supposed to come out equal.
47:50
So 4p plus-- so 4 times 2/3 is 8/3,
47:57
plus 1 minus p is 1/3 times--
48:00
plus 2/3 is 10/3.
48:03
So I think that this is 10/3.
48:06
And if that one isn't 10/3, I'm very surprised.
48:10
So that's 2/3-- help.
48:14
Is it?
48:16
4p, 2p, 4/3.
48:23
Yes, it's telling me they're the same.
48:27
Did I set them equal?
48:29
Yes.
48:29
I set them equal to find p.
48:30
So they have to be the same.
48:33
Except for instructor mistakes, which never happen, I suppose.
48:38
OK.
48:38
So those should be equal.
48:41
Then x has no way to do better, choose these columns.
48:48
But he can't choose those columns freely--
48:50
those rows freely because y could take advantage, unless--
48:55
so this would give the best strategy for q--
49:00
sorry-- the best q for x.
49:04
Yes.
49:04
49:07
Do you see that picture now?
49:08
There could be other--
49:10
it could be a much bigger matrix, of course.
49:13
There could be other columns.
49:15
Suppose there was a 0, 0 column.
49:19
What difference-- what would be the effect
49:21
on the optimal strategy of having that additional column,
49:25
that additional option for y3?
49:29
Well, he wouldn't take it.
49:32
So let's make it more tempting.
49:34
10, 10, 10.
49:38
Oh, he would take that, right?
49:41
Yes.
49:41
That was not-- so I'm not sure what I am trying to say here.
49:45
49:49
Yes.
49:51
There certainly could be-- there could be rows that--
49:54
or columns, or rows for x, that don't enter the mixed,
49:59
the optimal mixed strategy.
50:02
A mixed strategy is some combination
50:04
of strategies, some combination of pure strategies,
50:08
like choose this column, choose this row.
50:11
But some columns may not-- or rows-- may not
50:15
show up in the best mixture.
50:17
So I won't complete that partial thought there.
50:22
50:26
So do you see that we have a duality theorem?
50:31
First of all, you could write that as a linear program.
50:35
The unknown is p for x--
50:39
for y.
50:40
The unknown is q for x.
50:42
So, actually, you just have one unknown in this simple problem,
50:50
for this small problem.
50:52
But you have a minimization, a maximization.
50:55
They meet at the optimum.
50:58
And the duality theorem becomes the theorem
51:05
for two-person games.
51:08
Linear programming matches two-person games.
51:12
The point about two persons is very important.
51:16
Three-person games are incredibly complicated.
51:20
No theory at this simple level would solve three-person games.
51:27
So that's where John Nash's Nobel Prize
51:32
comes into the picture.
51:35
So his Nobel Prize was in economics
51:38
because of the wide applications,
51:40
but he was able to analyze the problem of--
51:45
and for functions more than for matrices--
51:47
of a three-person or n-person game.
51:53
So you know the story of John Nash?
51:57
The book A Beautiful Mind and the movie A Beautiful Mind.
52:01
So it's one of those movies that involves MIT
52:03
because he was here.
52:05
But you can't recognize anything about MIT in the movie.
52:09
It's like Good Will Hunting.
52:12
You're maybe in some basement of some remote building.
52:17
But anyway.
52:20
It was of course a tragic--
52:22
tragic, and then cheer, then wonderful, and then tragic
52:26
again for John Nash.
52:29
He had-- so when I met him, he was
52:33
going to teach linear algebra, one section,
52:36
but that never developed.
52:39
That was when he was--
52:41
his mental state was going downhill.
52:45
And he moved to Princeton and just stayed.
52:53
And then the wonderful thing was that he improved,
52:55
and then the very sad thing was his death
52:58
in a car accident on the way home from the Nobel Prize.
53:04
So quite a story, an amazing story.
53:09
Yes.
53:10
So that's specific optimization problems, linear programming
53:17
and two-person games.
53:19
And I hope that Friday it will be Professor Sra. Anyway,
53:27
the lecture will certainly be about stochastic gradient
53:30
descent.
53:31
Good.
53:31
Thanks.
English - CC (English)
###