hello internet this is oscar veliz for this video we're looking at brent's method for minimizing
functions not to be confused with the brent-dekker method which is also called brent's method
i'll be going over the algorithm trying to visualize as much as i can and providing
some discussion this video will assume that you're familiar with golden section search as
well as successive parabolic interpolation check out my videos if you haven't already
i would also recommend checking out my video on brent's method i mean the other brent's method
let's turn back again to "algorithms for minimization without derivatives"
in it brent writes quote in this section we describe an algorithm
which combines golden section search and successive parabolic interpolation
brent shows these two methods because golden section search is guaranteed to
find a minimum and pretty efficiently even though it only has a linear order
meanwhile successive parabolic interpolation isn't guaranteed to converge but when it does
it will do so quickly with an order of 1.325 by combining them we get the best of both worlds
brent provides this table so sort of demonstrating how analogous this
new algorithm is to the previous one on finding roots if there's anything i would
add would be to also mention inverse quadratic interpolation as part of the zero finding method
let's look back at our earlier example from x cubed over three minus x squared
over two minus x minus one if we were to solve this using
successive parabolic interpolation we would need three starting points
and then compute the parabola that interpolates those three points keep
in mind though that the order of the points doesn't really matter such as x1 x2 and x0
we then use these values to come up with our next point x3
what if we instead renamed these variables to be v x and w
we'll need to define a few rules that say x is our least value of f w was our second lowest value of
f and v breaks the mold being the previous value of w but it is usually the next lowest
we then interpolate to find another parabola to give us our next point x4 this will also rename
we'll call that value u which was the last evaluated point of our function
we'll need a few more variables first a which is our left bound
and b which is our right using those we can come up with the midpoint
m essentially brent's method uses these important variables when making its decisions
our algorithm for brent's minimization looks like this from our start
given a unimodal function f has an interval a b we initialize our values for v
w and x from this function leaving u undefined then check if b minus a is less than our epsilon
when it is that's our minimum we return a plus b over two and stop otherwise we check to see if
SPI would behave when it is we'll then apply successive parabolic interpolation otherwise
we use golden section search and then regardless update our variables finally restart the process
if we look at our equation from jarratt's method we can rewrite it to be our value for u is x plus
p over q jarratt's method would behave poorly whenever q is equal to zero because we'd end
up dividing by zero this happens whenever any of these three points are the same also
if our value for u would go outside of our bounds for a and b we wouldn't want to use jarratt's
method brent adds another step which is to do this condition check keeping track of our step sizes
especially for the second to last step just to make sure we're taking good enough steps
there's also another check for tolerance which i'm not going to get into whenever it does
behave badly just switch to golden section search computing a new u using this equation
brent again then f is evaluated at the new point u the points a b v w and x are updated as necessary
and the cycle is repeated brent doesn't give a lot of detail as to how to update these variables
referring instead to the code that he provides to give the actual description essentially it's a lot
of bookkeeping and accounting so i don't blame brent for not providing a more user-friendly
explanation before diving into visualization of brent's method i do want to point out for
golden section search our values for c and d would be evaluated here note their locations
with brent's method we're given the starting interval a and b
and we use this equation to initialize our values for v w and x you can also rewrite it like this
anyways they would all show up here we would then use their values for v w and x to try to
do successive parabolic interpolation which would fail because all these points are the
same therefore we would switch to golden section search and compute u right there
and update our variables notice again that v and x are still the same point so if we try to do SPI it
would fail again this means we have to use golden section search to come up with our new value for u
and then repeat the process
this time we have unique values for x w and v which will allow us to use
parabolic interpolation to come up with our new value for u right there
we would then update all of our variables and parabolic
and interpolation would work again in this case
let's again use the same numerical example that i've used in my other videos in minimization
in this case it only took six iterations for brent's minimization method to find our solution
notice that the first two iterations are golden section search
if we compare that against all of our other search techniques brent's method is by far the best
keep in mind it also found are a minimum in the first iteration
but it doesn't know that until the shrinks the interval is small enough
brent comments usually the algorithm stops doing golden section steps and
eventually does only parabolic interpolation steps
as we saw in our previous example let's change gears now and look at matlab
here is the documentation for the function fminbnd
an algorithm based on golden section search and parabolic interpolation
does that sound familiar even cites forsythe moler and brent huh yes it is brent's method
if you look at an example plugging in our solution from earlier you can see it doing this initial
step then a golden section search followed by parabolic interpolation until it terminates
if you've seen all the videos in this minimization series you'll recall this slide from ternary
search that says you can use the derivative at f equal to zero to find our minimum it would not
be guaranteed to converge though you could instead apply brent-dekker on that function
or newton-bisection hybrid it does require you now to take an extra derivative but
you could always swap out steffensen's method if you wanted to go this route
this is using brent's method on the root finding approach to solve for a minimum
let's look at one final quote from brent where he writes
convergence in a reasonable number of steps is guaranteed for any function
and on well behaved functions convergence is super linear with an order at least 1.325
importantly brent's method is guaranteed to find your minimum assuming you have a valid interval
it's analogous to the brent-dekker method for finding roots combining
golden section search with successive parabolic interpolation also known as jarratt's method
recall that the first two iterations are always golden section search usually switching off
to interpolation the method converges superlinearly with an order of 1.325
and you can also apply the brent-dekker method to f prime assuming you can find the derivative
matlab's fminbnd and scipy's.optimize.minimize_scalar also use
brent's method the example code that i wrote will be found on github as always thank you very much
for watching this will probably be the last video on minimization in this series but let me know if
you want to keep covering similar topics i know i skipped over some details but a lot of that was
just variable housekeeping definitely check out my code if you want to see how that actually works