1
00:00:00,890 --> 00:00:03,546
So now I'll go through a quick example

2
00:00:03,546 --> 00:00:08,000
of solving a optimization problem using
the Lagrange method.

3
00:00:11,080 --> 00:00:13,780
So suppose I want to find the minimum

4
00:00:13,780 --> 00:00:18,700
and maximum values of the function 4x2
minus 2x3.

5
00:00:18,700 --> 00:00:22,732
So this is this is a function of three
variables, x1, x2, x3, but

6
00:00:22,732 --> 00:00:26,960
the first one in the objective function it
just has a zero multiplied by it.

7
00:00:26,960 --> 00:00:30,610
So I'm going to simplify it just to say
4x2 minus 2x3.

8
00:00:32,720 --> 00:00:36,596
Then subject to the constraint, 2x1 minus

9
00:00:36,596 --> 00:00:40,760
x2 minus x3 equals 0.
So I've written the constraints.

10
00:00:40,760 --> 00:00:47,452
Equal to 0.
and constrained to x 1 plus, x 1

11
00:00:47,452 --> 00:00:54,120
squared plus x 2 squared minus 13 also has
to be equal to 0.

12
00:00:54,120 --> 00:00:58,122
So the first step is just to write down
the Lagrangian,

13
00:00:58,122 --> 00:01:03,168
so If I have two constraints, the form of
the Lagrangian is going to be

14
00:01:03,168 --> 00:01:06,996
objective function plus lambda 1, times
the first

15
00:01:06,996 --> 00:01:11,510
constraint, plus lambda 2 times the second
constraint.

16
00:01:11,510 --> 00:01:14,669
And then I just have to substitute these
things

17
00:01:14,669 --> 00:01:17,360
in, so f of x is my objective function.

18
00:01:17,360 --> 00:01:20,320
That's 4 x 2 minus 2 x 3.

19
00:01:20,320 --> 00:01:23,330
So that's what I've put here.
Then minus lambda

20
00:01:23,330 --> 00:01:25,350
1 times the first constraint.

21
00:01:26,446 --> 00:01:28,654
sorry, plus lambda 1 times the first

22
00:01:28,654 --> 00:01:32,110
constraint, plus lambda 2 times the second
constraint.

23
00:01:36,870 --> 00:01:40,500
And then I need to also check my necessary
condition.

24
00:01:40,500 --> 00:01:44,322
So, if I look at the gradient, the
gradient of the

25
00:01:44,322 --> 00:01:48,590
first constraint is going to be 2 minus 1,
minus 1.

26
00:01:50,200 --> 00:01:55,868
And the gradient of the second constraint
is going to be,

27
00:01:55,868 --> 00:02:00,020
2 X 1 plus, two X one, 2 X 2, and 0.

28
00:02:05,120 --> 00:02:07,220
And so you have to just look at this a
little

29
00:02:07,220 --> 00:02:10,670
bit and convince yourself that it's always
going to have pivots.

30
00:02:10,670 --> 00:02:14,444
So one way this could not have a pivot is
if

31
00:02:14,444 --> 00:02:18,390
x1 was equal to 0 and x2 was equal to 0.

32
00:02:18,390 --> 00:02:24,685
But if that were the case, I wouldn't be,
I wouldn't satisfy this constraint

33
00:02:24,685 --> 00:02:30,195
because negative 13 would not be equal to
0, and then if x1 and x2

34
00:02:30,195 --> 00:02:35,459
are any other values and I were to, I get
this 2 as a pivot for free

35
00:02:38,330 --> 00:02:40,779
If I did any sort of row operation with

36
00:02:40,779 --> 00:02:44,440
this row, I would turn this 0 into
something else.

37
00:02:44,440 --> 00:02:46,818
So, if I had to do a row operation to

38
00:02:46,818 --> 00:02:50,510
get a pivot, here, this zero would become
non zero.

39
00:02:50,510 --> 00:02:55,140
So, it's a, it's a little bit of a, you
have to make a little more of an argument.

40
00:02:55,140 --> 00:02:58,200
It's not something you can always, just
see very clearly.

41
00:02:58,200 --> 00:03:01,150
That that this condition is going to be
satisfied.

42
00:03:01,150 --> 00:03:03,346
But you should well I guess it would be a

43
00:03:03,346 --> 00:03:04,700
good habit to, to check.

44
00:03:08,340 --> 00:03:11,940
Okay, so, start off with Lagrangian that I
had on the previous slide

45
00:03:16,210 --> 00:03:19,000
And I'll compute the gradient of the
Lagrangian, so

46
00:03:19,000 --> 00:03:21,560
I'm not going to do the matrix vector
notation.

47
00:03:21,560 --> 00:03:25,774
I just, this is a function of five
variables, so I'm just

48
00:03:25,774 --> 00:03:30,459
going to do the five partial derivitives,
one by one, by hand.

49
00:03:32,110 --> 00:03:33,630
And just to make it fit on a slide.

50
00:03:33,630 --> 00:03:35,398
It was too wide as a row vector so

51
00:03:35,398 --> 00:03:38,390
I wrote it as a column vector, and then
transposed.

52
00:03:39,610 --> 00:03:41,612
And to find the critical points

53
00:03:41,612 --> 00:03:45,539
of the Lagrangian, I now have to solve for
Lambda 1, Lambda

54
00:03:45,539 --> 00:03:49,350
2, X1, X2, and X3 to make this vector
equal to zero.

55
00:03:53,060 --> 00:03:55,170
So, sometimes you get a little bit of
help.

56
00:03:55,170 --> 00:03:57,282
So, I can look and I, I find the middle

57
00:03:57,282 --> 00:03:59,922
row here, row number three, if I set this
equal

58
00:03:59,922 --> 00:04:02,232
to 0 there's only going to be one value of

59
00:04:02,232 --> 00:04:04,990
lambda 1 that's going to make that equal
to 0.

60
00:04:04,990 --> 00:04:08,398
So I get one of the one's for free, but
now I'm going to have

61
00:04:08,398 --> 00:04:12,040
to do some, some work to get the, get the
rest of the values.

62
00:04:14,720 --> 00:04:17,280
So I get Lambda 1 equals negative 2 for
free.

63
00:04:17,280 --> 00:04:24,100
And then I have to take the other rows,
and set them equal to zero.

64
00:04:24,100 --> 00:04:28,480
So, once I set these equal to 0, then I
have four equations and four unknowns.

65
00:04:28,480 --> 00:04:32,300
They're not linear anymore, so there might
be multiple solutions to this.

66
00:04:32,300 --> 00:04:36,026
So, for instance, the, the last equation
is has

67
00:04:36,026 --> 00:04:39,300
X squared and X1 squared and X2 squared in
it.

68
00:04:40,910 --> 00:04:45,030
but I can do some simplification because I
know these lambda 1s.

69
00:04:45,030 --> 00:04:48,039
They're going to be equal to negative two,
so I can put a, I can

70
00:04:48,039 --> 00:04:52,350
substitute in a negative two, to get
myself out of a little bit of work.

71
00:04:52,350 --> 00:04:58,100
But I have to find lamba two, X1, X2, and
X3, that are going to solve this.

72
00:04:58,100 --> 00:05:02,420
And the other tricky part is I not only
have to find

73
00:05:02,420 --> 00:05:05,948
The solution but I have to find all of the
solutions because

74
00:05:05,948 --> 00:05:09,404
the only guarantee that I get is that the
optimal val, the

75
00:05:09,404 --> 00:05:14,084
critical points are going to include the
extreme values, it doesn't tell me

76
00:05:14,084 --> 00:05:18,476
that the, you know, once I have once of
those critical points, whether

77
00:05:18,476 --> 00:05:22,900
it's a maximum or a minimum, and so if I
find one solution.

78
00:05:22,900 --> 00:05:26,554
When I'm looking for a maximum, and that
one just happens to correspond to

79
00:05:26,554 --> 00:05:28,468
a minimum, then instead of solving the

80
00:05:28,468 --> 00:05:31,310
problem I've actually found the worst
possible solution

81
00:05:31,310 --> 00:05:34,580
for, you know, any other, any other vector
would be better.

82
00:05:35,940 --> 00:05:37,968
So you have to not only find the solution
to this

83
00:05:37,968 --> 00:05:40,530
but you have to find all of the possible
solutions to this.

84
00:05:43,860 --> 00:05:46,827
And so, if you do a little algebra, which
I decided

85
00:05:46,827 --> 00:05:49,863
to skip in the interest of brevity, you
can solve for

86
00:05:49,863 --> 00:05:52,692
X1, X2 and X3, in terms of lambda two, and
so

87
00:05:52,692 --> 00:05:56,470
you end up with these three expressions
for X1, X2, and X3.

88
00:05:56,470 --> 00:06:00,389
And I got those just from the first three
equations.

89
00:06:01,540 --> 00:06:05,026
And then I'm going to combine that with
the fact that

90
00:06:05,026 --> 00:06:08,680
I know x1 squared plus x2 squared is equal
to 13.

91
00:06:08,680 --> 00:06:08,882
So

92
00:06:08,882 --> 00:06:12,518
I can plug x1, so 2 over lambda 2, in for

93
00:06:12,518 --> 00:06:17,130
x1 here, and minus 3 over lambda 2 in for
x2 here.

94
00:06:18,180 --> 00:06:21,542
And what I end up getting is 13 divided by
lambda

95
00:06:21,542 --> 00:06:24,986
2 squared, is equal to 13, and so that
tells me

96
00:06:24,986 --> 00:06:28,266
that lambda 2 squared has to be equal to
1, and

97
00:06:28,266 --> 00:06:31,730
that lambda 2 is then going to be plus or
minus 1.

98
00:06:31,730 --> 00:06:34,076
And now because x1, x2,

99
00:06:34,076 --> 00:06:38,564
and x3, they're functions of lambda 2, It
means

100
00:06:38,564 --> 00:06:42,740
I'm going to end up with this, so the
Lambda one.

101
00:06:42,740 --> 00:06:46,220
That's fixed at negative 2, that will
always be negative 2.

102
00:06:46,220 --> 00:06:48,985
Then my other critical points are going to
be

103
00:06:48,985 --> 00:06:52,110
Lambda 2 equals positive 1, x2 equals 2.

104
00:06:52,110 --> 00:06:57,890
Sorry, x1 equals 2, x2 equals negative 3,
and x3 equals 7.

105
00:06:57,890 --> 00:06:59,186
Or, lambda 2 equals

106
00:06:59,186 --> 00:07:00,050
negative 1.

107
00:07:00,050 --> 00:07:04,006
And then I'm going to get negative 2,
positive 3, and

108
00:07:04,006 --> 00:07:06,640
negative 7 for my x 1, x 2, x 3.

109
00:07:06,640 --> 00:07:11,540
So, these are the, the two critical
points.

110
00:07:12,890 --> 00:07:16,580
And then if you evaluate f at this
critical point.

111
00:07:16,580 --> 00:07:20,293
So, this lambda kind of wants I'm using
that as a crutch

112
00:07:20,293 --> 00:07:24,243
to get myself to here, but once I've got
the critical point

113
00:07:24,243 --> 00:07:28,746
for the x's, those are actually the ones I
want to evaluate because

114
00:07:28,746 --> 00:07:33,360
I'm trying to find the maximum and minimum
value of this function f.

115
00:07:33,360 --> 00:07:38,340
So then I just have to evaluate f at all
of those critical points that I found.

116
00:07:39,590 --> 00:07:42,505
And then whichever one is the biggest,
that's the maximum, and

117
00:07:42,505 --> 00:07:45,460
whichever one is the smallest, that's
going to be the minimum.