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

[Zhoulai <ze...@gm...>]

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
>