Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Motion 31 draft text V04.4, extra notes

Baker Kearfott wrote:

On 04/08/2012 10:49 AM, Nate Hayes wrote:

John Pryce wrote:

On 6 Apr 2012, at 17:13, Nate Hayes wrote:

But I believe we also want to support intervals as ranges, e.g. for
constraint propagation. In that case it is essential to provide for
unbounded intervals at Level 1.


Folks, I apologize in advance for being pedantic but someone needs to
explain this to me:

Why is it "essential"?

Specifically: what is a concrete example of a computer algorithm that
can
produce more meaningful results with unbounded Level 1 intervals as
opposed
to "overflown" intervals at Level 2?


Speaking as a user, rather than as chair:
How would you represent, say, in an optimization code,
a decision variable that had a lower bound constraint
but no upper bound constraint, visa versa, or a free
interval?  For example, in input conventions for LP solvers,
something akin to infinity is used.  In older solvers,
these absent bounds are sometimes replaced by something
like 10^{12}, which can lead to scaling problems and
other problems.

Such intervals are not the result of an operation.

In constraint propagation, such free variables or semi-free
variables can be initialized to something like [a,\alpha], where
\alpha is either thought to be MAXREAL or \infty, intervals that
are subsequently processed either with arithmetic or by intersection.
Using MAXREAL rather than \infty can lead to the arithmetic
"lying," although merrily computing while unaware of the presence
of \infty can also lead to problems.


Hi Baker,

I've managed to dig up out of the archives an old e-mail from Ian McIntosh
(attached) which I still think is a rather helpful summary of Overflow vs.
Infinity. In that e-mail, a distinction is made between mathematical
infinity (+Inf) and overflow (+OVR), where +OVR represents some unknown
finite value greater than the largest Level 2 number. Ian's definition is a
bit informal and framed within the context of floating-point arithmetic
rather than interval arithmetic, but I think it still represents a good
starting point for intuition.

As he points out, the rules for floating-point arithmetic with +OVR are
almost identical to the IEEE 754 rules for +Inf. For example:
   (+OVR) - (+OVR) = NaN        and        (+OVR) / (+OVR) = NaN
but one important difference is:
   (+OVR) * 0 = 0
as opposed to:
   (+Inf) * 0 = NaN

In my mind, a similarly informal definition of an "overflown" interval is a
Level 2 interval with +OVR at one or both endpoints. For example, at Level 2
the interval [0,+OVR] represents the input domain
   x >= 0
to any practical extent a computer in the real world can prove anything
meaningful about the domain of a function within the numerical limits of the
underlying system, even though [0,+OVR] is not truly unbounded.

A branch-and-bound algorithm in the current P1788 model would split the
unbounded interval domain [0,+Inf] and eventually obtain the interval
[REALMAX,+Inf]. In the new model, the same algorithm would split the Level 2
interval domain [0,+OVR] and eventually obtain the interval [REALMAX,+OVR].
Now how in the world does the input interval [REALMAX,+Inf] allow a
numerical algorithm of any sorts to prove something more useful about the
domain of our function for x > REALMAX than if instead the same algorithm
is given [REALMAX,+OVR] as input? It seems to me there is none.







In my view, unbounded intervals are an overly-complicated and unnecessary
aspect of the Level 1 model, and I see this complication trickles down to
Level 2 and below into the implementations. I believe Motion 3 was the
right
thing to do at the time, but over the years of listening to P1788
discussions I've come to the conclusion the standard Level 1 model should
be
restricted to bounded intervals, with the notion of "overflown" intervals
then introduced at Level 2.




Please clarify the difference between an unbounded interval produced as
the result of an overflow and an unbounded interval that contains
infinity,
other than that the first is the result of an operation and the second
is a datum with the same status as other data values, that can be
present before computations begin.


With "overflown" intervals at Level 2 I don't believe such a distinction is
needed anymore. This is one of the nice simplifying aspects.

For example, I see the more formal definition of the "overflown" interval
[0,+OVR] as a family of intervals. One can think of the number of intervals
in the family as being infinite, but each member of the family is a closed
and bounded (compact) interval. This means unbounded intervals are not
required at Level 1 in order for "overflown" intervals to exist at Level 2.
As illustrated earlier, [0,+OVR] is suitable input, under this
intepretation, for a branch-and-bound or global optimization algorithm, say.
It is also suitable as the result for arithmetic operations. For example, in
the current P1788 model
   1/[0,2] = [1/2,+Inf]
whereas in the new model
   1/[0,2] = [1/2,+OVR].

From a practical perspective: for any and all inverval arithmetic operations
and applications, if you simply replace +Inf from the current P1788 model
with +OVR, then the interval arithmetic formulas in Motion 5 are still
completely accurate and unchanged. The main difference is in the formality
of the underlying mathematical definitions about how such results are
obtained. In the new model, all Level 1 intervals are closed and bounded
(compact). IMO this leads to a cleaner, simpler Level 1 model with stronger
algebraic properties than the current P1788 model; and I don't see in terms
of actual meaning and practical functionality that anything is lost by
removing unbounded intervals from the Level 1 model in this way.

Nate







This is all separate from the issue of whether 1788 should give a way to
*distinguish* a genuinely unbounded interval from an "overflowed" one
that
is known to be bounded but has a bound outside the representable range.


I think P1788 just needs to pick one or the other: ubounded or "overlown"
intervals. I see absolutely no reason for both, since I have been asking
the
question for years "what is an example of any algorithm that requires
both"
and no one has ever answered that question, either!!




I agree with that.  (Although the prominent among us have discussed both
kinds of intervals, it is still somewhat unclear to me why the
distinction need be made.  Perhaps we can revisit this issue, and maybe
put forward some additional defining motions.)



Nate




--

---------------------------------------------------------------
Ralph Baker Kearfott,   rbk@xxxxxxxxxxxxx   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------
--- Begin Message ---

NH> Keep in mind, Ian McKintosh has suggested replacing unbounded closed
NH> intervals with "overflown" compact intervals. In practice, there is not
NH> really a difference between the two. For example, +INF and -INF are
NH> replaced by +OVR and -OVR in all compuations, where OVR is some unknown
NH> finite real number larger than the magnitude of the largest
NH> floating-point number. In this way, intervals such as [1,+OVR] remain
NH> compact intervals and are not unbounded like the interval [1,+INF].
NH> Arithmetic operations on the endpoints of compact overflown intervals is
NH> the same as in Motion 5, i.e., (-OVR) + (-OVR) = -OVR, 0 * OVR = 0, etc.

AN> But then OVR has a different meaning in different places, which is
AN> unacceptable from a mathematical point of view. It is just INF in
AN> duisguise, and it hides mathematical propoerties of the limit under
AN> the carpet. One cannot use it in a mathematical argument....
AN>
AN> To argue for existence, one _needs_ in certain case the unbounded case.
AN> Mathematical programming had once a tradition for using big M (which is
AN> about the same as your OVR), and it is now deprecated (though still used
AN> by a few who don't like unbounded variables) since it behaves poorly not
AN> only mathematically but also algorithmically.

I did suggest Overflow (OVR) as a better floating point value than Infinity to represent an overflowed value, and that it would be very often more useful as an interval endpoint.

In doing that I did not mean it to totally replace Infinity, and I did not mean they would have the same semantics. The whole point is to distinguish their semantics.

In IEEE floating point, you can get Infinity two ways. One is by dividing a nonzero by zero. The other is by overflow. The following mostly ignores signs for brevity:
IEEE nonzero / 0 = Infinity
IEEE overflow on any operation = Infinity

One problem with that is that you don't know whether you're dealing with an infinite value or with an overflowed value. You need to know to get the semantics of subsequent operations correct.
IEEE Infinity * 0 = NaNQ

NaNQ is the right answer for Infinity resulting from nonzero/0, but should be 0 if the Infinity was the result of an overflow instead. Clearly the two meanings of Infinity need to be distinguished.

Proposed nonzero / 0 = Infinity
Proposed overflow on any operation = Overflow

Proposed Infinity * 0 = NaNQ
Proposed Overflow * 0 = 0
Most of the other rules are straightforward. One mustn't be tempted to think that subtracting Overflow from itself gives 0 though. In floating point
Proposed Infinity - Infinity = NaNQ
Proposed Overflow - Overflow = NaNQ
while in Interval Arithmetic
Proposed (+Infinity, +Infinity) - (+Infinity, +Infinity) = (-Infinity, +Infinity) (assuming Real* to allow Infinity - if not then ignore this line)
Proposed (+Overflow, +Overflow) - (+Overflow, +Overflow) = (-Overflow, +Overflow)
and multiplying that by 0 gives
Proposed (-Overflow, +Overflow) * (0, 0) = (0, 0)

If Interval Arithmetic was based on IEEE 754 with Overflow added, some of the operations would be simplified because they would not have to handle special cases.

I think that IEEE and others before them, including CDC and Cray, erred in combining two concepts that must be kept separate for correctness. (Note the operations creating them do have separate exceptions.) Simplicity is essential, but oversimplification is trouble.

With this clarification that Overflow is not Infinity, and our agreement that Infinity (which I think you mean by the unbounded case) is also needed, do we actually disagree? Overflow simply means a finite value that's larger than the largest representable in the chosen precision, while Infinity means the mathematical infinity. They are both infinite sets. They are disjoint sets. In some contexts you could treat them the same way, in others you can benefit by distinguishing them. Maybe most importantly, adding Overflow to floating point not only improves floating point, it lets it be a better more meaningful representation for interval end points.

- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development


Inactive hide details for Arnold Neumaier ---09/19/2010 02:47:40 PM---Nate Hayes wrote: > Arnold Neumaier wrote:Arnold Neumaier ---09/19/2010 02:47:40 PM---Nate Hayes wrote: > Arnold Neumaier wrote:


From:
Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>

To:
Ian McIntosh/Toronto/IBM@IBMCA

Date:
09/19/2010 02:47 PM

Subject:
Re: Motion P1788/M0013.04 - Comparisons




Nate Hayes wrote:
> Arnold Neumaier wrote:
>> Nate Hayes wrote:
>>> John Pryce wrote:
>>>> On 18 Sep 2010, at 23:15, Nate Hayes wrote:
>>>>> I speak against this.
>>>>> Ulrich's interior is better.
>>>>>
>>>>> Note that the topological interior, i.e., "proper subset," is
>>>>> already expressed efficiently in terms of Ulrich's relations for
>>>>> intervals A,B:
>>>>>   ( A \subset B ) and not ( A == B )
>>>> Doesn't that make [2,3] interior to [1,3]?
>>>>
>>>>> I don't see Entire should be interior to Entire.
>>>> Well, it seems weird to me too, but there it is. You're an expert on
>>>> quantified statements. Isn't it inescapable from the definition "B
>>>> is a neighbourhood of each a in A" (eqn1)?
>>>
>>> As you are so fond of quoting from George Corliss: if it even seems
>>> weird to you -- a seasoned mathemetician -- then "God help the casual
>>> user!"
>>>
>>>
>>>> The thing about definitions grounded in standard theory (and this
>>>> theory has been around for roughly 100 years) is that, compared with
>>>> ad-hoc definitions, you KNOW they can't lead to inconsistencies --
>>>> assuming math itself is consistent.
>>>>
>>>
>>> This is a reason I think P1788 might want to investigate sticking to
>>> compact intervals, instead.... which if you remember was one of my
>>> first choices.
>>
>> Unbounded intervals are essential for applications to general global
>> optimization and nonlinear systems solving, where for complex models
>> one often doesn't know in advance bounds on all variables.
>
> Yes, being able to initialize such unknown variables appropriately is
> important for these applications. I agree. I don't suggest P1788 should
> not provide a mechanism for this.
>
> Keep in mind, Ian McKintosh has suggested replacing unbounded closed
> intervals with "overflown" compact intervals. In practice, there is not
> really a difference between the two. For example, +INF and -INF are
> replaced by +OVR and -OVR in all compuations, where OVR is some unknown
> finite real number larger than the magnitude of the largest
> floating-point number. In this way, intervals such as [1,+OVR] remain
> compact intervals and are not unbounded like the interval [1,+INF].
> Arithmetic operations on the endpoints of compact overflown intervals is
> the same as in Motion 5, i.e., (-OVR) + (-OVR) = -OVR, 0 * OVR = 0, etc.

But then OVR has a different meaning in different places, which is
unacceptable from a mathematical point of view. It is just INF in
duisguise, and it hides mathematical propoerties of the limit under
the carpet. One cannot use it in a mathematical argument....

To argue for existence, one _needs_ in certain case the unbounded case.
Mathematical programming had once a tradition for using big M (which is
about the same as your OVR), and it is now deprecated (though still used
by a few who don't like unbounded variables) since it behaves poorly not
only mathematically but also algorithmically.


> So this approach seems to retain all the important advantages of
> unbounded intervals without actually introducing the complications that
> arise from them. To the extent I can see, it has big potential to
> simplify P1788 a great deal, without hurting or compromising the
> important needs of global optimization and nonlinear programming
> application you mention.

It is an artificial device without a proper mathematical support.

There are verygood reasons why mathematics has developed all these
topological concepts, sincve they are _exactly_ right in the circumstances.


Arnold Neumaier




--- End Message ---