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

[Jaroslav Hajek]

On Tue, Sep 21, 2010 at 4:14 PM, c. <address@hidden> wrote:
>
> On 21 Sep 2010, at 15:17, Jaroslav Hajek wrote:
>
>>
>> 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.
>
> What I don't like in the current approach is that the sequence
> of trial values is completely arbitrary and is hardcoded in the function,
> which makes it quite hard guess a-priori for what class of problems it will
> fail.
> I'd prefer something where the number of attempts and the distance between
> successive
> steps is somehow dependent on the specific problem being considered.
>

Precisely - that's what I called a "smarter" approach.

> [...]
>
>> 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.
>
> well, the use case I have in mind is, as I said before, someone who
> has some code that runs in Matlab but fails in Octave.
> Here the person who has set the options for fzero and the one using it
> are not the same, the first one would probably be able to fix the problem
> by providing a correct bracket, while the latter would most likely just
> complain about Octave not being compatible...
>

That won't get you anywhere, I think, because the options imported
from Matlab still won't make it work, unless we copy Matlab's approach
(which we don't want to). Incidentally, do you have a reason to thing
that Matlab uses a trial sequence based on tolx or other options?



>>> 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?
>
> what about fitting the evaluated function values whith a simple function
> for which an inequality constraint can be easily solved and use that as a
> guess?
>

If you can make it specific, why not. We can even try multiple
approaches and compare them on a number of testcases.


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