Re: fzero initial bracketing [WAS: bug #31070]

[Jaroslav Hajek]

On Tue, Sep 21, 2010 at 2:51 PM, c. <address@hidden> wrote:
>
> On 21 Sep 2010, at 13:58, Jaroslav Hajek wrote:
>
>> Yes, but what attempts? My example algorithm will find the bracketing
>> almost always (despite the finite precision), and a simple
>> modification can make it always find the bracketing if it exists. It
>> may be impractical nevertheless.
>
> whether the algorithm is 'practical' or not depends on how far you push it,
> what I am trying to propose is something extremely simple which would still
> have some probability to succeed.

That is exactly what the current implementation is about.
Yet, you are unhappy with it on the basis that it is too simple and
has too low probability to succeed. I am merely saying that simply
using a different, longer sequence may satisfy you now but you can
still easily find another failing example later. Using a too long
sequence can, on the contrary, be inconvenient to some users. For
instance, when accidentally trying to solve an equation that has no
solution, I'd prefer the algorithm to try a few dozen values and error
out, rather than keep trying for half an hour until I break it, having
no idea what went wrong. That's why I would recommend my "sure fire"
approach neither.

> I assume the user is giving his interpretation of the concepts 'far' and
> 'very close'
> by specifying the algorithm options and I would like to use those to avoid
> looking
> for the bracketing too close or too far away from the initial guess.
>

Er, no, I disagree. I'm almost 100% convinced that an user who can
give options to fzero will be also well aware of the bracketing issues
discussed here, and is most likely able to supply a bracket himself.

> Maybe the approaches I have been suggesting do not do this very well, but if
> you are not opposed to the idea of
> improving fzero's heuristics alltogether I might keep trying.
>
>> I think a much better (and truly practical) algorithm would not just
>> try a number of trial steps, but make use of the function value
>> information gathered in the process to attempt to construct "smart"
>> trials.
>
> that makes sense, but I'd say the resulting function would be a completely
> different algorithm than the current fzero.
> c.

Yes, that is exactly my point. Given that this is all about making
fzero smarter, why not actually aim for a smarter approach?
For instance, something like this:

1. try a double newton step using a crude FD approximation.
2. if it steps away from zero, try several steps in opposite
direction, then error.
2. otherwise, try again logarithmically (for exp-like functions).
3. if these three points are monotonic, try several even larger steps.
4. otherwise, call fminbnd to attempt to find a minimum/maximum with
the opposite sign.

what do you think?

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz