Jon,
That's a good question.
Short answer:
The exact algorithm in optimize() is a bit more complicated than the
bi-section, but conceptually you can think of this as a bi-section on the
first derivative of the function (the same properties hold).
Long answer:
Now the reason why optimize does not in fact require you to enter f'(x) is
because it relies on a method that is often referred to as quadratic fit.
The way this works is that it fits a quadratic function through the three
points of the objective function given by the lower interval bound a, the
midpoint m, and the upper interval bound b. The quadratic function that fits
these three points is
q(lambda) = c2 lambda^2 + c2 lambda + c3 where lambda is the vector lambda =
(a,m,b). It's like a parabola fitted through these points. Then you can
solve this for lambda_{k+1} = argmin q(lambda) and for this minimization a
closed form solution exists (like in the NR). The solution is (subject to
key stroke errors):
lambda_{k+1} = 0.5 * {(m^2-b^2)Q(a)+ {(b^2-a^2)Q(m)+
{(a^2-m^2)Q(b)}/{(m-b)Q(a)+ {(b-a)Q(m)+(a-m)Q(b)}
where Q() is the quadratic fit q() evaluated at either a, m, or b
respectively. Then you update the "outside" point (a, m, or b) and continue
with the next interval.
The properties of this are the same as in the bi-section (unimodality, the
min/max needs to be contained in the search interval) but you don't need the
analytical derivative. Convergence is about as fast as with the golden
section on f'(x).
Hope this helps. The c code for the exact implementation is here:
-----Original Message-----
From: gov2001-l-bounces at
lists.fas.harvard.edu [mailto:gov2001-l-
bounces at
lists.fas.harvard.edu] On Behalf Of Jon Bischof
Sent: Monday, February 25, 2008 7:40 AM
To: gov2001-l at
lists.fas.harvard.edu
Subject: Re: [gov2001-l] optimize() function
Yes, I know, but what I was saying is that the optimize() function
takes the *original function* and not the derivative and finds the
extrema. Finding the roots of the original function wouldn't give us
the answer. So what I wanted to know was how the optimize function
works given that we *don't* input the derivative. Does somehow
optimize() calculate the derivative itself of does it use some other
method to find the extrema?
Thanks.
Jon
2008/2/25, Jeremy Hodgen <jeremy.hodgen at kcl.ac.uk>:
the roots of the first derivative function
indicate where the
extrema of
the original function are
Jeremy
On 24 Feb 2008, at 19:07, Jon Bischof wrote:
Hey Jens,
It's not clear to me from the R help file and the lecture slides how
the optimize() command works. When we use the bisection or NR method,
we are only looking for roots using the first derivative. However,
the
optimize command somehow takes the original
function and finds its
extrema. Is there anywhere we can get more information on how this
command works so I can say something more insightful for question 2c?
Thanks,
--
Jon Bischof
Graduate Student
Department of Government
Harvard University
_______________________________________________
gov2001-l mailing list
gov2001-l at
lists.fas.harvard.edu
http://lists.fas.harvard.edu/mailman/listinfo/gov2001-l
Dr Jeremy Hodgen
Senior Lecturer in Mathematics Education
King's College London
Department of Education and Professional Studies
Franklin-Wilkins Building
Waterloo Bridge Wing
150 Stamford Street
London SE1 9NH
Tel: 020 7848 3102
Fax: 020 7848 3182
E-mail: jeremy.hodgen at kcl.ac.uk
_______________________________________________
gov2001-l mailing list
gov2001-l at
lists.fas.harvard.edu
http://lists.fas.harvard.edu/mailman/listinfo/gov2001-l
--
Jon Bischof
Graduate Student
Department of Government
Harvard University
_______________________________________________
gov2001-l mailing list
gov2001-l at
lists.fas.harvard.edu
http://lists.fas.harvard.edu/mailman/listinfo/gov2001-l