Re: Branch & bound for not everywhere defiend constraints
> Date: Mon, 7 Sep 2009 12:21:31 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> Dan Zuras Intervals wrote:
> >> . . .
> >> 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)?
>
> Yes. I think to be visually accurate (and not misleading), the area of the
> circle *should* be tiled with blue color. This was part of my recent point,
> i.e., that in this case the covering produced by the NaI algorithm is 100%
> optimal with no wasted effort.
And I see you explain how just below, but...
>
> > 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?
>
> This requires two NaIs: "TotallyUndefined" and "PossiblyUndefined". For
> example, sqrt([-10,-4]) should return a "TotallyUndefined" NaI, while
> sqrt([-3,5]) should return a "PossiblyUndefined" NaI. The
> "PossiblyUndefined" NaI should also propagate over the "TotallyUndefined"
> NaI. This allows the branch-and-bound algorithm to add a check for
> isTotallyUndefined(f(x)) and therefore avoid bisecting a large blue box into
> many small epsilon-sized blue boxes.
Isn't another name for "TotallyUndefined", "Empty"?
You define it to be true in exactly the same place
as empty is true & you use it as others use empty.
Are we just a name away from agreement?
>
> . . .
>
> >> 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?
>
> Sorry, it should read
>
> else if ( wid(x) <= eps ) { accept x if not IsNaN(g(x)) }.
>
> To avoid the unnecessary bisections of blue boxes, one additional
> isTotallyUndefined(g(x)) check should be added to the branch-and-bound
> algorithm. This eliminates large blue boxes and prevents useless chopping
> into tiny epsilon-sized blue boxes.
Ah, so you are using TotallyUndefined to avoid the
unnessary & inefficient bisections that happened
before.
But, again, you are using it just as others use
Empty & for the same reasons. What's in a name?
That which we call a rose, by any other name, would
smell as... empty. :-)
>
> >
> >> . . .
> >>
> >> 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...
>
> I just refer to the original instance of your wetware example, where the
> isEmpty(f(x)) check was in the wrong place, or how using the flags semantics
> according to Vienna Proposal can lead to Paving A instead of Paving B if the
> user isn't really careful. The whole "syntactic sugar" issue may only be a
> minor part of the NaI debate. However, I think its pleasant icing on the
> cake.
>
> Nate Hayes
OK, to err is human.
But I hardly think the fallibility of my wetware compiler
constitutes compelling evidence of 'subtle & innocent
programming errors'.
We expect our computers to be better than us in this sort
of thing. Were it not so we would not need 1788. :-)
And when our computers are still unable to decide if
something is correct we expect our programmers to test
their programs. That an untested program may have errors
is neither subtle nor innocent. :-)
Finally, while I'm not happy with the concept of global
flags for any purpose, I agree that 'syntactic sugar' AKA
'decorations' attached to intervals may be of value.
As for the naming of things, it could be that sufficiently
many 'flavors' of 'syntactic sugar' could take the place
of either or both of NaIs or empty for what we need them
to do.
We are having that discussion now. Let's see how it turns
out.
Thanks for your explanations,
Dan