Re: Branch & bound for not everywhere defiend constraints
> Date: Sun, 6 Sep 2009 18:33:49 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
>
> Nate Hayes wrote:
> > Arnold Neumaier wrote:
> >> Nate Hayes schrieb:
> >>> . . .
> >>>
> >>> There remains a circle at radius 3 where some unnecessary effort
> >>> still remains.
> >>
> >> . . .
> >
>
> I should also clarify:
>
> In the original Paving B example, the user is concerned about f(x) > 0
> or any f(x) that is not real. In either case, something catastrophic may
> happen. In this Paving C example, the center circle (and its entire area)
> represent f(x) not real. If this information is valuable to the user, as
> in Paving B, then the circle in Paving C represents zero wasted effort
> and is actually an optimal covering.
Nate,
3 minor points here. More in the way of questions than
criticisms.
Why is it that Paving C has the center circle grey (a color
you have been using for f(x) > 0)? Shouldn't it be blue (in
the NaI case) or yellow (in the empty case)? And, while the
yellow case would tile as you have it & not waste any effort,
how is the branch & bound written so as to prevent the blue
case from continuing to bisect down to your epsilon limit as
happened in your Paving B?
>
> Also, Alexandre's original fixed-point example (attached for convenience)
> can be reformulated into a branch-and-bound problem; the existence (or
> non-existence) of a fixed point f(x) =3D x for function f can be reduced
> to finding the zeros of
>
> g(x) =3D f(x) - x =3D 0.
>
> In this case, the problem can be solved entirely without decorated
> intervals, i.e., ExpressionResult, or global/local flags, provided NaI is
> used instead.
>
> For example, the branch-and-bound algorithm
>
> if ( g(x) > 0 ) delete x
> else if ( g(x) < 0 ) delete x
> else if ( wid(x) <=3D eps ) accept x if not isNaN(g(x))
> else bisect x
Next, I'm not sure I read the 3rd line of this correctly.
Do you mean to say:
else if (( width(x) <= eps ) and not isNaN(g(x))) accept x
If so, does the NaI case continue to bisect along with the
uncertain interval boundary or is there another test that
prevents that?
>
> Over the input domain [-5,5], this algorithm correctly proves the
> non-existence of a fixed point for f(x) =3D sqrt(x-1); it also proves the
> existence of a fixed point within the interval [1.61803,1.61804] for f(x)
> =3D sqrt(x+1).
>
> As a side benefit, note the "syntactic sugar." In these examples, g(x)
> will never be empty. So subtle and innocent programming errors due to
> empty set, such as fogetting g(x) > 0 is true if g(x) is empty, won't occur.
>
> Nate Hayes
>
Finally, what does it mean to "forget g(x) > 0 is true
if g(x) is empty"? And how CAN g(x) > 0 be true when
g(x) is empty? Is this another example of your 'vacuous
truth'? If so, what is the 'subtle & innocent programming
error' committed in this case?
Just curious...
Dan