Re: [Dclib-devel] Root-finding algorithm in DLib
Brought to you by:
davisking
Menu
▾
▴
Re: [Dclib-devel] Root-finding algorithm in DLib
|
From: Davis K. <dav...@us...> - 2014-05-31 17:44:35
|
No problem :)
f^2 should be faster since it is a closer match to the polynomial
interpolation used to take the steps. That is, I would expect it to
require fewer iterations to solve when using f^2.
Also, it should be noted that the method can also get stuck in a local
minima which doesn't correspond to any root. For example, if f(x) has
a local minimum somewhere and the output of f(x) at the location is >
0 then f(x)^2 will also have a minimum in the same place. But that
spot isn't a root of f(x). So find_min_single_variable() might return
one of these points as a solution which isn't what you want. To avoid
this you would need to make sure the initial search point is not too
far from a root.
Here is a little example:
auto f = [](double x) {
return 3*x*x*x - 8*x*x + x - 10;
};
auto g = [&](double x) {
double val = f(x);
cout << ".";
return val*val;
};
double x = 10;
find_min_single_variable(g, x);
cout << x << endl;
cout << f(x) << endl;
It works with x = 10. But if you try x = -10 as the starting point it
finds a minimizer of f() that isn't a root. You can also see the
number of times g() is called, which in this case is 19 times.
Cheers,
Davis
On Sat, May 31, 2014 at 1:30 PM, Zhoulai <ze...@gm...> wrote:
> Thank you very much for your quick reply !
>
> What do think about the efficiency between minimizing f^2 and |f| with
> find_min_single_variable?
>
> My guess is: since find_min_single_variable is based on bracket approaches,
> to compute |f| at each step is less complex than computing fˆ2, and thus to
> minimize |f| is more efficient than to minimize fˆ2, am I correct?
>
> Thanks for your ideas.
>
> Zhoulai
>
>
> On Sat, May 31, 2014 at 10:23 AM, Davis King
> <dav...@us...> wrote:
>>
>> I don't have any detailed description of find_min_single_variable()
>> other than
>> http://dlib.net/dlib/optimization/optimization_line_search_abstract.h.html#find_min_single_variable.
>> But if it can't find a bracket or a good enough solution in under
>> max_iter function evaluations then it throws an exception. Beyond
>> that, I would just look at the code. It's got comments telling you
>> what it does at each step and on the whole it's one of the simpler
>> optimization algorithms. But basically, it's just interpolation
>> except when the interpolation output is not useful and then it will do
>> a bisection step.
>>
>> Cheers,
>> Davis
>>
>> On Sat, May 31, 2014 at 1:13 PM, Zhoulai <ze...@gm...> wrote:
>> > Thank you for your very quick reply. I wonder the efficiency between
>> > minimizing f^2 and |f| in my problem?
>> >
>> > Otherwise, do you have documentation about your implementation
>> > details? Of
>> > course, the source code is the best document but I am also looking for a
>> > (maybe not that formal) mathematical description of what you have
>> > implemented in some provided functions. For example, how can I know
>> > which
>> > your find_min_single_variable has implemented, bisection, false
>> > position, or
>> > Brent etc? What is the expected behavior if the implementation fails to
>> > find
>> > endpoints with opposite signs?
>> >
>> > Thank you for your ideas.
>> >
>> > Zhoulai
>> >
>> >
>> > On Sat, May 31, 2014 at 10:04 AM, Davis King
>> > <dav...@us...> wrote:
>> >>
>> >> Well, to describe find_min_single_variable() in terms of what is
>> >> described on wikipedia
>> >> (http://en.wikipedia.org/wiki/Root-finding_algorithm),
>> >> find_min_single_variable() first finds a bracket containing the
>> >> minimizer and then uses interpolation to shrink the bracket to the
>> >> solution. So it's pretty representative of general purpose root
>> >> finding methods that don't require the user to supply a derivative.
>> >> So it sounds like a reasonable thing to use for your problem. In your
>> >> case, you just have to ask it to minimize f(r)^2 so that the root is
>> >> the minimum and it should work fine.
>> >>
>> >> Cheers,
>> >> Davis
>> >>
>> >> On Sat, May 31, 2014 at 12:48 PM, Zhoulai <ze...@gm...> wrote:
>> >> > Hello,
>> >> >
>> >> > I am new to Dlib, but I am surprised that there is no root-finding
>> >> > procedures in Dlib. Although the functionality provided by the
>> >> > optmization.h should also be able to solve root-finding problems, I
>> >> > guess
>> >> > that comes with a higher complexity?
>> >> >
>> >> > So what if I want to solve a problem as follows using Dlib?
>> >> >
>> >> > I have a one dimensional function 'f' which is not necessarily
>> >> > differentiable. I want to find a root 'r' that is closest to an
>> >> > initial
>> >> > guess 'g' so that f(r)=0 ?
>> >> >
>> >> > More formally, I am looking for a low-cost way to minimize |r-g|
>> >> > under the constraint f(r)=0;
>> >> >
>> >> > In my problem setting, it is likely the initial guess is the root,
>> >> > thus
>> >> > I
>> >> > would use 'g' as an initial guess. However, I do not have an interval
>> >> > [a,b]
>> >> > such that f(a).f(b)<0 which is a common request for most root-finding
>> >> > procedures.
>> >> >
>> >> > Of course the problem above can be handled by the optimization
>> >> > approaches
>> >> > like find_min_single_variable etc, but my guess is that it can also
>> >> > treated
>> >> > as a root-finding problem which is less expensive. What do you
>> >> > think?
>> >> >
>> >> > Thank you for your ideas.
>> >> >
>> >> > Sncerely,
>> >> > Zhoulai
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >
>> >> >
>> >> > ------------------------------------------------------------------------------
>> >> > Time is money. Stop wasting it! Get your web API in 5 minutes.
>> >> > www.restlet.com/download
>> >> > http://p.sf.net/sfu/restlet
>> >> > _______________________________________________
>> >> > Dclib-devel mailing list
>> >> > Dcl...@li...
>> >> > https://lists.sourceforge.net/lists/listinfo/dclib-devel
>> >> >
>> >>
>> >>
>> >>
>> >> ------------------------------------------------------------------------------
>> >> Time is money. Stop wasting it! Get your web API in 5 minutes.
>> >> www.restlet.com/download
>> >> http://p.sf.net/sfu/restlet
>> >> _______________________________________________
>> >> Dclib-devel mailing list
>> >> Dcl...@li...
>> >> https://lists.sourceforge.net/lists/listinfo/dclib-devel
>> >
>> >
>> >
>> >
>> > ------------------------------------------------------------------------------
>> > Time is money. Stop wasting it! Get your web API in 5 minutes.
>> > www.restlet.com/download
>> > http://p.sf.net/sfu/restlet
>> > _______________________________________________
>> > Dclib-devel mailing list
>> > Dcl...@li...
>> > https://lists.sourceforge.net/lists/listinfo/dclib-devel
>> >
>>
>>
>> ------------------------------------------------------------------------------
>> Time is money. Stop wasting it! Get your web API in 5 minutes.
>> www.restlet.com/download
>> http://p.sf.net/sfu/restlet
>> _______________________________________________
>> Dclib-devel mailing list
>> Dcl...@li...
>> https://lists.sourceforge.net/lists/listinfo/dclib-devel
>
>
>
> ------------------------------------------------------------------------------
> Time is money. Stop wasting it! Get your web API in 5 minutes.
> www.restlet.com/download
> http://p.sf.net/sfu/restlet
> _______________________________________________
> Dclib-devel mailing list
> Dcl...@li...
> https://lists.sourceforge.net/lists/listinfo/dclib-devel
>
|
