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

Re: DirectedInf

Nate Hayes wrote:

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.
No. The upper bound of each member of the family is known, namely it is u. But it is not known which member of the family is intended, and no 
largest element of the family exists.

You are just replacing an elegant mathematical concept by
introducing a special case of set intervals, just to work around
a minor inconvenience.
This makes the same distinction between the decorated interval ([1,Infinity],IsBounded). 

But we have this already, and we need also ([1,Infinity],IsUnbounded).

Indeed, the range if x _is_ unbounded, and we know that.



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. 

I revised my stand on this, and now follow the argument of Dan Zuras
that that in comparisons, the decorations should be ignored.
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 nothing is gained, the concept is superfluous, as you just argue.
and it is mostly about semantics: 

The semantics of Inf is clear and simpler.
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.
Motion 3 already admits the same. aAn interval standfs for an unknown number in the given range. No overflow is needed to express this semantics. The standard mathematical semantixcs did it all the time.
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.
Since nothing has been agreed on that so far, one can erase these differences, without consequences for the applications.
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 

I aim at the same, and more:
-- to keep the conceptual basis clean, close to the mathematics used to create verification tools, and to minimize possible confusion. 


Arnold Neumaier