Re: [Dclib-devel] Root-finding algorithm in DLib

[Davis K. <dav...@us...>]

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
>