Re: DirectedInf
Arnold Neumaier wrote:
Nate Hayes wrote:
As controversial as it may be, more and more I believe Motion 3 is
too liberal in allowing unbounded intervals. Overflow makes things
more
efficient because P1788 then no longer has to deal with special case
disctinctions between when the result is known to overflow and be
unbounded vs. when the result is known to overflow and be bounded.
How would you then represent the interval defined by the bound
constraint x>=1 in a linear program?
Nothing overflowed, x can be any real number >=1.
If it is a constraint, then as I mentioned just last night
1 <= X
will always be true for non-empty X with the lower bound
greater-or-equal to 1. THis is all that's needed to program the
constraint.
No.
Your suggestion amounts to giving up using intervals on this problem.
How do you use your recipe and standard interval operations
to deduce from
1<=x, y=x^2-1
that y>=0?
Using the intervals from Motion 3, one simply writes
x in [1,Inf], hence y in [1,Inf]^2-1=[1,Inf]-1=[0,Inf],
and reads off from the result that Y.=0. This is how constraint
propagation works in _every_ decent presolve code for optimization.
Or one can write:
x in [1,Overflow], hence y in [1,Overflow]^2-1=[0,Overflow]
But nothing overflowed.
Yes it did: the domain of x is larger than can be represented by the working
precision of the hardware.
And you don't treat Overflow as a real number, since
Overflow^-1 = Overflow
would imply that Overflow=GoldenSectionRatio.
So you are just using Overflow as Infinity,
and pretend you do something different.
Why then not use DirectedInf which doesn't show these artifacts?
I've always said, e.g., what [1,Overflow] means to me is:
{ x | 1 <= x <= u }
where MAXREAL < u is some unknown real number.
You've already stated in past e-mails this means [1,Overflow] is a family of
compact intervals. The element of this family with the largest upper bound
is unknown. This makes the same distinction between the decorated interval
([1,Infinity],IsBounded).
This is why in your own logic and reasoning
([1,Infinity],IsBounded) \subseteq ([1,Infinity],IsBounded)
should be "false," since each decorated interval represents a family of
possibilities: it is known in this case that the upper bound of each
interval is actually some finite number.... we just don't know _what_
number.
Inside a physical computer, not much interesting can be said about real
numbers greater than MAXREAL, anyways.
In the far past, people often BigM methods in optimization, using
x in [1,M] for x>=1, fwith a huge value of M, ollowing your argument.
This proved to be ok in simple cases but unreliable and numerically
unstable in general, and is now generally considered bad design.
If a problem truly requires knowing a distinction between [0,Overflow]
and [0,Infinity] as a result, probably it needs to be scaled or
transformed by some affine transformation so as to better utilize the
available precision of the hardware.
What about
x>=1, y=log(x) -1
in place of the above example?
x in [1,Overflow], hence y in log([1,Overflow])-1
=[0,Overflow]-1
=[-1,Overflow]
If your argument were correct, you could argue that y cannot be much
bigger than 710. But depending on the application, it might be that y
the parameter of real interest, and x is only an auxiliary quantity
that happens to be needed, and hence can be astronomically large.
But it cannot be done if all intervals are required to be bounded.
Instead, one has to use logical arguments and formalize them to
achieve the same effect.
Bound constrains are represented in global optimization codes by
interval enclosures, to be able to apply a multitude of interval
techniques to them.
Without having unbounded intervals, one can no longer do that,
but needs to account in the code separately for variables without
bounds, variables with a lower bound only, variables with an upper
bound only, and bounded variables.
It seems to me the differences between Overflow and Infinity in this case
are entirely theoretical, not practical. For example, it would be better
for the user to solve the problem with a Computer Algebra System than
with some numerical computing algorithm.
This pushes constraint satisfaction problems and global optimization
problems into the symbolic world rather than to the interval world,
just because some variables are unbounded.
In this way, interval methods would lose much of their applicability,
just because your preference for Overflow in place of Infinity.
Fortunately, the global optimization community values unbounded intervals
too much to go that way. Just as they now have to modify existing interval
implementations to suit their needs, they'd have
to implement their own workaround around a bounded interval arithmetic
to make it handle unbounded intervals, at the cost of efficiency.
Thus the burden that should be taken away from the application area
where interval arithmetic is most widely used and the only area where
it is accepted as main stream would be back on them.
If this would become a standard, it would be worse than having no
standard, since it cements the situation for a long time to come.
I don't see any of this is true.
In a nutshell, Overflow gives the same results as Infinity in all the
interval arithmetic operations. So nothing is lost, and it is mostly about
semantics: with Overflow we admit we are dealing with large but finite
unknown numbers that cannot otherwise be handled in the working precision of
the hardware. So at theoretical level there is really little difference from
Infinity, and the results are mostly the same. Some of the interval
relations are slightly different, but that is really the only difference.
The reason to adopt these semantics are practical: it does not require
re-defining the exisitng IEEE 754 definitions or notions of infinity, and as
it has been mentioned already adding overflow would make IEEE 754 a better
standard, anyways. So this will give non-interval people motivation and
incentive to put this into hardware, as well.
In any case, I'm GLAD to hear you are up to the task of putting together a
proposal for DirectedInf. I encourage you to do this, and I will be pleased
to study it on its merits. It will also be nice, because then P1788 will
actually be able to do a scientific study/comparison between Overflow and
DirectedInf. This will be a good thing.
I do have my doubts about DirectedInf, but I don't have any preconcieved
notion regarding Overflow, either (its just that right now from my vantage
point it appears to be the best solution). Bottom line for me is I'm looking
for the design that accomplishes three things:
-- facilitates the fastest and most efficient hardware and software
implementations we can think of
-- is mathematically correct
-- provides incentive to vendors like Intel, AMD, etc. to adopt the
conventions in future hardware designs, even if this only represents
incremental hardware changes that are shy of a full-blown interval procssor
Nate Hayes