0:09

So let's recall the first example that we looked at here.

We wanted to maximize 200M + 100W subject to this bunch of equations.

Now it turns out we had a very clever way of proving

that optimum was correct once we found it.

So the best you could do is 60000, and there was a great way of proving it.

We took one constraint, we multiplied by a hundred, we took another constraint and

we multiplied it by half.

We added those together and we got a new constraint that,

if we satisfied our original constraints, it had to be the case.

That 200M plus 100W, the thing we were trying to optimize, was at most 60,000.

And this is a very interesting and

general technique that if you want to bound your objective.

You can try and

do this by combining the constraints that you have together to prove a bound.

1:10

Subject to a bunch of these linear inequality constraints A11x1 plus

a12x2 plus dot dot dot is at least b1 and thenetc etc.

So how can we try and do this?

Well if you give me any constant ci bigger than 0,

you can take the first constraint and multiply it by c1 and

the second constraint multiplied by c2 and so on and so forth, and add those all up.

And what you'll get is a new linear inequality,

w1x1 plus w2x2 plus dot dot dot is at least T.

Here the w i are some combination of the Cs, w i is the sum of c j a j i and

t is the sum of c j b j and this is a new inequality.

Now, if it's the case that w i is equal to Vi for

all i, we have is that V1X1 plus V2X2 plus dot,

dot, dot that thing we were trying to minimize is at least t.

And so, if we can arrange for Wi to the Vi for all i,

we've proven a lower bound on the thing that we're trying to minimize.

So, we'd like to find there's a bunch of Ci's that are all non-negative such that

vi is the sum of j = 1 to m of cj aji for all i.

And so that subject to this constraints t the sum of cjbj is as large as possible.

So we like the biggest lower bound we can.

Now the very interesting thing about this,

is that this system we just wrote down is actually just another linear program.

We want to find the c in Rm such that cjbj the sum of that is as

large as possible subject to a bunch of linear inequalities.

CI bigger than or equal to 0 and a few linear equalities.

vi is the sum of cj times aji.

3:03

And so, to put this formally,

given any linear program we can call the primal very often..

Say minimize v.x subject to Ax at least b.

There's a dual linear problem,

which is the linear problem that we want to maximize.

Y.b subject to y transpose A equals v and

that's just another way of rewriting our inequality constraints.

And y at least 0.

And it should be noted that even if your linear program wasn't exactly in

this form, you can still write a dual program,

it's with a linear program of trying to find a combination of the constraints.

To bound the thing that you're trying to optimize.

And so it's not hard to show that a solution to the dual program

bounds the optimum for the primal.

4:14

Now the surprising thing is that not just is this a way that you can get lower

bounds, that these two linear programs they actually have the same solution.

If you find the best solution for

the dual program, it actually always gives you a tight lower bound for the primal.

4:38

And this is incredibly useful.

On the one hand it says if you have a linear program and

want to prove that your answer is optimal you could try and

solve the dual to provide a matching upper band or lower band.

4:51

It also means that if all you care about is the numerical

answer you can try to solve with dual program rather than the primal.

And often, dual program is easier to solve, and so

this makes things more convenient.

And even if the dual program isn't easier,

often looking at the dual gives you some insight into the solution to the primal.

5:13

Ok so that's the new programming duality.

Let's look at some examples.

For example, let's look at the max flow problem.

The size of your flow is the total flow going out of a source minus

total flow going into a source.

5:26

Now, we have a bunch of these conservation of flow equations, and

we can add any multiples of those that we like.

And the objective stays the same.

So when we do that, the thing we're trying to maximize is the same

as the sum over all vertices V of some constant C sub V

times the total flow out of vertex V minus the total flow into vertex V.

5:50

Here C sub s needs to be 1 if s is a source and

C sub t needs to be zero if t is a sign but for

any other vertex V we can take C sub v to be anything we like.

[COUGH] Okay, so

we have this expression, what do we get when we write this down?

6:18

We can now try to bound this above using our capacity constraints.

And so the best we can do here,

it's not hard to show is the sum over edges v to w of the capacity

of the edge e times the maximum of either C sub v minus C sub w or zero.

6:58

The bound that we prove then reduces to the sum over edges V w,

where V is in script C and w isn’t of the capacity h.

But you'll note, C is just cut and

this bound that we proved is just the size of the cut.

And so, this dual program in some sense is just trying to find the minimum cut.

Hence, linear programming in duality,

in this special case, just gives us the max flow equals min cut.

7:27

Okay, let's look at this other problem for example.

The diet problem.

Here we want to minimize the total cost of foods you need to buy,

subject to constraints.

It needs to meet your various daily requirements for various nutrients, and

you need to get a non-negative amount of each type of food.

8:02

Okay, so when we combine all of those together we're suppose to get

A lower bound on the cost of our diet.

And so, if you compare coefficients well, the coefficient we need to end up with for

a food f is the cost of that food.

8:18

And this should be equal to the sum of our nutrients N

of C sub of N times the amount of that nutrients in the food f.

Plus some positive amount that we got by adding whatever multiple we had

on the constraint that we got a non-negative amount of that food.

8:43

But there’s a nice way now of interpreting this C sub N.

We can interpret it as a cost in order to buy a unit of nutrients N.

And so if there was a market where you could just buy calories at the cost of

Cn and you could buy protein at the cost of whatever.

What the above equations are saying.

Is that for each food you can't cheat the system by buying out food.

You can't get nutrients more cheaply than you could

by buying the nutrients individually.

9:14

And the cheapest way to get nutrients is buying them individually

it's pretty clear the total cost of a balanced diet

is at least just the sum over nutrients at the cost of that

nutrient times the amount of nutrient that you're required to have in your diet.

9:28

And so, what this linear program tries to do,

is it tries to find non-negative costs for

the various nutrients that satisfy this, no food allows you to cheat inequalities.

Such that the total cost of your diet is large as possible.

Now, there's one interesting observation about the solution,

supposed that we're actually trying to exactly achieved this lower bound.

9:53

That would mean that you could never afford to buy overpriced food.

You can never afford to buy foods where the cost of that food was strictly bigger

than the total cost of all the nutrients that make up that food.

You could only buy foods where the cost of the foods is exactly the cost

of the nutrients in that food.

10:11

And this gives us as an example of a general phenomena

called complementary slackness

where basically what this says Is that if you look at the solutions the dual,

you should look at which equations you needed to use in the dual program.

That tells you about which equations in the primal program need to be

10:30

so in particular, complementary slackness is the following theorem.

If you give me a primal in your program, minimize v.

x subject to Ax at least b.

And it's dual.

Then if you take solutions to these two, if you use a positive multiple of

an equation in the dual, if yi is strictly bigger than 0, in the dual.

11:04

So let's reveal what this means.

Let's suppose that we have a linear program to find by these five

linear inequalities labelled 1, 2, 3, 4, 5 and the diagram below.

We have allowed what regions this gray region and

the red point located is the optimal.

11:20

Now, suppose that we're looking for solutions of the dual program.

Which of these five equations might actually be used as sort of positive

multiple of those equations, in the solutions to the dual program?

11:34

Well, it turns out the only equations that you could actually use are two and

four because complementary slackness says that the only equations that get used in

the solution to the dual are ones with that equation is tight in the primal.

And in this case, two and

four are the only lines of this solution to the primal actually lies on.

And its those are the only equations that could actually be used in the solution.

12:00

So in summary everything in your program has a dual in your program.

The solution to dual actually bounds to the solutions to the primal.

And surprisingly the LP na dit's dual has the same answer.

And this means that the solution do dual actually

is tight bound to the solution to the primal An.

In addition, we have this complementary slackness where knowing the solutions to

the dual tells you a lot about where the solutions to the primal lies.

In fact, it tells you which equations in the solutions the primal needs to be tied.

12:32

So that's basically everything we have for this lecture.

Next lecture we're going to talk about proofs for these things so that

material is not necessarily required, but if you'd like to see it, it's informative.