welcome to this fourth lecture in the
series of lectures on numerical
optimization so so far in the last two
lectures we saw some mathematical
background needed for this course and
some of those concepts will be useful
for understanding from the theory that
we are going to see today especially the
concepts on differential calculus and
some analysis so in today's lecture we
will look at unconstrained optimization
problems how how to solve those problems
what are the necessary and sufficient
conditions for the solutions of those
problems so to begin with let us look at
a constrained optimization problem which
is given here so you have a function f
from the domain X to R and X is a subset
of RN and our aim is to minimize the
function f where X belongs to the set X
so this is a constrained optimization
problem but any unconstrained
optimization problem is a special case
of this constrained optimization problem
in the sense that if I replace this X by
RN then it becomes a unconstrained
optimization problem so our aim is to
solve this problem and for that we need
the definition of a minimum ok so X star
and belonging to the set X is said to be
a global minimum of F over X if the
value of x star the value of the
function at X star is less than or equal
to the value of the function at any
other point in the set X so such a point
X star is said to be a global minimum
for example let us consider a problem
where you have a function on the Left
panel which is shown in the black line
and let us assume that the constraint
set is only this interval then you will
see that the global minimum of this
problem is it occurs at this X and the
corresponding minimum value of the
objective function is shown here now on
the right panel you will see another
function which is not as nice as the
function on the Left panel so you will
see that there are lots of peaks and
lots of valleys and suppose we restrict
ourselves to this interval and assuming
that the function goes to plus infinity
beyond these points although it is not
of interest to us we are only interested
in this small interval and you will see
that in this interval this is the point
where the function achieves the least
value and the corresponding X star turns
out to be this so among all possible
points in the domain of that function on
which we want to minimize the function
this is the point where the function ID
achieves
the least value so this is called a
global minimum similarly one can define
what is called a global maximum so in
the definition of global maximum this
inequality will will be reversed so f of
X star greater than or equal to f of X
for all X belongs to X for X star to be
a global maximum now in this course many
times I will be talking about
minimization problems of this type but
the ideas that we discuss here can be
easily extended by writing to the
maximization problem by writing a
maximization problem as a minimization
problem which we saw how to do that was
seen in the first lecture now the
question is that are there any
conditions on F or on X or both
so that the function f does attain its
maximum or minimum in the set X so can
we have some conditions on this F as
well as on X so that the the minimum or
maximum is guaranteed in the set X now
for that let us look at some examples so
let us take a function FX equal to X
cube where the domain of the function is
a set of real numbers and the function
is defined from R to R okay now the
function is shown here in this plot so
on the right side the function goes to
plus infinity as X goes to plus infinity
and on the left side the function goes
to when X goes to minus infinity the
function goes to minus infinity now you
will see that over the domain X equal to
R this function has neither a minimum
nor a maximum because the function
extends to plus infinity and minus
infinity so it has no minimum or no
maximum now in this case if you look at
the domain set which is X that's a
closed set the set of real numbers R
that's a closed set but it's not a
bounded set so so that means naturally X
is not a compact set now do we want X to
be bounded and not necessarily closed we
do not know as of now let us see another
example now here is an example where the
domain X is a open interval A to B and
the function f is from X to R and
defined as f of X equal to X so the
function is shown in this figure
and so you will see that these endpoints
are not included in the domain so that's
why they are shown using some special
symbols now if you look at this domain
this domain is now bounded so
like the previous case where the domain
was not bounded here the domain is
bounded but it is not closed so I again
X is not a compact set now you will see
that if attends neither a minimum nor a
maximum on X because F of a and F of B
are not defined so we cannot have a
minimum value of the function in this
open interval A to B but in this case
you can get a bound on this minimum and
maximum values and those are called
infimum and supremum so the infimum of
this function is f of a which is
attained at X equal to a and the
supremum of this function is f of B
which is attained at B but remember that
a and B do not belong to the domain so
we cannot say that the minimum or
maximum is attained but in this case the
infimum and supremum are possible so so
far we have considered two examples
where the domain X in one case was not
bounded but closed in the other case it
was bounded but not closed so that that
essentially means that the domain was
not a compact set now so does that does
that mean that do we need the X to be
compact to attain a minimum okay so let
us look at one example so let us
consider domain X to be the closed
interval minus 1 to 1 now it is a closed
set as well as a bounded set so hence it
is a compact set and let us define a
function f from X to R as f of X equal
to X if X is in the open interval minus
1 to 1 and 0 otherwise so in the open
interval minus 1/2
the function is a straight line and at
the endpoints the function has a value
zero so clearly you will see that the
function is a discontinuous function on
the site X now again we can say that the
F does not attain a minimum or a maximum
in this set X so remember that here X is
a compact set and F is not continuous
so compactness of X alone was not enough
probably we need something some more
conditions on F and that condition is
the continuity of function f on X so
suppose if we have X to be a compact set
and F to be a continuous function on the
set X then can we say something so these
leads us to the wise of stress the the
Weierstrass theorem which states that if
X which is a subset of RN is a nonempty
compact set and F is from X to R is a
continuous function on X then F does
attain a maximum and a minimum of X that
is there exists some x1 and some x2
belonging to X such that f of X is less
than or equal to f of X 1 for all X
belongs to X and f of X greater than or
equal to f of X 2 for all X belonging to
X so so this theorem was proposed by
Weierstrass will not go into the proof
of this theorem but it gives us
sufficient conditions for the existence
of optima that is the if f is a function
defined from X to R then we need X to be
compact and F to be a continuous
function on X then it is guaranteed that
the there exists two points X 1 and X 2
such that f of X 1 greater than or equal
to f of X greater than or equal to f of
X 2
for all X belongs to X so as I said that
this Weierstrass theorem just provides a
sufficient consistent exist conditions
for existence of Optima but it does not
give you the necessary conditions for
the existence of Optima for example
suppose we take a function f which is I
haven't written the explicit form of
this function here but assume that the
function has a form like this now the
function is defined on a closed interval
A to B the closed interval A to B is a
closed and bounded set and hence it is
compact but the function f is not
continuous here you will see that there
is a break in the function and this at
this point now although if it is not
continuous you will see that the
function does attain a minimum at this
point and the minimum value of this
function is somewhere here so although F
X is not continuous F does attain a
minimum in the closed interval a B for
this case so this example illustrates
that and the conditions of vyse Trust
theorem are not made but the function
does have a minimum right so why stress
theorem does not talk about necessary
conditions for existence of Optima it
only talks about the sufficient
conditions for Optima now here is a
another example let us define a function
FX as X minus 2 square and defined from
R to R and the function is shown here
now you will see that the function is
continuous what X is not compact the set
R of real numbers is not a compact set
so again the conditions required by
Weierstrass theorem are not met because
X is not compact but despite this fact
the function
does attained a minimum at this point
and the corresponding X star is
somewhere here so we'll see so you will
see that Weierstrass theorem just gives
sufficient conditions for existence of
optima or up many optimum points but
does not give the necessary conditions
for the existence of Optima but anyway
it is a useful theorem in the sense that
under if those conditions are made like
if F is a function from X to R and X is
compact and F is continuous on X then
the minimum and the maximum are of the
function f are guaranteed in the set X
so now let us look at a general problem
so you will see that on the Left panel
we will see that figure which we saw
earlier in this lecture that the
function is very nice and attains
minimum at a single point and on the
right panel you will see a function
where there are lots of peaks and
valleys and if you look at this point
for example so in the neighborhood you
will see that the function is increasing
and the function has the least value in
this if you consider a neighborhood
around this point but this value is
still higher than the value which is
called a global minima right now it
turns out that finding this global
minima is difficult for example it is
very difficult to characterize or find
the global minimum for a general
nonlinear function so if you have a
function which is nice as on the left
panel it is easy to find the global
minimum while on the song on the right
panel you will see a function whose
global minimum is very difficult to find
and suppose we find this point which is
a global minimum then can we say that it
is a global minimum so for that purpose
we need to look at the value of the
function at all the points and to
ascertain that f of X star is less than
or equal to f of X for all X belong to X
and that's going to be a very difficult
task so identifying a global minimum or
characterizing it is very difficult for
a general nonlinear function only in
some special cases one can characterize
them very easily we will see those cases
sometime later in this course but as of
now we know that it is difficult to
characterize this one this global minima
so it resulted in the concept of a local
minimum so again let us consider X to be
a subset of RN and F to be a function
from X to R and let us consider a
constrained optimization problem and we
are trying to minimize f of X subject to
X belongs to X now X star belongs to X
is said to be a local minimum F if there
is a delta greater than 0 such that in
the Delta neighborhood of x star the
value of the function is less than or
equal to the value of the function at
all points in the neighborhood so so if
you look at this this point in the
neighborhood you will see that the value
of the function is less than or equal to
all the points so if you take a small
neighborhood remember that Delta in the
definition of local minimum can be very
small so if you take a small
neighborhood around this point and find
out the function values at all the
points you will see that the value of
the function is at least the value of
all the value of the function at all the
points in the neighborhood so similar
similarly in this case it
true that the value of the function is
at least the value of the function in
the neighborhood however small
neighborhood that you would take and
same is true in this case also but here
interestingly the function is almost
flat in some range and then in one
direction it starts increasing in the
other direction it starts decreasing so
such points in which the function
increases in one direction decreases in
the other direction and they are they
are called the saddle points so and
similarly in this case of course this is
a global minimum so it also is a local
minimum because in the neighborhood the
function value increases so from this
definition one can extend this
definition to the definition of local
maximum so again as I said earlier that
the inequality reverses in this
definition so again one has to take a
local neighborhood can be sufficiently
small and find out the value of the
function in the local neighborhood and
you will see that these points are local
Maxima ok so the definitions of local
minimum and local maximum they are
centered around the neighborhood of a
given point now let us consider one
example so here the function is shown
here now let us take a point X star now
X star by the definition of local
minimum that there exists a neighborhood
around X star so that the value of the
function is f of X is greater than or
equal to f of X star so because of that
definition there is a problem in this
case mainly that since we are allowing f
of X star greater than or equal to F
X for all X in the neighborhood of X
star so you will see that X star turns
out to be a local minimum because of the
definition but by looking at the
function assuming that the function goes
to minus infinity in both the directions
when X goes to plus infinity and minus
infinity so you will see that X star
indeed is a global maximum so you have X
star is a to be a local mean and as well
as a global maximum now to avoid such
cases one can think of a definition of a
strict local minimum now X star
belonging to X is said to be a strict
local minimum of F if f of X star is
less than strictly less than f of X for
all X in the neighborhood of X Delta
neighborhood of X star and X not equal
to X star so you will see that then if
we use this definition then X star Iza
is a local mean but not a strict local
mean and also it is a global max because
the function value is highest at X star
of course at the other point in the at
the other neighboring points also the
function value is highest so remember
that the global minimum or global
maximum they need not be unique so this
is one example where you have a multiple
global Maxima and X star is not a strict
local mean so all these points which are
in the neighborhood they are not strict
local minima so now let us look at the
function again the fungus function we
saw earlier so these are the points
which are local minima and not only
local minima they are strict local
minima now this is a point which is a
weak local minimum so you will see that
f of X star is less than or equal to f
of X in the neighborhood of
extra so such points are weak local
minima and this point is a global
minimum now earlier I said that this
global minima are difficult to
characterize so one may wonder that how
about finding different local minima
strict local minima or big local minima
collecting them together and then trying
to find out the least among those so
this idea may work in some cases but may
not work always for example suppose I
have a function which is shown here and
it goes to minus infinity so the domain
of the function is a set of real numbers
and you will see that this X star is a
local minimum in fact it is a strict
local meaning because the value of the
function in the neighborhood of x star
that does not reach f of X star at any
point other than X star so it's always a
it always exceeds f of X star so now if
you look at this function and if you
collect all the local minima which is 1
in this case that will not give you a
global minima because the function does
not have a global minimum the function
goes to minus infinity in both positive
x as well as then you get you x
direction so by collecting all local
minima it is not always guaranteed that
we can find a global minimum of a
function so one has to check whether the
function has a proper form so that
collecting all local minima can give us
a
so now let us look at the unconstrained
optimization problems as I said earlier
that if we are trying to solve a problem
from to minimize the function f from
where X belongs to capital X and F is a
function from X to R and X is a subset
of RN so this is a general constrained
optimization problem and an
unconstrained optimization problem is a
special case of this now to solve a
constrained optimization problem many
times we need to solve an unconstrained
optimization problem first I will so see
those techniques later but solving an
unconstrained property optimization
problem is important to solve a
constrained optimization problem now to
solve an unconstrained optimization
problem one has to solve many one
dimensional unconstrained optimization
problems which are of this type so in
today's talk will focus on solving one
dimensional unconstrained optimization
problem they are very important to solve
unconstrained multi dimensional
optimization problem and these
unconstrained multi dimensional
optimization problems are important to
solve the general constrained
optimization problem so this being an
important problem will spend some time
studying about the solutions of these
types of problems so here is a
unconstrained one-dimensional
optimization problem where F is a
function from R to R so remember that
now we are not worried about the set X
in this case the domain of the function
is the entire set of real numbers the
range is also the entire set of real
numbers now we want to solve this
problem and as we saw earlier that it is
very difficult to identify the global
minima of a function so we will restrict
ourselves to local minima now the ideas
that we see here and
easily extended to finding local maxima
also so the natural question that one
would like to ask is that what are the
necessary and sufficient conditions for
a local minimum now what what do we mean
by the necessary and sufficient
conditions so necessary conditions are
the conditions which are satisfied by
every local minimum for example if
suppose X star is the local minimum of
this problem then we can say that if X
star is a local mean then certain
conditions are satisfied and those
conditions are called necessary
conditions and by sufficient conditions
we mean those conditions which guarantee
a local minimum for example if at X star
belong to are certain conditions are
satisfied then we can say with guarantee
that X star is a local minimum now as we
saw earlier that there exists lots of
there might exist lot of local minima
for a general nonlinear function then
how do we characterize such local minima
that's the next question that we would
like to answer because again we do not
want to find a local neighborhood along
around X star and check whether the
value of the function exceeds the value
of the function at X star because there
could be infinitely many points again in
the neighborhood and we do not want to
ensure we do not want to have any
conditions which will require finding
different points in the neighborhood and
checking the function matters
so instead is there any algebraic
approach to check whether a particular
point X star is a local minimum now the
ideas of differential calculus come
become very useful in this case so if
the function is sufficiently smooth that
means it's a first order derivative
second order derivative and so on they
exist and they are continuous
then one can arrive at different
conditions for characterization of local
minima so we are going to see those
conditions now now let us consider a
function from R to R and F belongs to C
1 so this C 1 denotes the class of
functions whose first derivatives are
continuous ok so now we are restricting
ourselves to functions whose first
derivatives are continuous and let us
consider the problem to minimize f of X
where X belongs to R now here is the
first set of conditions called first
order necessary conditions the result is
very simple if it says that if X star is
a local minimum then f dash X star is
equal to 0 so which means that the
derivative of the function vanishes so
if X star is a local minimum the
derivative of the function at X star
vanishes so these conditions are called
the first order necessary conditions
they are necessary conditions because if
X star is a local minimum of F then
these conditions are satisfied so that's
why they are necessary conditions and
they use the first order derivative
information so that's why we call them
as first order necessary conditions now
let us look at the proof of this result
the proof is based on the fact that let
us so we have a statement which is of
the type a implies B so what we do is
that we assume that B is not true and
then say that a is not true so we saw
this method of proof in one of our
earlier lectures so let us assume that F
dash X star is greater than 0 so the
result says that if X star is a local
minimum then f dash X star equal to 0 so
on the contrary let us assume that F
dash X star is greater than 0
and then we will prove that in such a
case X star cannot be a local minimum
okay now since F belongs to C 1 so it's
derivative it's a continuous function so
that means F dash belongs to C naught so
let us take a interval a D which is of
size 2 Delta around X star so X star
minus Delta 2 X bar X star plus Delta is
open interval so let this interval be
chosen such that the derivative of the
function at any point in this interval
the derivative of the function at any
point in this interval is greater than
zero now that is possible a it is
possible to get such an interval because
we are assuming that F belongs to C 1 so
at least in the neighborhood F Dash is
continuous and we are assuming that F
dash X star greater than 0 so at least
in the neighborhood F dash X is greater
than 0 now if you write the truncated
Taylor series expansion of f of X around
X star and truncate it to the first
order so what we get is the f of X is
nothing but f of X star plus F 2 dash X
bar into X minus X star where X bar is a
point on the line segment joining X star
and X now remember that f dash X bar is
greater than 0 because X bar is a point
in the interval D so f dash X bar is
greater than 0 now we are free to choose
any X in the interval D so suppose we
choose X to be in the open interval X
star minus Delta to X star so X minus X
bar X minus X star will become negative
because X X lies in this interval so X
minus X star becomes negative
so X minus X star becomes negative f
dash X bar is greater than zero so
therefore f of X will become less than f
of X star and that contradicts the fact
that X star is a local minima now one
can use similar ideas by assuming that f
dash X star less than zero and then the
rest of the things follow as they are
except that you choose the point in the
open interval X star to X star minus x
star plus Delta
so in that case f dash X bar will be
less than zero and this quantity is
greater than zero so that product will
be less than zero and therefore f of X
will be less than f of X star so in
either case we come up with the
contradiction that X star is not a local
minimum so so if X is a local minimum
then the first derivative of the
function should vanish now here are some
examples so on the Left panel you will
see a function f of X which is X minus 2
square and the derivative of the
function at 2 vanishes so you will see
that the function has a zero slope at X
equal to 0 and then on either side the
function is increasing now on the right
panel you will see one function which is
f of X equal to minus X square and at x
equal to zero you will see that the
slope of the function is zero but in
this case X equal to zero turns out to
be a global maximum and in this case it
turns out to be a global minimum if
assuming that the function extends to
plus infinity here and function goes to
minus infinity in this case so the slope
of the function is zero at a local
minimum as well as at the local Maxima
so looking at the slope really does not
tell us much about the minimum or
maximum of a function at that point
now let us consider one more case so on
the right panel you will see a function
f of X equal to X cube so this f dash X
at X equal to 0 is 0 but you will see
that the function increases in one
direction and decreases in the other
direction so if you move X to minus
infinity the function goes to minus
infinity so the slope of the function
really does not tell us anything about
the existence of a local minimum or
local maximum at that point so the
points at which the slope of the
function is 0 the such points are called
saddle points
sometimes people also call it stationary
points so the saddle points really do
not give us any idea about the local
minima or Maxima so we need some extra
information and as I said that f dash X
equal to 0 is just a necessary condition
for a local minimum but not a sufficient
condition so if you collect all points
for which F dash X star equal to 0 such
points are called stationary points now
since we are interested in solving a
problem of the type minimize f of X
where X belongs to R the natural
question that we would like to ask is
that how do we ensure that a stationary
point is indeed a local minimum and we
have seen the case that checking the
gradient of the function or taking the
derivative of the function in the
one-dimensional case does not really
guarantee a local minimum right so let
us look at the second order information
now on the left panel you will see the
same function f of X equal to X minus 2
square now the derivative of the
function vanishes at this point the
second derivative of this function at X
equal to 2 is 4 and that is greater than
0 now on the right panel
you will see the function f of X equal
to
six square the first derivative of the
function at X equal to zero is zero and
the second derivative of the function at
X equal to zero is minus two so you will
see that for this function the the
second derivative of the function at
this point is positive and for this
function the second derivative of the
function at this point is negative so
the second derivative in some sense
talks about the curvature of the
function at that point so this function
has a positive curvature at this point
and this function has a negative
curvature at this point so you will see
that although the first derivatives of
these two functions at these points are
zero it is the second derivative which
tells us about the curvature and that
tells that this point it indeed is a
local minimum and this point indeed is a
local maximum so so let us look at the
second order necessary conditions now
for the second order necessary
conditions we need the second derivative
of the function so let us assume that
the F belongs to C 2 that is the second
derivative of the function is continuous
and the function is from R to R and we
are interested in solving in one
dimensional unconstrained optimization
problem now here is a result about the
second order necessary conditions now if
X star is a local minimum of F then the
first derivative at X star vanishes and
the second derivative is non-negative so
this result gives us so the necessary
conditions we choose the second order
information of the function now how do
we prove this so the proof is very easy
now the by the first order necessary
conditions we know that if X star is a
local minimum then f dash X star equal
to 0 we already proved that result now
let us assume that the second derivative
is less than 0 at X star and then we
will come up with the contradiction now
since F belongs to C 2 the second
derivative of the function is a
continuous function so again as in the
previous case let us choose an interval
around X star of size 2 Delta so this is
the interval D X star minus Delta X star
plus data now since F 2 Dash is
continuous we can always choose this
interval such that for any point in this
interval D and the second derivative is
less than 0 because we have assumed that
F 2 dash X star is less than 0 so now
let us write down the second-order
truncated Taylor series so f of X is
nothing but f of X star plus F dash X
into X minus X star plus half F 2 dash X
bar into X minus 6 X star square X where
X bar is a point on the line segment
joining X star and X now we know that
from the first order necessary
conditions that F dash X star equal to 0
now we also have chosen this interval
such that F 2 dash X is less than 0 for
all X belongs to D and X bar belongs to
this interval so if F 2 dash X bar is
also less than 0 now now this quantity
this should be X X star so this quantity
is 0 and F 2 dash X bar is less than 0 X
minus X star square is greater than 0 X
minus X star square is greater than 0 so
so you will see that this quantity
vanishes and this quantity is less than
0 so which means that f of X is less
than f of X star and which is a
contradiction so so we will see that we
see that if X star is the local minimum
then f dash X star equal to 0 and F 2
dash X star greater than or equal to 0
so remember that this is f dash X star
and by first order necessary conditions
F dash X star equal to 0
now the question is are these
second-order sufficient conditions are
the second order necessary conditions
also sufficient and the answer is no
because if you consider a problem which
is to minimize X cube subject to X
belongs to R the function is drawn here
now at this point the first derivative
and the second derivative both are 0 but
then extract turns out to be a saddle
point so so these conditions are
necessary for the existence of a local
minimum but not sufficient so what are
the sufficient conditions for the
existence of a local minima so let F be
a function from R to R a belongs to C to
the second order sufficient conditions
result states that if X star is a point
on from the set R such that the first
derivative of the function vanishes at
that X star and the second derivative is
greater than 0 then X star is a strict
local minimum of of F over R so remember
that this is a result which guarantees
strict local minimum of F over R now the
proof of this is again very easy that
since I belongs to C - f - - is
continuous so we'll choose the interval
D such that in the in that interval for
any X in that interval F 2 dash X is
greater than 0 and that's possible
because F 2 dash X star is greater than
0 so let us write down the truncated
Taylor series expansion of F around X
star so f of X is nothing but f of X
star plus F dash X star into X minus X
star plus 1/2 F 2 dash X bar into X
minus X star square where X bar is the
point on the line segment X star - X now
if F F dash X star equal to 0 then F F X
minus f of X star is nothing but half F
2 F 2 dash X bar into X minus X star
square now X
Bar is a point in the interval D so f 2
- X bar is greater than 0
this quantity is also greater than 0
because it is square so the whole
quantity is greater than 0 so which
means that f of X is greater than f of X
star for all X belongs to D so at least
in the there exists some Delta greater
than 0 such that in the neighborhood
delta delta neighborhood of x star the
value of the function does not attain f
of X star in fact it is it exits f of X
star so which implies that X star is a
strict local minimum so remember that
so these sufficient conditions guarantee
a strict local minimum of F over R now
are these conditions necessary do they
though they guarantee that the local
minimum is straight they turn out to be
not necessary conditions because if we
consider a case where f of X equal to X
to the power 4 then X star equal to 0 is
a strict local minimum but then f dash X
star and F 2 dash X star
are both 0 so this second order
sufficient conditions they are not
necessary in this case so so now we have
a important result which will state
without the proof so let us assume that
f is a function from R to R and F
belongs to C infinity that is all the
derivatives of the function exists and
they are continuous let us also assume
that f is not a constant function so let
us rule out that possibility also and
let us denote the K the derivative of F
at X as FK x and consider the problem to
minimize f of X X belongs to PI now here
is the result which say that X star is a
local minimum of F if and only if
the first non-zero element of the
sequence fkx is positive and occurs at
even positivity so this is a very
important result which says that if you
take a you start taking the derivative
of the function from the first
derivative second derivative and so on
now if you consider that sequence of
derivatives of function f at x so the
the first nonzero element of the
sequence fkx star is positive and occurs
at positive even and positive K so
that's very important so if you consider
the example of f of X equal to X to the
power 4 so you will see that at if X X
star equal to 0 is a local minimum of
that function and the first 3
derivatives at X star are 0 and the
fourth derivative is positive so the the
fourth derivative that means that the K
is equal to 4 which is a even and
positive number and fourth derivative of
the function X X to the power 4 is
positive so that's why X star equal to 0
is the local minimum of FX equal to X to
the power 4 now one can have a similar
result for the local maximum so the only
change that one has to make is that the
sequence at K X star is negative the
first element of the first nonzero
element of the sequence fkx star is
negative and it occurs at even positive
K now let us see some examples to find
out the minima or Maxima minima of a
problem now let us consider the problem
minimize X square minus 1 square now the
first step to solve such problems is
always to identify the station
points and the stationary points are
found by equating the derivative to zero
so if you take the first derivative of
this function and that turns out to be
for X into X square minus 1 and that
equal to 0 implies that either X equal
to 0 or X equal to plus 1 or X equal to
minus 1 so it has three stationary
points now we need to check which of
these stationary points are local minima
or local maxima so then we need to go
for the second derivative information
now F 2-1 in this case turns out to be 8
and F 2 dash minus 1 also turns out to
be 8 and that is the greater than 0 so
you will see that the first derivative
is 0 at 1 and minus 1 and the second
derivative is positive so the first
nonzero element of the sequence F 2 dash
K if of the sequence fkx star is
positive and occurs at e1 K which is 2
in this case so 1 and minus 1 are strict
local minima and along similar lines one
can say that 2 - 0 which is minus 4 and
less than 0 implies that 0 is a strict
local maximum because this the second
derivatives negative the first
derivative 0 and 2 is a even positive
integer so 0 is a strict local maximum
now let us consider another case where
minimize f of X where X f of X equal to
X square minus 1 cube now if you look at
the stationary points again we get 3
stationary points 0 1 and minus 1 at
which points the derivative of the
function vanishes so so we look at the
second derivative now second derivative
information tells us that the second
derivative of the function at 0 is 6
which is positive which means that 0 is
a strict local minimum but at the
stationary points 1 and minus 1 the
second derivative also vanishes so we
have to look for the higher-order
derivatives so let us look at the third
derivative
now if 3 - X is a function like this and
you will see that f 3 - s F 3 - 1 is
positive F 3 - minus 1 is negative so we
really cannot conclude anything from our
result about sufficient optimality
conditions because that these
derivatives are nonzero at K which is
odd so we can just conclude that 1 and
minus 1 are saddle points of this
problem and 0 is a strict local minimum
now if you look at example X to the
power 4 and so you will see that F 3 F 4
- X is 24 which is positive and all the
earlier derivatives right from the first
second and third all these derivatives
are 0 so the first nonzero element of
the sequence fkx star occurs at K which
is even and positive and the element is
positive so which means that zero is a
strict local minima so so you will see
that to solve such problems we need to
find the derivative of the function and
identify the stationary points by
equating the derivative to zero and then
go to the higher-order derivatives from
the second order derivative onwards to
see whether we can conclude anything
about the stationary points whether they
are local minima or local maxima now if
the problem is such a simple problem
then why do we need any algorithm to
solve the problem so here is a simple
example minimize X - 2 square and F dash
X equal to 0 implies X star equal to 2
so 2 is a stationary point and at that
stationary point you will see that the F
2 - 2 is greater than 0 which implies
that X star is a strict local minimum so
as I said that if it is such a
easy thing to solve - to solve Lepidus X
equal to zero and identify stationary
points then where is the need of an
algorithm so here is an example so let
us consider the example to minimize f of
X equal to X square plus C to the power
X where f is a function from R to R now
the derivative of the function which
will denote in this course when using
the function G of X that turns out to be
2 X plus e to the power X and if we
equate it to 0 we really cannot find a
solution of this problem in a
straightforward way like what we did
here so we need some algorithm to find
out X which satisfies 2x plus e to the
power x equal to 0 and that sir we'll
need a numerical procedure or algorithm
to solve to find a stationary point of
these kinds of functions so in general
it is difficult to find the stationary
points using a simple way like this and
one has to go for some algorithm to
solve this now there exist different
kinds of algorithms to solve this
problem so some algorithms they do use
the derivative information some
algorithms do not use the derivative
information so but assume certain form
of the function called unimodal function
so we will see those things in the next
class so in the next class we look at
some algorithms to solve the problem of
the type f dash x equal to 0 or finding
the minimum of the function f of X
without resorting to any derivative
information so those are called the
derivative free methods and the methods
which use derivatives they are
derivative based methods so we'll see
some of them to solve the problems of
the type G of X equal to zero or the are
the problems where the the derivative of
the function vanishes or the function as
the minimum so we'll stop here and
continue in the next class
thank you
you