Good morning or good afternoon I'm Esteve Codina and I'm going
to present this video multivariate functions and local extrema
corresponding to the BLOCK 3: Calculus
We will go through the following contents.
We will go first to examine which are the learning objectives.
And next we will go into an introduction and we'll go next into the multivariate
functions reminder; a concept that you already see in the previous videos.
Next we will see which are the first order conditions
for interior, global and local minima for these multivariate functions.
We will solve the first order conditions using an example
of pen and paper and next,
we will see the idea of the gradient method for finding global,
sorry, local minimum of a function.
We will finally go into the key learning concepts and give some references
and extensions.
Okay,
so the learning objectives is to get the notion of
what is a global/local, maximum or minimum of a multivariate real function.
In case that it's possible to calculate the derivatives
of this multivariate function,
we will see a condition that maximum and minimum must verify.
And in case of the minimum,
we will see how the gradient method operates for obtaining approximate
local minimum.
Well, we have seen
that there are many problems in engineering that are solved finding
the values of variables of a given system that maximize or minimize some function.
And in this video we will extend the concept of maximum/minimum
to the case of real multivariate functions.
We saw in the previous video the case of univariate functions, and show
how can they be approximately found this maximum/minima by using
the gradient method.
Okay, let's
have a reminder of what a multivariate function is,
so we can see here in the example a function F,
which depends on two arguments X and y; so, a multivaried
function is some function which has more than one argument.
And we can see here in the and the graph a 3D representation of the function
thinking at the third axis, as the axis
on which this non-positive function takes values.
The level sets we will see them on the on the right hand side of the slide.
They are simply curves in which the function takes constant values.
So if we walk through these curves, the function wouldn't change its value.
It's like we, many of you will remember geographical charts,
because actually they are in this case geographical charts
and but they are very useful for illustrating
our concepts with multivariate functions two variables.
So, next we
will see ... let's make a reminder of what partial derivative is
and how they can build the gradient vector
Let's consider this simple function
two of two arguments, two varaibles: x squared plus y squared.
So the partial derivative of this function G with respect x
is the one that is obtained by considering the other variable y.
as constant and carry out an ordinary derivative with respect to x.
So the partial derivative
is designated by this the symbol
and in this case for the partial derivative of G with respect to x,
will be 2x, the partial derivative of g with respect to y would be 2y.
If we we pile up these two partial derivatives
and make a vector, we will obtain the one that is on the on the right hand
side at the bottom, and it's designated by the gradient vector.
It's usually by
this 'nabla' operator, which is these upside down triangle.
So the gradient vector, at ab arbitrary
point of this function is the vector 2x and 2y.
Okay. So
we can see here in this, in this, in this slide,
which are the level sets for our function g of 'x' and 'y'
equal x squared plus the y squared, which is a non-negative function.
So it's a because it's a non-negative function, we see clearly that, at the point
x = 0, y = 0, it will achieve its minimum possible value.
So actually x = 0, y = 0, would be a global
minimum of the function and
at point x = 0.707
and y = 0.707,
we see evaluated the gradient.
The point (0.707, 0.707)
is the red point on the level set.
And we see that the gradient vector
is the fastest uphill direction.
Of course,
if we take the negative of the gradient vector will obtain the fastest downhill
descent direction, and this will be
the one we will use for our gradient method for minimizing
real multivariate functions.
Okay, so we have seen that for our function,
g = x^2 + y^2,
that it achieves a global minimum at point (0,0).
In there, the gradient
vanishes: is equal to zero.
So and it happens that for a differentiable function,
any local minimum or maximum also verifies this condition.
So a method for finding a local minimum or maximum can be to find solutions
of the equation:
gradient of the function equal to zero, which actually are the first
order conditions. Yes,
but we should be cautious because actually there are there exist
functions like this one, which is a rather simple x^2 - y^2
in which, if we calculate its gradient, it also vanishes at point (0,0)
and but (0,0) is neither a local maximum nor minimum.
But it is the solution of the equation gradient of h = 0.
Such points are called the stationary points.
So depending on the
function, stationary points, the solutions of gradient of the function =0
can be local maxima, local minima, or neither of them
as it happens in this example.
Sometimes finding local minima
or solutions of the
gradient of the function equals zero can be done with pen and paper.
We can see a very simple example in here.
Sorry,
not in this slide.
Right. So, the example of pen and paper.
We have here a quadratic function.
We only with a squares and cross products plus linear terms, let's put it in this way,
and we calculate the
the gradient of the function.
So the gradient of the function is these two components
and we impose it to be =0.
We then form this linear system of two variables,
whose solution can be obtained very easily
with and paper,
which is the point x = -7 and y = -3.
So we've found the only stationary point of this function.
However, however,
when solving
the equation gradient of the function = 0,
we have seen that we can find local maximum, local minima, or neither of them.
And here we see an example of this function, and
we have depicted the 3D graph
and the level sets. Local maxima appears at points A and B
when solving for a gradient of the function = 0.
Local minima is, for instance, the point C,
but also will appear the point D which is neither
local maxima nor local minima.
So let's go now
into the idea of the gradient method.
This, this method can be applied when there are many variables
or there are other difficultes and for finding local minima.
And it's known that it was found by Cauchy and published in the year 1847.
Let's have a general idea
of it and imagine the first function of that we have seen in this video.
And you see here the level two sets of this region.
In the end in the central part
of the of the box interval on which is defined.
So the gradient method
basically starts by considering an arbitrary point x sub zero.
On that point, it calculates the minus
gradient direction, which is the steepest descent direction.
And along this direction
it makes an exploration in order to find the smallest possible value.
Right?.
So notice at that point x sub zero, there is a blue vector
emanating from it, which is a descent direction,
and we then stop at point x sub one because it yields
the smallest possible value of the function along that direction.
Once we found this smallest possible value,
we stop at that point and repeat the operation we calculate
another blue vector
consisting of the minus gradient, the steepest descent direction,
and then by scanning it, the values of the function
on that segment we will find point x sub 2.
And so we will repeat the procedure finding x sub 3, x sub 4 ...
so we'd be getting closer and closer to the optimal,
I mean, to the local minimum point of the function,
which is the red point in the level set.
Okay.
So formally the gradient method is going to be formlized in this way.
We start at an arbitrary point we set the counter k = 0.
We evaluate the steepest descent direction = minus the gradient value .
at the point x sub k
And then we see that the step number two is some sort of
of an approximate condition for the first order conditions.
So we check whether the gradient of the function is small, near zero.
If it's like that, then we stop the procedure
and we accept that x sub k is the stationary point.
Otherwise what we do is we examine
the function along the steepest descent direction,
And then we find as new iterate the point that
minimizes the function on that direction and then
we repeat the the procedure going to the step number one.
So, the key learning concepts we have reached.
We have introduced
the idea of global maximum, a minimum of real multivariate function
and also the idea of local maximum and minimum
we have used, we have introduced examples, of the first order conditions
that not only maximum and minimum verify, which are called stationary points.
Stationary points are the
solutions of the first order conditions: gradient of the function equal zero.
And we have introduced the gradient method
for approximately calculating local minima
As references,
you can find in chapter two of Sheffi, very good compendium of these basic concepts.
If you want to see more details of these concepts,
you can go into the other these two other references.
Introduction to Methods for Nonlinear Optimization, especially Chapter two.
And if you want to get more details of the gradient
method, you can go in chapter 7 and 8.6 of the
Luenberger's linear and linear programing book by Springer.
So thanks for your attention. And that's all