From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Apr  1 00:30:41 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g316Ueb04167
	for reliable_computing-outgoing; Mon, 1 Apr 2002 00:30:40 -0600 (CST)
Received: from mailhost.iitb.ac.in (garbo.iitb.ac.in [203.197.74.149])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with SMTP id g316UT304163
	for <reliable_computing [at] interval [dot] louisiana.edu>; Mon, 1 Apr 2002 00:30:30 -0600 (CST)
Received: (qmail 32551 invoked from network); 1 Apr 2002 06:30:17 -0000
Received: from mailscan2.iitb.ernet.in (HELO thisdomain) (144.16.108.202)
  by mailhost.iitb.ac.in with SMTP; 1 Apr 2002 06:30:17 -0000
Received: from nataraj by iitb.ac.in ; Mon, 01 Apr 2002 12:00:12 +0530
Date: Mon, 01 Apr 2002 12:00:12 +0530
X-Originating-IP: 144.16.100.71
X-Auth-User: nataraj [at] ee [dot] iitb.ernet.in
From: "P. S. V. Nataraj" <nataraj [at] ee [dot] iitb.ernet.in>
To: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>, <markst [at] nd [dot] edu>,
   <reliable_computing [at] interval [dot] louisiana.edu>
Subject: RE: Taylor models - how to get valid comparisons
Date: Mon, 1 Apr 2002 12:05:32 +0530
Message-ID: <NEBBJIKHDMLBDKBEGMNECEDHCDAA.nataraj [at] ee [dot] iitb.ernet.in>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="Windows-1252"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
In-Reply-To: <2.2.32.20020330212237.009efe18 [at] pop [dot] louisiana.edu>
Importance: Normal
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Prof. Kearfott,

Thank you very much for your valuable comments and appreciation of our work
on the Taylor-Bernstein form. Thanks also for the clarifications on
Gritton's problem and your work with Dr. Arazyan (reported in the AD 2000
proceedings) concerning the Taylor model and Globsol results.

Our work has been so far done using just the "basic" Moore-Skelboe
algorithm, with only the cut-off and monotonicity steps added. No other
steps such as concavity, Newton steps, etc., have been used for any of the
inclusion forms. As your default Globsol results of Gritton's problem show,
the comparisons would probably appear in quite a different light, with the
other steps included.

We hope to do such a study in the near future.


Regards,
Nataraj

..............................................
Prof. P. S. V. Nataraj
Systems and Control Engineering Group
Department of Electrical Engineering
Indian Institute of Technology
Bombay 400 076 India
Ph: +91-022-5723757 Fax: +91-022-5726263
Email: nataraj [at] ee [dot] iitb.ernet.in

-----Original Message-----
From: owner-reliable_computing [at] interval [dot] louisiana.edu
[mailto:owner-reliable_computing [at] interval [dot] louisiana.edu]On Behalf Of R.
Baker Kearfott
Sent: Sunday, March 31, 2002 2:58 AM
To: markst [at] nd [dot] edu; reliable_computing [at] interval [dot] louisiana.edu
Cc: P. S. V. Nataraj
Subject: Re: Taylor models - how to get valid comparisons


Mark,

Thank you for the enlightenment.  It's nice to run realistic test
problems, even when we're just testing optimization packages :-)
I'm sure J. D. Seader knew about Gritton's problem;  he must have
just given it to me over [-12,8] as a challenge or a test problem.


In any case, I've solved the nonlinear system over [0,1],
and attached the output from the present version of GlobSol
(just for fun).  Apparently, the problem over [0,1] is significantly
easier :-)  You can probably do even better than GlobSol with your
group's codes.

Best regards,

Baker


P.S. My tardy reply was due to air conditioning problems where
     the university's incoming mail server resides.  It is
     definitely spring :-)

At 05:15 PM 3/28/02 -0500, Mark Stadtherr wrote:
>
>An aside to the discussion of "Gritton's second problem"--
>While it may be interesting from a computational standpoint to
>find (rigorously) all roots in [-12,8], or the minimum
>in [1,2], it should be noted that the variable in this problem
>is a mole fraction, which by definition must be in [0,1].
>Thus, from an application (chemical engineering) standpoint,
>it is pointless (and a waste of computational effort) to
>consider any interval other than [0,1].  Incidently, there
>is (exactly) one root in [0,1].
>
>Mark
>
>--
>Mark A. Stadtherr
>Professor
>Department of Chemical Engineering
>University of Notre Dame
>Notre Dame, IN 46556 USA
>Telephone:  (574) 631-9318
>Fax:        (574) 631-8366
>E-mail:     markst [at] nd [dot] edu
>WWW:        http://www.nd.edu/~markst
>
>========================================================================
>
>"R. Baker Kearfott" wrote:
>>
>> Prof. Nataraj,
>>
>> That is impressive work overall.  It is a laudable contribution, and
>> the experiments make their point well.
>>
>> I wish to point out minor discrepancies in the experiments on page 10 of
>> the work you make available below, as follows:
>>
>> 1.  You define Gritton's second problem as finding the minimum of
>>     a particular degree 18 univariate polynomial.  However, the original
>>     problem that I got from Prof. Seader at the University of Utah
>>     was to find all of the ROOTS of that polynomial in [-12,8], not find
the
>>     minimum in [1,2].  Readers should take this into account when
comparing
>>     the results you report to the results in previous papers.
>>
>> 2.  You mention that "Kearfott and Arazyan report in [the AD 2000
>>     proceedings] that GlobSol had some difficulty in tackling this
>>     problem."  That is only true in a certain sense, as follows:
>>
>>     (a)  We did not report results on the minimization problem, only
>>          on the root-finding problem.  Using "find_roots" from
>>          an early version of GlobSol, all 18 roots were found without
>>          too much problem.  I attach the output file
>>
>>     (b)  I just tried  GlobSol with default configuration on the
>>          "minimization" version of Gritton's problem, and GlobSol
>>          found the minimum with NO problems on [-12,8], in particular,
>>          with only three bisections.
>>          (It reported .06 seconds on a 450 MHZ machine;  however,
>>          due to OS inadequacies, this is total elapsed time, and
>>          I was simultaneously processing a stereo MP3 stream
>>          through the CPU and a software-based network connection.)
>>          On your interval [1,2], the problem was indeed somewhat
>>          harder, with the default configuration and not using
>>          any Taylor arithmetic:  GlobSol made 516 bisections before
>>          obtaining the result, and took roughly 2 seconds of total
>>          elapsed time.  However, this is much less than the failure
>>          after an hour you reported with the raw Moore-Skelboe algorithm,
>>          regardless of timing questions.
>>
>>     (c)  GlobSol uses alternate techniques, such as finding approximate
>>          solutions followed by epsilon inflation and interval Newton
>>          methods, to make things efficient.
>>          However, GlobSol is configurable.  The purpose of our
experiments
>>          in the AD 2000 proceedings was to test the usefulness of the
>>          Taylor extensions defined by Berz; we turned off some of
GlobSol's
>>          capabilities to simplify the environment for our experiments.
>>          We did find that the Taylor extensions of Berz et al were very
>>          useful in certain circumstances.  Of course, your experiments
>>          show that your Bernstein-Taylor extensions are even better,
>>          and MUCH better at that, in certain circumstances.
>>
>> In any case, I'm impressed that you have found a practical way of doing
>> higher-order inclusions for multivariate functions.  I had been thinking
>> about that for some time, but had not devised a scheme :-)
>>
>> Best regards,
>>
>> Baker
>>
>> At 05:06 PM 3/8/02 +0530, P. S. V. Nataraj wrote:
>> >Dear All,
>> >
>> >For a new inclusion function form having higher order convergence, along
>> >with a  convergence study of this form vs. that of Berz's Taylor model,
pl.
>> >see our paper (under review):
>> >www.ee.iitb.ac.in/~nataraj/Super_TB_ps.zip
>> >In the new form, Bernstein polynomial techniques were used to bound the
>> >range of the Taylor polynomial part.  We studied in this paper six
problems,
>> >of dimensions varying from 1 to 6.
>> >
>> >The new form (along with Taylor model) has also been used in a modified
>> >Moore-Skelboe Global Optimization algorithm in our paper (to appear in
Jl.
>> >Global Optimization)
>> >www.ee.iitb.ac.in/~nataraj/GOTB_Final_PS.zip
>> >
>> >In all our studies, we badly needed a good collection of challenge
problems
>> >to study the convergence behavior of the various forms.
>> >
>> >Can somebody suggest a good collection of such problems  - preferably
with a
>> >structure more general than polynomial, and dimensions varying from 1 to
(at
>> >least) 6 ?
>> >
>> >Regards,
>> >Nataraj
>> >
>> >..............................................
>> >Prof. P. S. V. Nataraj
>> >Systems and Control Engineering Group
>> >Department of Electrical Engineering
>> >Indian Institute of Technology
>> >Bombay 400 076 India
>> >Ph: +91-022-5723757 Fax: +91-022-5726263
>> >Email: nataraj [at] ee [dot] iitb.ernet.in
>> >
>> >-----Original Message-----
>> >From: owner-reliable_computing [at] interval [dot] louisiana.edu
>> >[mailto:owner-reliable_computing [at] interval [dot] louisiana.edu]On Behalf Of
>> >Arnold Neumaier
>> >Sent: Thursday, March 07, 2002 1:12 AM
>> >To: berz [at] msu [dot] edu; reliable_computing [at] interval [dot] louisiana.edu
>> >Subject: Re: Taylor models - how to get valid comparisons
>> >
>> >
>> >Arnold Neumaier wrote:
>> >
>> >> you'd have to compare it at least to techniques that use centered
forms
>> >> with slopes which are available for easy use in Rump's INTLAB
>> >> (and perhaps to Bernstein polynomial techniques, and to affine
>> >> arithmetic),
>> >
>> >Another relevant comparison would be to a modified Moore-Skelboe
>> >algorithm,
>> >applied twice to get the lower and upper bound. This is a little
>> >inefficient since part of the wirk is duplicated, but it has the
>> >advantage that it can be done in a simple way since the NEOS server
>> >allows one to solve global optimization problems on a box online
>> >via the WWW. See
>> >http://www-neos.mcs.anl.gov/neos/solvers/GO:GLOBMIN/
>> >---
>> >Incoming mail is certified Virus Free.
>> >Checked by AVG anti-virus system (http://www.grisoft.com).
>> >Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
>> >
>> >---
>> >Outgoing mail is certified Virus Free.
>> >Checked by AVG anti-virus system (http://www.grisoft.com).
>> >Version: 6.0.325 / Virus Database: 182 - Release Date: 2/19/02
>> >
>> >
>> >
>>
>>   -----------------------------------------------------------------------
-
>>
>>    gritton2.RO1Name: gritton2.RO1
>>                Type: Plain Text (text/plain)
>>
>>   -----------------------------------------------------------------------
-
>>
>> ---------------------------------------------------------------
>> R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
>> (337) 482-5270 (work)                     (337) 981-9744 (home)
>> URL: http://interval.louisiana.edu/kearfott.html
>> Department of Mathematics, University of Louisiana at Lafayette
>> Box 4-1010, Lafayette, LA 70504-1010, USA
>> ---------------------------------------------------------------
>
>--
>Mark A. Stadtherr
>Professor
>Department of Chemical Engineering
>University of Notre Dame
>Notre Dame, IN 46556 USA
>Telephone:  (219) 631-9318
>Fax:        (219) 631-8366
>E-mail:     markst [at] nd [dot] edu
>WWW:        http://www.nd.edu/~markst
>
>
---
Incoming mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.338 / Virus Database: 189 - Release Date: 3/14/02

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.338 / Virus Database: 189 - Release Date: 3/14/02



From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Apr  1 06:44:02 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g31Ci1L05807
	for reliable_computing-outgoing; Mon, 1 Apr 2002 06:44:01 -0600 (CST)
Received: from mail.epost.de ([64.39.38.76])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g31Cht305800
	for <reliable_computing [at] interval [dot] louisiana.edu>; Mon, 1 Apr 2002 06:43:56 -0600 (CST)
Received: from TP570MSUKM (12.245.210.11) by mail.epost.de (5.5.056) (authenticated as Kyoko.Makino [at] epost [dot] de)
        id 3C9E442F00155979; Mon, 1 Apr 2002 14:43:54 +0200
Reply-To: <makino [at] uiuc [dot] edu>
From: "Kyoko Makino" <makino [at] uiuc [dot] edu>
To: <reliable_computing [at] interval [dot] louisiana.edu>
Subject: RE: Taylor models - how to get valid comparisons
Date: Mon, 1 Apr 2002 07:44:29 -0500
Message-ID: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="Windows-1252"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
In-reply-to: <NEBBJIKHDMLBDKBEGMNECEDHCDAA.nataraj [at] ee [dot] iitb.ernet.in>
X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Importance: Normal
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Baker, Prof. Nataraj, and Intervalers,

we would like to make some additional remarks about the Gritton example, both about 
range bounding and about performance of other evaluation forms. Thank you for 
bringing this interesting topic to the community. 

1. While the amount of overestimation is an important issue, as the paper 'Super-
Convergence ...' by Prof. Nataraj and Kotecha discusses, listing the really
occurring ranges or widths is also important for the purpose of checking
practical usefulness of the various range bounders. Especially, if the exact bound
is known for some test problems, it should be noted. Often, the actual improvement
in the width by the different bounders is only a small fraction. As seen below,
the particular case of Gritton's problem discussed in the paper 'Super-Convergence
...' is such a case.

2. Regarding superconvergence, we studied Gritton's problem using Taylor models
with the linear dominating range bounder outlined in my dissertation (in the
following, denoted LDB), which uses the fact that as the domains get smaller and
smaller, the lowest orders are more and more dominant. This algorithm has been
implemented in the FORTRAN layer of COSY by Jens Hoefkens in late 1999 / early 2000
and is also available in a higher level version of the object oriented COSY language.
Baker and John Pryce may remember that we analyzed it during the "mini" workshop
at MSU in early 2000 that Baker mentioned in his AD2000 paper.

We compare this with the Horner evaluation and give rigorous enclosures. 
Like Prof. Nataraj and Kotecha in their paper, we choose the domain as
-1 + [-1,1]*2^{-i}, where i = 0, ... ,7, and we use the similar format with
their tables, except for listing the range obtained by rastering. 
The range is estimated through 1000 points, using a small tool in COSY;
Baker described it nicely in his AD2000 paper. We estimate the overestimation
compared to this inner range. TPD denotes naive Taylor polynomial evaluation,
described as 'No.1' method in my dissertation; it is quite fast and is used as
the default method in our current Taylor model implementation in COSY. Hence,
as far as I can see, what Prof. Nataraj and Kotecha refer to 'Taylor model'
means this evaluation. LDB denotes the linear dominating bounder. 
We show orders 4 and 8. 

Overestimation over the domain: -1 + [-1,1]*2^{-i}.

i      Range     TPD 4th     LDB 4th     TPD 8th     LDB 8th     
0     260764     1628450     1628450     1286226     1286226       
1     152521      110226       38706      105963           6.9
2      79684       16352        1115       16285           8.5E-3
3      39560        3678          33.6      3677           1.3E-5
4      19723         902           1.1       902           2.2E-8
5       9854         225           3.2E-2    225           3.1E-10
6       4926          56.1         1.0E-3     56.1         2.7E-10  
7       2463          14.1         3.1E-5     14.1         2.6E-10

* 'Range' is evaluated by rastering of 1000 points, hence is an inner bound.
* It is shown that the function is guaranteed to be monotonic for cases i=2,3,...


The overestimation is in fact superconvergent with order (n+1), too. And, the
LDB performs as well as the Taylor-Bernstein approach. Furthermore, 
it is better to not simply give the name 'Taylor model' to the naive interval
evaluation of the Taylor polynomial part. In my dissertation I have tried 
to clearly distinguish between the Taylor model approach itself and the actual 
underlying polynomial bounder being used. 


3. The algorithm of the linear dominated range bounder on the box [-h,h]^d is very 
simple: Obtain an initial bound B1 of the linear part L= sum_{j=1}^d cj xj 
(scales with h) and one of the higher order parts B2 (scales with h^2). In each 
direction xj, the maximizing point cannot occur more than B2/cj away from the
maximizing point of the linear part L, which if cj is assumed positive reduces
the box to [ max(-h,h-B2/cj) , h ]. Recenter in the new box and iterate until the
box size stabilizes. 

Of course for a large B2, there may not be much or not any reduction in box size; 
but as h goes to 0, since B2 ~ h^2, and since the linear parts in any new boxes will 
eventually not differ by more than say a factor of 2 from cj, there will eventually
be convergence to one of the boxes. In practice, the convergence happens in a few to
several iterations. At that time, the corner point has been shown to be the actual
maximizing point; and of course combined with the Taylor remainder bound which
scales with order (n+1), we thus have order (n+1) convergence. 

For practical calculations, it is nice that even if the maximum is not yet in the 
corner point, the method still usually performs a few iterations and reduces the 
range compared to other bounders. It is also possible by a single box splitting to 
make the method works if the first derivatives are zero, or even if several of 
the lower derivatives are zero.


4. As pointed out by Baker, the numerically (but not scientifically) more 
interesting region of the Gritton function is [1,2], and things are particularly 
critical around 1.4. We repeat the calculation around the point 1.4, but for the 
purpose of comparison, we also show the overestimations of the interval evaluation, 
evaluation using the centered form (CF) and mean value form (MVF) as described 
in many books, including Moore's 1979 book. 


Overestimation over the domain: 1.4 + [-1,1]*2^{-i}.

i   Range    Interval     CF       MVF      TPD 8th       LDB 8th
0  224       4833275   5976707   20157942     4081         4081
1    4.7      552935    517868    1108831       52.5         52.5
2    2.0      145534     90638     157031        2.2          2.2
3    3.8E-1    51899     20517      28746        2.1E-1       2.1E-2
4    8.6E-2    21845      5000       6108        3.7E-2       3.7E-2
5    2.7E-2    10316      1242       1422        9.9E-3       1.8E-3
6    1.2E-2     5048       310        348        2.7E-3       3.9E-10   
7    5.5E-3     2499        78         86        6.7E-4       3.7E-10

* 'Range' is evaluated by rastering of 1000 points, hence is an inner bound.


We see that

a) Centered Form and Mean Value Form scale quadratic as expected, but they suffer 
from a dependency problem like the original function. Centered Form is slightly
better than Mean Value Form.

b) The linear Taylor model scales quadratically too but yields sharper bounds; 
and higher order Taylor models yield sharper bounds yet. 

c) The Taylor model method does not suffer the dependency problem, and any of the 
Taylor model based schemes lead to relatively sharp estimates.

d) Again, indeed the Taylor method is superconvergent with order (n+1).


As Prof. Nataraj already pointed out, it would be useful to have many more
good test problems for such algorithms.


Best regards, 

Kyoko

P.S.: We regret that we could not post for weeks about the Taylor model related
discussions. Besides two Physics meeting trips, a move of the offices of
Martin's whole group to a new building took our latest attention. (I also have
an office at MSU as a frequent visitor.) Connected to the move, the web server
changed the address: in general from ***.nscl.msu.edu to ***.pa.msu.edu.
Also, we've been having quite heavy discussions about Taylor models off-line
in the last weeks. We will try to address as many questions as our time and
energy permit.
---
Kyoko Makino
Department of Physics
University of Illinois at Urbana-Champaign
makino [at] uiuc [dot] edu


From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Apr  1 07:14:46 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g31DEjJ05950
	for reliable_computing-outgoing; Mon, 1 Apr 2002 07:14:45 -0600 (CST)
Received: from mail.epost.de ([64.39.38.76])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g31DEe305946
	for <reliable_computing [at] interval [dot] louisiana.edu>; Mon, 1 Apr 2002 07:14:41 -0600 (CST)
Received: from TP570MSUKM (12.245.210.11) by mail.epost.de (5.5.056) (authenticated as Kyoko.Makino [at] epost [dot] de)
        id 3C9E442F001568D6; Mon, 1 Apr 2002 15:14:39 +0200
Reply-To: <makino [at] uiuc [dot] edu>
From: "Kyoko Makino" <makino [at] uiuc [dot] edu>
To: <reliable_computing [at] interval [dot] louisiana.edu>
Cc: <rbk [at] louisiana [dot] edu>
Subject: More about Taylor model polynomial bounders
Date: Mon, 1 Apr 2002 08:15:14 -0500
Message-ID: <NEBBLGMLDAEBJEKKJNEKIEFBENAA.makino [at] uiuc [dot] edu>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Importance: Normal
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Prof. Nataraj, Baker, et al.

Here are some more examples using the LDB bounder for bounding of the polynomial
part in Taylor models, this time for high-dimensional problems up to dimension 10. The
bounder can easily handle these problems with CPU times in the range of seconds with a similar accuracy to the methods reported
by Prof. Nataraj and Kotecha.

1. Problem 4.6, the six dimensional example function suggested by Nataraj and
Kotecha in their paper "Super-Convergence ... ". We performed calculations of
orders 2, 4, 6, and 8, and determined the overestimation. The notation is like in
Prof. Nataraj's paper, i.e. we use the expansion point 1.75^6 and domain width
around it of [-1,1]*2^{-i} for i=0, ... , 7. For the sake of compactness we show
the range estimate from rastering and fourth and eight order Taylor model results only.
We determine overestimations against the inner estimate. We denote by TPD the direct polynomial evaluation of the Taylor model,
and by LDB the use of the linear dominated
bounder. As in Nataraj's paper, only a few digits are shown for compactness; we are
happy to send out detailed output files upon request. Execution times were less than
1 sec on a Pentium III 450 MHz for LDB 8th, compared to 3 hours for Prof. Nataraj's
approach.


I      Range      TPD 4th     LDB 4th     TPD 8th     LDB 8th
0      1965       2247        2427        2246       2434
1      1148        369         404         369        404
2       597         73         1.6E-2       73        2.5E-7
3       301         16         3.3E-4       16        3.6E-10
4       151          4         7.9E-6        3.8      1.1E-12
5        76          0.92      2.1E-7        0.92     1.2E-13
6        37.8        0.23      5.9E-9        0.23     1.2E-13
7        18.9        0.06      1.8E-10       0.06     1.2E-13


2. An example function similar to the previous one, but in 10 dimensions. The
function merely contains a sum over dimensions, and it is obvious how to extend it
to higher dimensions. CPU time was around 30 sec on a Pentium III 450 MHz for LBD
8th.


I      Range      TPD 4th     LDB 4th     TPD 8th     LDB 8th
0      8849      10491       10967       10519      11024
1      5229       1702        1788        1703       1789
2      2725        333         281         333        281
3      1377         73         9.3E-4       73        8.7E-10
4       690         17.0       1.9E-5       17.0      3.7E-12
5       345          4.1       4.2E-7        4.1      2.3E-12
6       173          1.1       1.1E-8        1.1      1.4E-12
7        86          0.25      2.9E-10       0.25     1.0E-12

In both cases, it should be noted that in the beginning the inner estimate is likely
too pessimistic, which is one reason for the initially larger overestimations;
another reason is that the LDB algorithm cannot yet contract boxes
sufficiently. For smaller boxes, the algorithm behaves close to the scaling
law of order (n+1). Furthermore, it puts into perspective the amount of actual
overestimation, which here even over a domain width of 2 represents only
a factor of two in the very worst case, and for smaller ranges is much less for any
bounder.

It is also worth noting that the reason why in the initial stages LDB yields
slightly larger overestimations than direct polynomial evaluation is because the
latter uses a scheme that recognizes squares and treats them as positive, while the
method used here for LDB does not; this can be changed with minor additional
effort, and we are happy to re-post upon request.

Best regards,

Kyoko

---
Kyoko Makino
Department of Physics
University of Illinois at Urbana-Champaign
makino [at] uiuc [dot] edu


From owner-reliable_computing [at] interval [dot] louisiana.edu Mon Apr  1 09:00:02 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g31F01e06225
	for reliable_computing-outgoing; Mon, 1 Apr 2002 09:00:01 -0600 (CST)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g31Exv306214
	for <reliable_computing [at] interval [dot] louisiana.edu>; Mon, 1 Apr 2002 08:59:57 -0600 (CST)
Received: from aragorn (aragorn [129.108.5.35])
	by cs.utep.edu (8.11.3/8.11.3) with SMTP id g31ExrU07176
	for <reliable_computing [at] interval [dot] louisiana.edu>; Mon, 1 Apr 2002 07:59:53 -0700 (MST)
Message-Id: <200204011459.g31ExrU07176 [at] cs [dot] utep.edu>
Date: Mon, 1 Apr 2002 07:59:51 -0700 (MST)
From: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Reply-To: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Subject: from NA Digest
To: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: uNwKFnPnwU0545DamVL/Yw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc 
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

From: Jorge More' <more [at] mcs [dot] anl.gov>
Date: Sun, 24 Mar 2002 15:09:25 -0600
Subject: Wilkinson Prize for Numerical Software

THE WILKINSON PRIZE FOR NUMERICAL SOFTWARE

In honor of the outstanding contributions of James Hardy Wilkinson to
the field of numerical software, Argonne National Laboratory, the
National Physical Laboratory, and the Numerical Algorithms Group award
a numerical software prize of US $1000.  The first prize was awarded
to Linda Petzold for DASSL at the International Conference in
Industrial and Applied Mathematics (ICIAM 91), the second prize was
awarded to Chris Bischof and Alan Carle for ADIFOR 2.0 at ICIAM 95,
and the third prize was awarded to Matteo Frigo and Steven Johnson for
FFTW at ICIAM 99.

The 2003 prize will be awarded at ICIAM 2003 in Sydney, July 7-11, 2003.

Rules for Submission

Each author of an entry must be at most 40 years of age on January 1, 2003. 
Each entry must contain the following:

  Software written in a widely available high-level programming language.

  A paper describing the algorithm and the software implementation.
  The paper should give an analysis of the algorithm and indicate any
  special programming features.

  Documentation of the software, which describes its purpose and method of use.

  Examples of use of the software, including a test program and data.
  A (two page) summary of the main features of the algorithm and
  software implementation.

Submissions must be in English. Entries must be received by November 4, 2002.

Selection Criteria

The award will be made to the entry that best addresses all phases of the
preparation of high-quality numerical software, including

  Clarity of the paper and of the software implementation and documentation;

  Portability, reliability, efficiency, and usability of the software 
implementation;

  Depth of analysis of the algorithm and the software;

  Importance of application addressed by the software; 

  Quality of the test software.

Submissions

Submissions ideally be in the form of a uuencoded, gzipped, tar archive.  
Submissions should include a README file describing the contents of the 
archive and Makefiles for executing the test programs.
Submissions can be sent by email to wilkinson-prize [at] mcs [dot] anl.gov.
Contact this address for further information.


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 08:49:37 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32Ena909051
	for reliable_computing-outgoing; Tue, 2 Apr 2002 08:49:36 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32EnU309047
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 08:49:31 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
	by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g32EnMxf039148;
	Tue, 2 Apr 2002 16:49:25 +0200
Message-ID: <3CA9C4F2.34A389F7 [at] univie [dot] ac.at>
Date: Tue, 02 Apr 2002 16:49:22 +0200
From: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-31 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: reliable_computing [at] interval [dot] louisiana.edu
Subject: Gritton2
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk


We'd at least have the problem definition correct.
I programmed Gritton2 according to the coefficients in 
Kearfott and Arazyan, and got instead of a root at 1.381
one at 0.7241=1/1.381. Can it be that the coefficients in that 
paper should be in reverse order?

Arnold Neumaier

===============================================================

The following Matlab program treats first a simple quadratic, 
then gritton2

coef=[1 -4 4]; % 1-4*x+4*x^2 has double root 1/2
trivial_roots=sort(roots(coef))             % wrong formula
trivial_roots=sort(roots(coef(end:-1:1)))   % right formula

coef=[
+0.0002274682229
-0.0001951095576
-0.03589148622
+0.1245990848
1.575580173
-8.88303902
-16.17913459
+202.6270915
-283.4435875
-1281.47944
+4782.532296
-3518.536872
-9326.549359
+22140.72827
-16547.8928
+978.1375167
+4044.944143
-791.2465656
-371.93625
];
gritton_roots=sort(roots(coef(end:-1:1)))

gritton_roots =
   -3.6041
   -3.0086
   -0.5148
   -0.2709
   -0.2004
   -0.1602
   -0.0901
    0.1437
    0.2049
    0.2824
    0.3648
    0.4375
    0.5084
    0.5708
    0.6275
    0.6757
    0.7241
    1.1821

From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 09:38:26 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32FcPA09241
	for reliable_computing-outgoing; Tue, 2 Apr 2002 09:38:25 -0600 (CST)
Received: from imf03bis.bellsouth.net (mail203.mail.bellsouth.net [205.152.58.143])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32FcG309236
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 09:38:16 -0600 (CST)
Received: from u8174 ([65.83.165.52]) by imf03bis.bellsouth.net
          (InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
          id <20020402153931.OCFJ27421.imf03bis.bellsouth.net@u8174>;
          Tue, 2 Apr 2002 10:39:31 -0500
Message-Id: <2.2.32.20020402153751.009da774 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 02 Apr 2002 09:37:51 -0600
To: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>,
   reliable_computing [at] interval [dot] louisiana.edu
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: Gritton2
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Arnold,

Alas, you are right :-(  Here is what I have in the
GlobSol file defining Gritton's problem:  

! Using Horner's scheme --

 F(1) =  -0.371936250000000D+03 + X(1)* (  &
         -0.791246565600000D+03 + X(1)* (  &
          0.404494414300000D+04 + X(1)* (  &
          0.978137516700000D+03 + X(1)* (  &
         -0.165478928000000D+05 + X(1)* (  &
          0.221407282700000D+05 + X(1)* (  &
         -0.932654935900000D+04 + X(1)* (  &
         -0.351853687200000D+04 + X(1)* (  &
          0.478253229600000D+04 + X(1)* (  &
         -0.128147944000000D+04 + X(1)* (  &
         -0.283443587500000D+03 + X(1)* (  &
          0.202627091500000D+03 + X(1)* (  &
         -0.161791345900000D+02 + X(1)* (  &
         -0.888303902000000D+01 + X(1)* (  &
          0.157558017300000D+01 + X(1)* (  &
          0.124599084800000D+00 + X(1)* (  &
         -0.358914862200000D-01 + X(1)* (  &
         -0.195109557600000D-03 + X(1)* (  &
          0.227468222900000D-03 ))))))))))))))))))

The above definition has 18 simple roots in [-12,8], as
Seader expressed to me.

In any case, thank you for pointing this out.

Best regards,

Baker

At 04:49 PM 4/2/02 +0200, Arnold Neumaier wrote:
>
>We'd at least have the problem definition correct.
>I programmed Gritton2 according to the coefficients in 
>Kearfott and Arazyan, and got instead of a root at 1.381
>one at 0.7241=1/1.381. Can it be that the coefficients in that 
>paper should be in reverse order?
>
>Arnold Neumaier
>
>===============================================================
>
>The following Matlab program treats first a simple quadratic, 
>then gritton2
>
>coef=[1 -4 4]; % 1-4*x+4*x^2 has double root 1/2
>trivial_roots=sort(roots(coef))             % wrong formula
>trivial_roots=sort(roots(coef(end:-1:1)))   % right formula
>
>coef=[
>+0.0002274682229
>-0.0001951095576
>-0.03589148622
>+0.1245990848
>1.575580173
>-8.88303902
>-16.17913459
>+202.6270915
>-283.4435875
>-1281.47944
>+4782.532296
>-3518.536872
>-9326.549359
>+22140.72827
>-16547.8928
>+978.1375167
>+4044.944143
>-791.2465656
>-371.93625
>];
>gritton_roots=sort(roots(coef(end:-1:1)))
>
>gritton_roots =
>   -3.6041
>   -3.0086
>   -0.5148
>   -0.2709
>   -0.2004
>   -0.1602
>   -0.0901
>    0.1437
>    0.2049
>    0.2824
>    0.3648
>    0.4375
>    0.5084
>    0.5708
>    0.6275
>    0.6757
>    0.7241
>    1.1821
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 10:41:04 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32Gf3r09499
	for reliable_computing-outgoing; Tue, 2 Apr 2002 10:41:03 -0600 (CST)
Received: from imf12bis.bellsouth.net (mail112.mail.bellsouth.net [205.152.58.52])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32Gex309495
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 10:40:59 -0600 (CST)
Received: from u8174 ([66.20.81.174]) by imf12bis.bellsouth.net
          (InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
          id <20020402164214.GAHQ8136.imf12bis.bellsouth.net@u8174>;
          Tue, 2 Apr 2002 11:42:14 -0500
Message-Id: <2.2.32.20020402164125.009ba6d8 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 02 Apr 2002 10:41:25 -0600
To: William Walster <Bill.Walster [at] Eng [dot] Sun.COM>
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: Gritton2
Cc: reliable_computing [at] interval [dot] louisiana.edu
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Bill,

I wasn't assuming the trailing zeros are significant.  I think I
created that file from fixed-format output from another program.

I agree with you concerning inputting the coefficients as intervals,
as representing a problem that more closely models reality.
That would also make a somewhat more interesting test problem.  I'll
see if I can try that :-)

Best regards,

Baker

At 08:16 AM 4/2/02 -0800, you wrote:
>
>Baker,
>
>Are you assuming the trailing zeros are significant?   Seems to 
>me that all these numbers should be entered as intervals with 
>[-1,+1]_uld added to the last significant digit (whatever that is)
>of the mantissa.
>
>That may smear out the problem somewhat, but that is the nature
>of the beast we are attacking.
>
>Cheers,
>
>Bill
>
>  >Date: Tue, 02 Apr 2002 09:37:51 -0600
>  >From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
>  >Subject: Re: Gritton2
>  >X-Sender: rbk5287 [at] pop [dot] louisiana.edu
>  >To: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>, 
>reliable_computing [at] interval [dot] louisiana.edu
>  >MIME-version: 1.0
>  >
>  >Arnold,
>  >
>  >Alas, you are right :-(  Here is what I have in the
>  >GlobSol file defining Gritton's problem:  
>  >
>  >! Using Horner's scheme --
>  >
>  > F(1) =  -0.371936250000000D+03 + X(1)* (  &
>  >         -0.791246565600000D+03 + X(1)* (  &
>  >          0.404494414300000D+04 + X(1)* (  &
>  >          0.978137516700000D+03 + X(1)* (  &
>  >         -0.165478928000000D+05 + X(1)* (  &
>  >          0.221407282700000D+05 + X(1)* (  &
>  >         -0.932654935900000D+04 + X(1)* (  &
>  >         -0.351853687200000D+04 + X(1)* (  &
>  >          0.478253229600000D+04 + X(1)* (  &
>  >         -0.128147944000000D+04 + X(1)* (  &
>  >         -0.283443587500000D+03 + X(1)* (  &
>  >          0.202627091500000D+03 + X(1)* (  &
>  >         -0.161791345900000D+02 + X(1)* (  &
>  >         -0.888303902000000D+01 + X(1)* (  &
>  >          0.157558017300000D+01 + X(1)* (  &
>  >          0.124599084800000D+00 + X(1)* (  &
>  >         -0.358914862200000D-01 + X(1)* (  &
>  >         -0.195109557600000D-03 + X(1)* (  &
>  >          0.227468222900000D-03 ))))))))))))))))))
>  >
>  >The above definition has 18 simple roots in [-12,8], as
>  >Seader expressed to me.
>  >
>  >In any case, thank you for pointing this out.
>  >
>  >Best regards,
>  >
>  >Baker
>  >
>  >At 04:49 PM 4/2/02 +0200, Arnold Neumaier wrote:
>  >>
>  >>We'd at least have the problem definition correct.
>  >>I programmed Gritton2 according to the coefficients in 
>  >>Kearfott and Arazyan, and got instead of a root at 1.381
>  >>one at 0.7241=1/1.381. Can it be that the coefficients in that 
>  >>paper should be in reverse order?
>  >>
>  >>Arnold Neumaier
>  >>
>  >>===============================================================
>  >>
>  >>The following Matlab program treats first a simple quadratic, 
>  >>then gritton2
>  >>
>  >>coef=[1 -4 4]; % 1-4*x+4*x^2 has double root 1/2
>  >>trivial_roots=sort(roots(coef))             % wrong formula
>  >>trivial_roots=sort(roots(coef(end:-1:1)))   % right formula
>  >>
>  >>coef=[
>  >>+0.0002274682229
>  >>-0.0001951095576
>  >>-0.03589148622
>  >>+0.1245990848
>  >>1.575580173
>  >>-8.88303902
>  >>-16.17913459
>  >>+202.6270915
>  >>-283.4435875
>  >>-1281.47944
>  >>+4782.532296
>  >>-3518.536872
>  >>-9326.549359
>  >>+22140.72827
>  >>-16547.8928
>  >>+978.1375167
>  >>+4044.944143
>  >>-791.2465656
>  >>-371.93625
>  >>];
>  >>gritton_roots=sort(roots(coef(end:-1:1)))
>  >>
>  >>gritton_roots =
>  >>   -3.6041
>  >>   -3.0086
>  >>   -0.5148
>  >>   -0.2709
>  >>   -0.2004
>  >>   -0.1602
>  >>   -0.0901
>  >>    0.1437
>  >>    0.2049
>  >>    0.2824
>  >>    0.3648
>  >>    0.4375
>  >>    0.5084
>  >>    0.5708
>  >>    0.6275
>  >>    0.6757
>  >>    0.7241
>  >>    1.1821
>  >>
>  >>
>  >---------------------------------------------------------------
>  >R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
>  >(337) 482-5270 (work)                     (337) 981-9744 (home)
>  >URL: http://interval.louisiana.edu/kearfott.html
>  >Department of Mathematics, University of Louisiana at Lafayette
>  >Box 4-1010, Lafayette, LA 70504-1010, USA
>  >---------------------------------------------------------------
>  >
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 12:59:35 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32IxZ509836
	for reliable_computing-outgoing; Tue, 2 Apr 2002 12:59:35 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32IxT309832
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 12:59:30 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
	by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g32IxMV01982812;
	Tue, 2 Apr 2002 20:59:23 +0200
Message-ID: <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at>
Date: Tue, 02 Apr 2002 20:59:22 +0200
From: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-31 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: makino [at] uiuc [dot] edu
CC: reliable_computing [at] interval [dot] louisiana.edu
Subject: Taylor models do *NOT* give high order range enclosures
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk


Against repeated claims by Berz and Makino, I want to reassert that
Taylor models in their current implementation (even with LDB) do  
*NOT*   
have more than second order approximation for range enclosure, except 
sufficiently far away from stationary points, where related monotony
arguments 
give the exact range (infinite order). See below my comments on Kyoko
Makino's 
posting.

While *high* approximation order is irrelevant in practice, *third*
order
is important, since, as shown by Kearfott and Du, it allows to eliminate
the
cluster effect in branch and bound methods for global optimization,
one of the main sources of inefficiency for many problems. 
Quadratic approximation order is not sufficient for this.

In particular, Taylor models, while reducing overestimation in many
interesting cases, are not suitable to fight the cluster effect in
global
optimization.

Arnold Neumaier



=========================

Kyoko Makino wrote:

> 2. Regarding superconvergence, we studied Gritton's problem using Taylor models
> with the linear dominating range bounder outlined in my dissertation (in the
> following, denoted LDB), which uses the fact that as the domains get smaller and
> smaller, the lowest orders are more and more dominant. 

> 3. The algorithm of the linear dominated range bounder on the box [-h,h]^d is very
> simple: Obtain an initial bound B1 of the linear part L= sum_{j=1}^d cj xj
> (scales with h) and one of the higher order parts B2 (scales with h^2). In each
> direction xj, the maximizing point cannot occur more than B2/cj away from the
> maximizing point of the linear part L, which if cj is assumed positive reduces
> the box to [ max(-h,h-B2/cj) , h ]. Recenter in the new box and iterate until the
> box size stabilizes.
> 
> Of course for a large B2, there may not be much or not any reduction in box size;
> but as h goes to 0, since B2 ~ h^2, and since the linear parts in any new boxes will
> eventually not differ by more than say a factor of 2 from cj, there will eventually
> be convergence to one of the boxes. In practice, the convergence happens in a few to
> several iterations. At that time, the corner point has been shown to be the actual
> maximizing point; and of course combined with the Taylor remainder bound which
> scales with order (n+1), we thus have order (n+1) convergence.

In this situation, the problem is in fact monotone, and using a
bicentered form
(as in my book p.59) with gradient computed by a Taylor form (to benefit
from the
cancellation effect), one even gets the exact range - infinite order. 
High order statements are therefore in this case not meaningful.
(But it suggests that it may be worth doing monotonicity tests using
Taylor forms.)

The correct test case for higher order than 2 is close to stationary
points 
since there branch and bound methods of order 2 only suffer from the
cluster effect
(as shown by Kearfott and Du). But precisely in this case where it would
be most 
needed, Taylor models with LDB  *FAIL*  to show the higher order.

> 4. As pointed out by Baker, the numerically (but not scientifically) more
> interesting region of the Gritton function is [1,2], and things are particularly
> critical around 1.4. We repeat the calculation around the point 1.4, but for the
> purpose of comparison, we also show the overestimations of the interval evaluation,
> evaluation using the centered form (CF) and mean value form (MVF) as described
> in many books, including Moore's 1979 book.

Actually, for optimization, things are particularly critical around
1.419332885742, 
which is a local minimizer. And if you center your intervals around this
point
or a closeby point for which the minimizer is within the box, your
method will only 
show second order convergence. Thus it is inadmissible to claim that

> d) Again, indeed the Taylor method is superconvergent with order (n+1).

From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 13:39:37 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32Jdba09982
	for reliable_computing-outgoing; Tue, 2 Apr 2002 13:39:37 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32JdW309978
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 13:39:32 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g32Jd2Z09064;
	Tue, 2 Apr 2002 14:39:04 -0500 (EST)
Message-ID: <001401c1da7d$d5201020$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Date: Tue, 2 Apr 2002 14:37:30 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MIMEOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Arnold,

What is the "cluster effect" in global optimization?

Ramon Moore

You wrote:
> . . . . 
> In particular, Taylor models, while reducing overestimation in many
> interesting cases, are not suitable to fight the cluster effect in
> global
> optimization.
> 
> Arnold Neumaier



From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 14:43:22 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32KhLL10171
	for reliable_computing-outgoing; Tue, 2 Apr 2002 14:43:21 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32KhH310167
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 14:43:17 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g32KgjZ21184;
	Tue, 2 Apr 2002 15:42:51 -0500 (EST)
Message-ID: <004001c1da86$bddc78a0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at> <001401c1da7d$d5201020$66ae1841 [at] columbus [dot] rr.com> <3CAA158B.5FCD8168 [at] univie [dot] ac.at>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Date: Tue, 2 Apr 2002 15:41:11 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MIMEOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Thanks, Arnold, for the explanation. Please forgive me for not being up on
all the global optimization literature. I had not heard that term before.

best wishes,  Ramon
----- Original Message -----
From: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
To: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
Sent: Tuesday, April 02, 2002 3:33 PM
Subject: Re: Taylor models do *NOT* give high order range enclosures


> Ramon Moore wrote:
>
> > What is the "cluster effect" in global optimization?
>
> Branch and bound methods for minimizing a function in a box
> (or a more complex region)
> frequently have the difficulty that subboxes containing no solution
> cannot be easily eliminated if there is a nearby good local minimum.
> This has the effect that near each zero, many small boxes are created
> by repeated splitting, whose processing may dominate the total work
> spent on the global search.
>
> This so-called cluster effect was explained and analyzed by
>
> R.B. Kearfott, K. Du,
> The Cluster Problem in Multivariate Global Optimization,
> J. Global Opt. 5 (1994), pp. 253--265.
>
> They showed that it is a necessary consequence of range enclosures with
> less than cubic approximation order, which leave an exponential number
> of boxes near a minimizer uneliminated. (There are other methods,
> e.g.,  verifying Fritz John conditions that can be used to fight the
> effect. See Kearfott's book.)
>


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 14:59:24 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32KxOv10286
	for reliable_computing-outgoing; Tue, 2 Apr 2002 14:59:24 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32KxI310282
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 14:59:19 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g32KwxZ10322;
	Tue, 2 Apr 2002 15:59:00 -0500 (EST)
Message-ID: <005301c1da88$ff4369a0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at> <001401c1da7d$d5201020$66ae1841 [at] columbus [dot] rr.com> <3CAA158B.5FCD8168 [at] univie [dot] ac.at>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Date: Tue, 2 Apr 2002 15:57:25 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MIMEOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Wouldn't the midpoint test limit the cluster effect unless the value of the
objective function happens to be nearly as small as the global minimum
value?

Ramon Moore
----- Original Message -----
From: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
To: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
Sent: Tuesday, April 02, 2002 3:33 PM
Subject: Re: Taylor models do *NOT* give high order range enclosures


> Ramon Moore wrote:
>
> > What is the "cluster effect" in global optimization?
>
> Branch and bound methods for minimizing a function in a box
> (or a more complex region)
> frequently have the difficulty that subboxes containing no solution
> cannot be easily eliminated if there is a nearby good local minimum.
> This has the effect that near each zero, many small boxes are created
> by repeated splitting, whose processing may dominate the total work
> spent on the global search.
>
> This so-called cluster effect was explained and analyzed by
>
> R.B. Kearfott, K. Du,
> The Cluster Problem in Multivariate Global Optimization,
> J. Global Opt. 5 (1994), pp. 253--265.
>
> They showed that it is a necessary consequence of range enclosures with
> less than cubic approximation order, which leave an exponential number
> of boxes near a minimizer uneliminated. (There are other methods,
> e.g.,  verifying Fritz John conditions that can be used to fight the
> effect. See Kearfott's book.)
>


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 15:12:06 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32LC5810397
	for reliable_computing-outgoing; Tue, 2 Apr 2002 15:12:05 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32LC1310393
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 15:12:01 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g32LC0Z26254
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 16:12:00 -0500 (EST)
Message-ID: <007b01c1da8a$cf648d20$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
Subject: cluster effect
Date: Tue, 2 Apr 2002 16:10:25 -0500
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_NextPart_000_0078_01C1DA60.E5E6AC60"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MIMEOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

This is a multi-part message in MIME format.

------=_NextPart_000_0078_01C1DA60.E5E6AC60
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Dear colleagues,

For what kinds of practical problems in global optimization has the =
cluster effect been noticed?

How, if at all, in those cases, has it been overcome?

best regards,  Ramon Moore

------=_NextPart_000_0078_01C1DA60.E5E6AC60
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 5.50.4134.600" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial>Dear colleagues,</FONT></DIV>
<DIV><FONT face=3DArial></FONT>&nbsp;</DIV>
<DIV><FONT face=3DArial>For what kinds of practical problems in global=20
optimization has the cluster effect been noticed?</FONT></DIV>
<DIV><FONT face=3DArial></FONT>&nbsp;</DIV>
<DIV><FONT face=3DArial>How, if at all, in those cases, has it been=20
overcome?</FONT></DIV>
<DIV><FONT face=3DArial></FONT>&nbsp;</DIV>
<DIV><FONT face=3DArial>best regards,&nbsp; Ramon =
Moore</FONT></DIV></BODY></HTML>

------=_NextPart_000_0078_01C1DA60.E5E6AC60--


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 16:09:42 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32M9g010569
	for reliable_computing-outgoing; Tue, 2 Apr 2002 16:09:42 -0600 (CST)
Received: from imf12bis.bellsouth.net (mail112.mail.bellsouth.net [205.152.58.52])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32M9b310565
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 16:09:38 -0600 (CST)
Received: from u8174 ([65.81.243.137]) by imf12bis.bellsouth.net
          (InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
          id <20020402221052.LKZU8136.imf12bis.bellsouth.net@u8174>
          for <reliable_computing [at] interval [dot] louisiana.edu>;
          Tue, 2 Apr 2002 17:10:52 -0500
Message-Id: <2.2.32.20020402220938.009b8f60 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 02 Apr 2002 16:09:38 -0600
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Ray (et al),

Our analysis was based on the algorithm with the midpoint test.  In
fact, the problem still occurs, even if we use the exact value of
the global optimum (rather than a value computed via the midpoint
test.)  However, unless we made some kind of error, we only showed
an exponential increase in the number of boxes in the list (as the
tolerance is decreased) when the order is strictly less than 2. 
When the order is exactly two, we get, in general, more than one
box in the list, but we didn't prove an exponential increase. For
orders greater than 2, we obtain only one box around an isolated 
optimizer, in the limit as we decrease the tolerance.  

We provide experimental results to illustrate this.

Of course, if there is uncertainty in the problem, etc., that
affects the practical computations.

Preprints of two papers (one for the univariate case and one that
generalizes to the multivariate case) can be obtained from the
web page

http://interval.louisiana.edu/preprints.html

Search that page for "cluster" (or "Cluster").

Best regards,

Baker

At 03:57 PM 4/2/02 -0500, Ramon Moore wrote:
>Wouldn't the midpoint test limit the cluster effect unless the value of the
>objective function happens to be nearly as small as the global minimum
>value?
>
>Ramon Moore
>----- Original Message -----
>From: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
>To: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
>Sent: Tuesday, April 02, 2002 3:33 PM
>Subject: Re: Taylor models do *NOT* give high order range enclosures
>
>
>> Ramon Moore wrote:
>>
>> > What is the "cluster effect" in global optimization?
>>
>> Branch and bound methods for minimizing a function in a box
>> (or a more complex region)
>> frequently have the difficulty that subboxes containing no solution
>> cannot be easily eliminated if there is a nearby good local minimum.
>> This has the effect that near each zero, many small boxes are created
>> by repeated splitting, whose processing may dominate the total work
>> spent on the global search.
>>
>> This so-called cluster effect was explained and analyzed by
>>
>> R.B. Kearfott, K. Du,
>> The Cluster Problem in Multivariate Global Optimization,
>> J. Global Opt. 5 (1994), pp. 253--265.
>>
>> They showed that it is a necessary consequence of range enclosures with
>> less than cubic approximation order, which leave an exponential number
>> of boxes near a minimizer uneliminated. (There are other methods,
>> e.g.,  verifying Fritz John conditions that can be used to fight the
>> effect. See Kearfott's book.)
>>
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 16:15:53 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g32MFq010663
	for reliable_computing-outgoing; Tue, 2 Apr 2002 16:15:52 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g32MFj310659
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 16:15:45 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g32MFgZ14424;
	Tue, 2 Apr 2002 17:15:42 -0500 (EST)
Message-ID: <00fd01c1da93$b4229ee0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <2.2.32.20020402220938.009b8f60 [at] pop [dot] louisiana.edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Date: Tue, 2 Apr 2002 17:14:05 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MIMEOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Baker,

Thanks very much. I'll read your papers on that.
----- Original Message -----
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
Sent: Tuesday, April 02, 2002 5:09 PM
Subject: Re: Taylor models do *NOT* give high order range enclosures


> Ray (et al),
>
> Our analysis was based on the algorithm with the midpoint test.  In
> fact, the problem still occurs, even if we use the exact value of
> the global optimum (rather than a value computed via the midpoint
> test.)  However, unless we made some kind of error, we only showed
> an exponential increase in the number of boxes in the list (as the
> tolerance is decreased) when the order is strictly less than 2.
> When the order is exactly two, we get, in general, more than one
> box in the list, but we didn't prove an exponential increase. For
> orders greater than 2, we obtain only one box around an isolated
> optimizer, in the limit as we decrease the tolerance.
>
> We provide experimental results to illustrate this.
>
> Of course, if there is uncertainty in the problem, etc., that
> affects the practical computations.
>
> Preprints of two papers (one for the univariate case and one that
> generalizes to the multivariate case) can be obtained from the
> web page
>
> http://interval.louisiana.edu/preprints.html
>
> Search that page for "cluster" (or "Cluster").
>
> Best regards,
>
> Baker
>
> At 03:57 PM 4/2/02 -0500, Ramon Moore wrote:
> >Wouldn't the midpoint test limit the cluster effect unless the value of
the
> >objective function happens to be nearly as small as the global minimum
> >value?
> >
> >Ramon Moore
> >----- Original Message -----
> >From: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
> >To: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
> >Sent: Tuesday, April 02, 2002 3:33 PM
> >Subject: Re: Taylor models do *NOT* give high order range enclosures
> >
> >
> >> Ramon Moore wrote:
> >>
> >> > What is the "cluster effect" in global optimization?
> >>
> >> Branch and bound methods for minimizing a function in a box
> >> (or a more complex region)
> >> frequently have the difficulty that subboxes containing no solution
> >> cannot be easily eliminated if there is a nearby good local minimum.
> >> This has the effect that near each zero, many small boxes are created
> >> by repeated splitting, whose processing may dominate the total work
> >> spent on the global search.
> >>
> >> This so-called cluster effect was explained and analyzed by
> >>
> >> R.B. Kearfott, K. Du,
> >> The Cluster Problem in Multivariate Global Optimization,
> >> J. Global Opt. 5 (1994), pp. 253--265.
> >>
> >> They showed that it is a necessary consequence of range enclosures with
> >> less than cubic approximation order, which leave an exponential number
> >> of boxes near a minimizer uneliminated. (There are other methods,
> >> e.g.,  verifying Fritz John conditions that can be used to fight the
> >> effect. See Kearfott's book.)
> >>
> >
> >
> ---------------------------------------------------------------
> R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
> (337) 482-5270 (work)                     (337) 981-9744 (home)
> URL: http://interval.louisiana.edu/kearfott.html
> Department of Mathematics, University of Louisiana at Lafayette
> Box 4-1010, Lafayette, LA 70504-1010, USA
> ---------------------------------------------------------------
>


From owner-reliable_computing [at] interval [dot] louisiana.edu Tue Apr  2 18:32:12 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g330WCJ11051
	for reliable_computing-outgoing; Tue, 2 Apr 2002 18:32:12 -0600 (CST)
Received: from rztsun.rz.tu-harburg.de (rztsun.rz.tu-harburg.de [134.28.200.14])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g330W4311047
	for <reliable_computing [at] interval [dot] louisiana.edu>; Tue, 2 Apr 2002 18:32:05 -0600 (CST)
Received: from omega.ti3.tu-harburg.de (omega.ti3.tu-harburg.de [134.28.20.55])
	by rztsun.rz.tu-harburg.de (8.9.0/8.8.8) with ESMTP id CAA27963;
	Wed, 3 Apr 2002 02:32:02 +0200 (MET DST)
Received: by omega.ti3.tu-harburg.de (Postfix on SuSE eMail Server 2.0, from userid 30)
	id 2BC9A10225; Wed,  3 Apr 2002 02:31:15 +0200 (CEST)
To: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Message-ID: <1017793875.3caa4d53222ee [at] www [dot] ti3.tu-harburg.de>
Date: Wed, 03 Apr 2002 02:31:15 +0200 (CEST)
From: rump@tu-harburg.de
Cc: makino [at] uiuc [dot] edu, reliable_computing [at] interval [dot] louisiana.edu
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at>
In-Reply-To: <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: IMP/PHP IMAP webmail program 2.2.3
X-Originating-IP: 210.131.114.165
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

To Martin Berz:

Dear Martin, 

here is again Arnold's statement. You said you think it is not true. So why 
don't you write a 5-lines mail (not 50 or 500) giving a reference to a theorem 
with precisely formulated assumptions and assertions to prove the contrary.

With best regards

Siegfried



Zitiere Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>:

> 
> Against repeated claims by Berz and Makino, I want to reassert that
> Taylor models in their current implementation (even with LDB) do  
> *NOT*   
> have more than second order approximation for range enclosure, except 
> sufficiently far away from stationary points, where related monotony
> arguments 
> give the exact range (infinite order). See below my comments on Kyoko
> Makino's 
> posting.
> 
> While *high* approximation order is irrelevant in practice, *third*
> order
> is important, since, as shown by Kearfott and Du, it allows to
> eliminate
> the
> cluster effect in branch and bound methods for global optimization,
> one of the main sources of inefficiency for many problems. 
> Quadratic approximation order is not sufficient for this.
> 
> In particular, Taylor models, while reducing overestimation in many
> interesting cases, are not suitable to fight the cluster effect in
> global
> optimization.
> 
> Arnold Neumaier
> 


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 01:51:06 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g337p5k11998
	for reliable_computing-outgoing; Wed, 3 Apr 2002 01:51:05 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g337p0311994
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 01:51:00 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
	by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g337oWlY018216;
	Wed, 3 Apr 2002 09:50:36 +0200
Message-ID: <3CAAB448.C289E9C3 [at] univie [dot] ac.at>
Date: Wed, 03 Apr 2002 09:50:32 +0200
From: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-31 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: Ramon Moore <rmoore17 [at] columbus [dot] rr.com>
CC: interval <reliable_computing [at] interval [dot] louisiana.edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at> <001401c1da7d$d5201020$66ae1841 [at] columbus [dot] rr.com> <3CAA158B.5FCD8168 [at] univie [dot] ac.at> <005301c1da88$ff4369a0$66ae1841 [at] columbus [dot] rr.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Ramon Moore wrote:
> 
> Wouldn't the midpoint test limit the cluster effect unless the value of the
> objective function happens to be nearly as small as the global minimum
> value?

The cluster effect happens near all local minimizers with a function
value 
close to or below the best function value found. So if there is a unique
global minimizer, if all other local minima have much higher function
values, and a point close to global minimizer is already known then 
the cluster effect only happens near the global minimum. But the
neighborhood
in which it happens may be quite large, and while the global optimum has
not 
yet been located it will appear also at other minimizers.

Arnold

From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 01:53:38 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g337rbi12060
	for reliable_computing-outgoing; Wed, 3 Apr 2002 01:53:37 -0600 (CST)
Received: from mailbox.univie.ac.at (mailbox.univie.ac.at [131.130.1.27])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g337rU312056
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 01:53:31 -0600 (CST)
Received: from univie.ac.at (hektor.mat.univie.ac.at [131.130.16.21])
	by mailbox.univie.ac.at (8.12.2/8.12.2) with ESMTP id g337rMlY969660;
	Wed, 3 Apr 2002 09:53:24 +0200
Message-ID: <3CAAB4F2.63E31C01 [at] univie [dot] ac.at>
Date: Wed, 03 Apr 2002 09:53:22 +0200
From: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
Organization: University of Vienna
X-Mailer: Mozilla 4.78 [en] (X11; U; Linux 2.4.9-31 i686)
X-Accept-Language: en, de
MIME-Version: 1.0
To: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
CC: interval <reliable_computing [at] interval [dot] louisiana.edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
References: <2.2.32.20020402220938.009b8f60 [at] pop [dot] louisiana.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

"R. Baker Kearfott" wrote:
> 
> Our analysis was based on the algorithm with the midpoint test.  In
> fact, the problem still occurs, even if we use the exact value of
> the global optimum (rather than a value computed via the midpoint
> test.)  However, unless we made some kind of error, we only showed
> an exponential increase in the number of boxes in the list (as the
> tolerance is decreased) when the order is strictly less than 2.
> When the order is exactly two, we get, in general, more than one
> box in the list, but we didn't prove an exponential increase. 

If the order is <2, the number of boxes grows exponentially with 
an exponent that increases as the box size decreases; if the order is 2,
the number of boxes is roughly independent of the box size but is
exponential in the dimension.

Arnold

From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 02:15:25 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g338FPv12219
	for reliable_computing-outgoing; Wed, 3 Apr 2002 02:15:25 -0600 (CST)
Received: from kathmandu.sun.com (kathmandu.sun.com [192.18.98.36])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g338FJ312215
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 02:15:20 -0600 (CST)
Received: from vic.Aus.Sun.COM ([129.158.87.25])
	by kathmandu.sun.com (8.9.3+Sun/8.9.3) with ESMTP id BAA29036
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 01:15:17 -0700 (MST)
Received: from retreat (retreat [129.158.87.155])
	by vic.Aus.Sun.COM (8.10.2+Sun/8.10.2/ENSMAIL,v2.2) with SMTP id g338FFh03262
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 18:15:16 +1000 (EST)
Message-Id: <200204030815.g338FFh03262 [at] vic [dot] Aus.Sun.COM>
Date: Wed, 3 Apr 2002 18:16:08 +1000 (EST)
From: Richard Smith - Systems Engineer - Melbourne <Richard.Smith [at] Sun [dot] COM>
Reply-To: Richard Smith - Systems Engineer - Melbourne <Richard.Smith [at] Sun [dot] COM>
Subject: Nonlinear optimization with constraints
To: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: Ik2iiF9I5m+/IvAJtiADAw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc 
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

In point arithmetic I'm moderately familiar with the technique of Lagrange
multipliers to minimize a function subject to constraints. Does it make
sense to use a similar approach to finding constrained global minimizers on
the interval extension of a function, subject to a set of constraints?

At least in principle it seemed to me that one could then use techniques
for global minimization for an unconstrained problem, but maybe that's not
a good way to proceed. I could imagine for example using some branch-and-bound
approach on the original function, but throwing away boxes based on subsequent
application of the constraint set.

============================================================================
   ,-_|\   Richard Smith - SE Melbourne
  /     \  Sun Microsystems Australia         Phone : +61 3 9869 6200
richard.smith [at] Sun [dot] COM                        Direct : +61 3 9869 6224  
  \_,-._/  476 St Kilda Road                    Fax : +61 3 9869 6290
       v   Melbourne Vic 3004 Australia
===========================================================================


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 03:38:03 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g339c3c12491
	for reliable_computing-outgoing; Wed, 3 Apr 2002 03:38:03 -0600 (CST)
Received: from imf09bis.bellsouth.net (mail309.mail.bellsouth.net [205.152.58.169])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g339bw312487
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 03:37:59 -0600 (CST)
Received: from u8174 ([66.20.80.209]) by imf09bis.bellsouth.net
          (InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
          id <20020403093912.NZZG15543.imf09bis.bellsouth.net@u8174>
          for <reliable_computing [at] interval [dot] louisiana.edu>;
          Wed, 3 Apr 2002 04:39:12 -0500
Message-Id: <2.2.32.20020403093806.009dd388 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 03 Apr 2002 03:38:06 -0600
To: interval <reliable_computing [at] interval [dot] louisiana.edu>
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Arnold,

Yes, you are right.

Best regards,

Baker

At 09:53 AM 4/3/02 +0200, Arnold Neumaier wrote:
>"R. Baker Kearfott" wrote:
>> 
>> Our analysis was based on the algorithm with the midpoint test.  In
>> fact, the problem still occurs, even if we use the exact value of
>> the global optimum (rather than a value computed via the midpoint
>> test.)  However, unless we made some kind of error, we only showed
>> an exponential increase in the number of boxes in the list (as the
>> tolerance is decreased) when the order is strictly less than 2.
>> When the order is exactly two, we get, in general, more than one
>> box in the list, but we didn't prove an exponential increase. 
>
>If the order is <2, the number of boxes grows exponentially with 
>an exponent that increases as the box size decreases; if the order is 2,
>the number of boxes is roughly independent of the box size but is
>exponential in the dimension.
>
>Arnold
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 03:38:23 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g339cMI12517
	for reliable_computing-outgoing; Wed, 3 Apr 2002 03:38:22 -0600 (CST)
Received: from imf09bis.bellsouth.net (mail209.mail.bellsouth.net [205.152.58.149])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g339cD312509
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 03:38:13 -0600 (CST)
Received: from u8174 ([66.20.80.209]) by imf09bis.bellsouth.net
          (InterMail vM.5.01.04.05 201-253-122-122-105-20011231) with SMTP
          id <20020403093923.OAAU15543.imf09bis.bellsouth.net@u8174>;
          Wed, 3 Apr 2002 04:39:23 -0500
Message-Id: <2.2.32.20020403093817.009dfe34 [at] pop [dot] louisiana.edu>
X-Sender: rbk5287 [at] pop [dot] louisiana.edu
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 03 Apr 2002 03:38:17 -0600
To: Richard Smith - Systems Engineer - Melbourne <Richard.Smith [at] Sun [dot] COM>,
   reliable_computing [at] interval [dot] louisiana.edu
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: Nonlinear optimization with constraints
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Richard,

It certainly does make sense.  The first discussion of this is perhaps
in papers by your colleague Bill Walster (with Sun in Palo Alto) and
Eldon Hansen; additional explanation is found in Eldon's 1990 book.

Our GlobSol software uses Lagrange multipliers (i.e. the Fritz John
system) in certain contexts.

However, in an interval context, the constraints can also be used
in other ways.  These additional ways probably need to be exploited
to make constrained validated global optimization software competitive.
The current state of the art can probably be improved in this regard.

Best regards,

Baker

At 06:16 PM 4/3/02 +1000, Richard Smith - Systems Engineer - Melbourne wrote:
>In point arithmetic I'm moderately familiar with the technique of Lagrange
>multipliers to minimize a function subject to constraints. Does it make
>sense to use a similar approach to finding constrained global minimizers on
>the interval extension of a function, subject to a set of constraints?
>
>At least in principle it seemed to me that one could then use techniques
>for global minimization for an unconstrained problem, but maybe that's not
>a good way to proceed. I could imagine for example using some branch-and-bound
>approach on the original function, but throwing away boxes based on subsequent
>application of the constraint set.
>
>============================================================================
>   ,-_|\   Richard Smith - SE Melbourne
>  /     \  Sun Microsystems Australia         Phone : +61 3 9869 6200
>richard.smith [at] Sun [dot] COM                        Direct : +61 3 9869 6224  
>  \_,-._/  476 St Kilda Road                    Fax : +61 3 9869 6290
>       v   Melbourne Vic 3004 Australia
>===========================================================================
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 07:54:03 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g33Ds3V13343
	for reliable_computing-outgoing; Wed, 3 Apr 2002 07:54:03 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g33Drx313339
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 07:54:00 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g33DrO124195;
	Wed, 3 Apr 2002 08:53:26 -0500 (EST)
Message-ID: <007e01c1db16$b644a500$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Arnold Neumaier" <Arnold.Neumaier [at] univie [dot] ac.at>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <NEBBLGMLDAEBJEKKJNEKGEEPENAA.makino [at] uiuc [dot] edu> <3CA9FF8A.84EB0B15 [at] univie [dot] ac.at> <001401c1da7d$d5201020$66ae1841 [at] columbus [dot] rr.com> <3CAA158B.5FCD8168 [at] univie [dot] ac.at> <005301c1da88$ff4369a0$66ae1841 [at] columbus [dot] rr.com> <3CAAB448.C289E9C3 [at] univie [dot] ac.at>
Subject: clustering
Date: Wed, 3 Apr 2002 08:51:51 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Arnold and all,

I asked:
> > Wouldn't the midpoint test limit the cluster effect unless the value of
the
> > objective function happens to be nearly as small as the global minimum
> > value?

Arnold replied:
> The cluster effect happens near all local minimizers with a function
> value
> close to or below the best function value found. So if there is a unique
> global minimizer, if all other local minima have much higher function
> values, and a point close to global minimizer is already known then
> the cluster effect only happens near the global minimum.

Yes, that is what I meant in my question. How "much higher" will depend
on details of a particular example, of course.

Arnold continued:
>But the
> neighborhood
> in which it happens may be quite large,

Certainly this is true, for example, when the objective function is very
"flat" near the global minimum.

Ramon Moore


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 08:21:42 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g33ELgH13480
	for reliable_computing-outgoing; Wed, 3 Apr 2002 08:21:42 -0600 (CST)
Received: from marnier.ucs.louisiana.edu (root [at] marnier [dot] ucs.louisiana.edu [130.70.132.233])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g33ELb313476
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 08:21:37 -0600 (CST)
Received: from liberty (liberty.louisiana.edu [130.70.46.171])
	by marnier.ucs.louisiana.edu (8.11.3/8.11.3/ull-ucs-mx-host_1.6) with SMTP id g33ELac19938;
	Wed, 3 Apr 2002 08:21:36 -0600 (CST)
Message-Id: <2.2.32.20020403142947.0154f5e0 [at] 130 [dot] 70.132.231>
X-Sender: rbk5287 [at] 130 [dot] 70.132.231
X-Mailer: Windows Eudora Pro Version 2.2 (32)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 03 Apr 2002 08:29:47 -0600
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
From: "R. Baker Kearfott" <rbk [at] louisiana [dot] edu>
Subject: Re: clustering
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Yes, indeed.

GlobSol attempts to avoid the "clustering" problem for flat
(ill-conditioned) objective functions with a heuristic 
epsilon-inflation process.  Some theoretical grounding for
this process can be found in 

Kearfott, R. B., "Abstract Generalized Bisection and a Cost Bound," 
Math. Comp. 49 (179), pp. 187--202, July, 1987

We considered the clustering problem when the function has interval
uncertainty in it, and we developed corresponding heuristics in

Kearfott, R. B. and Walster, G. W., "On Stopping Criteria in 
Verified Nonlinear Systems or Optimization Algorithms," ACM Trans. 
Math. Software 26(3), pp. 373--389, September, 2000.

A preprint of the latter is available from the page

http://interval.louisiana.edu/preprints.html

The case of interval uncertainty must be handled differently 
(perhaps with such a heuristic), since the asymptotic properties
of neither the interval Newton methods nor high-order extensions
do not hold after the boxes become relatively small.

Best regards,

Baker


At 08:51 AM 4/3/02 -0500, Ramon Moore wrote:
>Dear Arnold and all,
>
>I asked:
>> > Wouldn't the midpoint test limit the cluster effect unless the value of
>the
>> > objective function happens to be nearly as small as the global minimum
>> > value?
>
>Arnold replied:
>> The cluster effect happens near all local minimizers with a function
>> value
>> close to or below the best function value found. So if there is a unique
>> global minimizer, if all other local minima have much higher function
>> values, and a point close to global minimizer is already known then
>> the cluster effect only happens near the global minimum.
>
>Yes, that is what I meant in my question. How "much higher" will depend
>on details of a particular example, of course.
>
>Arnold continued:
>>But the
>> neighborhood
>> in which it happens may be quite large,
>
>Certainly this is true, for example, when the objective function is very
>"flat" near the global minimum.
>
>Ramon Moore
>
>
---------------------------------------------------------------
R. Baker Kearfott,    rbk [at] louisiana [dot] edu   (337) 482-5346 (fax)
(337) 482-5270 (work)                     (337) 981-9744 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 10:40:49 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g33Genq13821
	for reliable_computing-outgoing; Wed, 3 Apr 2002 10:40:49 -0600 (CST)
Received: from mercury.Sun.COM (mercury.Sun.COM [192.9.25.1])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g33Gei313817
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 10:40:44 -0600 (CST)
Received: from engmail2.Eng.Sun.COM ([129.146.1.25])
	by mercury.Sun.COM (8.9.3+Sun/8.9.3) with ESMTP id IAA04476
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 08:40:42 -0800 (PST)
Received: from phys-mpkmaila (phys-mpkmaila.Eng.Sun.COM [129.146.18.131])
	by engmail2.Eng.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v2.1p1) with ESMTP id IAA09996;
	Wed, 3 Apr 2002 08:40:41 -0800 (PST)
Received: from gww (gww.Eng.Sun.COM [129.146.78.116])
 by mpkmail.eng.sun.com (iPlanet Messaging Server 5.2 (built Jan 13 2002))
 with SMTP id <0GU000BQM3PD92 [at] mpkmail [dot] eng.sun.com>; Wed,
 03 Apr 2002 08:41:37 -0800 (PST)
Date: Wed, 03 Apr 2002 08:40:40 -0800 (PST)
From: William Walster <Bill.Walster [at] Eng [dot] Sun.COM>
Subject: Re: Nonlinear optimization with constraints
To: reliable_computing [at] interval [dot] louisiana.edu, Richard.Smith [at] sun [dot] com
Reply-to: William Walster <Bill.Walster [at] Eng [dot] Sun.COM>
Message-id: <0GU000BQN3PD92 [at] mpkmail [dot] eng.sun.com>
MIME-version: 1.0
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4.2 SunOS 5.8 sun4u sparc
Content-type: TEXT/plain; charset=us-ascii
Content-transfer-encoding: 7BIT
Content-MD5: p1aqB6Y0aZejnjLgltfWFA==
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk


  >Date: Wed, 03 Apr 2002 18:16:08 +1000 (EST)
  >From: Richard Smith - Systems Engineer - Melbourne <Richard.Smith [at] sun [dot] com>
  >Subject: Nonlinear optimization with constraints
  >To: reliable_computing [at] interval [dot] louisiana.edu
  >MIME-version: 1.0
  >Content-MD5: Ik2iiF9I5m+/IvAJtiADAw==
  >
  >In point arithmetic I'm moderately familiar with the technique of Lagrange
  >multipliers to minimize a function subject to constraints. Does it make
  >sense to use a similar approach to finding constrained global minimizers on
  >the interval extension of a function, subject to a set of constraints?
  
Yes.  In fact we do exactly that on linearizations of the nonlinear 
objective and constraint equations.  We form the set of linear 
equations called the John Conditions.

The trick is that these linear equations are interval *bounds* on the
nonlinear functions on which they are based.  Therefore, we use 
these equations as constraints with which to delete parts of given
boxes that cannot contain the global minimum within the feasible region
defined by the constraints.

The tricky part is when there are equality constraints that must 
be satisfied.  In this case we must prove there is a feasible point 
within a small box in the neighborhood of a point that satisfies the
equality constraint.

All this is documented in Eldon Hansen's book "Global Optimization
Using Interval Analysis".  We will soon be publishing a second
edition that contains many new algorithms and features.

  >
  >At least in principle it seemed to me that one could then use techniques
  >for global minimization for an unconstrained problem, but maybe that's not
  >a good way to proceed. I could imagine for example using some 
branch-and-bound
  >approach on the original function, but throwing away boxes based on 
subsequent
  >application of the constraint set.
  
Exactly right.  Constraints help us, as they give us tools with which
to delete sub-boxes that cannot contain the solution.

Cheers,

Bill

  >
  >============================================================================
  >   ,-_|\   Richard Smith - SE Melbourne
  >  /     \  Sun Microsystems Australia         Phone : +61 3 9869 6200
  >richard.smith [at] Sun [dot] COM                        Direct : +61 3 9869 6224  
  >  \_,-._/  476 St Kilda Road                    Fax : +61 3 9869 6290
  >       v   Melbourne Vic 3004 Australia
  >===========================================================================
  >


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 18:04:14 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g3404E714667
	for reliable_computing-outgoing; Wed, 3 Apr 2002 18:04:14 -0600 (CST)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g34049314663
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 18:04:09 -0600 (CST)
Received: from aragorn (aragorn [129.108.5.35])
	by cs.utep.edu (8.11.3/8.11.3) with SMTP id g3403QR28168;
	Wed, 3 Apr 2002 17:03:26 -0700 (MST)
Message-Id: <200204040003.g3403QR28168 [at] cs [dot] utep.edu>
Date: Wed, 3 Apr 2002 17:03:25 -0700 (MST)
From: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Reply-To: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Subject: Re: Taylor models do *NOT* give high order range enclosures
To: makino [at] uiuc [dot] edu, Arnold.Neumaier [at] univie [dot] ac.at
Cc: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: yQhcWPazGPyb2L7KztyOVw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc 
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Maybe I can somewhat reconciliate the positions by citing my own paper that 
states that the problem of estimating theb range with cubic accuracy is 
NP-hard. This means that

* on one hand, Arnold is right, Taylor's methods do not estimate the range with 
cubic accuracy;

* on the other hand, this fact does not in any way discredit Taylor methods, 
because (unless P=NP) no feasible algorithm can do that.  

This paper started from similar mailing-list discussions that Arnold and Martin 
had in 1999. 

I have a revised version somewhere, but I could not find it easily, so I am 
sending a link to the not-perfect version (sorry): 
http://www.cs.utep.edu/vladik/1999/tr99-45.ps.gz
It is in gzipped PostScript. 

Vladik

> Date: Tue, 02 Apr 2002 20:59:22 +0200
> From: Arnold Neumaier <Arnold.Neumaier [at] univie [dot] ac.at>
> X-Accept-Language: en, de
> MIME-Version: 1.0
> To: makino [at] uiuc [dot] edu
> CC: reliable_computing [at] interval [dot] louisiana.edu
> Subject: Taylor models do *NOT* give high order range enclosures
> Content-Transfer-Encoding: 7bit
> 
> 
> Against repeated claims by Berz and Makino, I want to reassert that
> Taylor models in their current implementation (even with LDB) do  
> *NOT*   
> have more than second order approximation for range enclosure, except 
> sufficiently far away from stationary points, where related monotony
> arguments 
> give the exact range (infinite order). See below my comments on Kyoko
> Makino's 
> posting.
> 
> While *high* approximation order is irrelevant in practice, *third*
> order
> is important, since, as shown by Kearfott and Du, it allows to eliminate
> the
> cluster effect in branch and bound methods for global optimization,
> one of the main sources of inefficiency for many problems. 
> Quadratic approximation order is not sufficient for this.
> 
> In particular, Taylor models, while reducing overestimation in many
> interesting cases, are not suitable to fight the cluster effect in
> global
> optimization.
> 
> Arnold Neumaier
> 
> 
> 
> =========================
> 
> Kyoko Makino wrote:
> 
> > 2. Regarding superconvergence, we studied Gritton's problem using Taylor 
models
> > with the linear dominating range bounder outlined in my dissertation (in 
the
> > following, denoted LDB), which uses the fact that as the domains get 
smaller and
> > smaller, the lowest orders are more and more dominant. 
> 
> > 3. The algorithm of the linear dominated range bounder on the box [-h,h]^d 
is very
> > simple: Obtain an initial bound B1 of the linear part L= sum_{j=1}^d cj xj
> > (scales with h) and one of the higher order parts B2 (scales with h^2). In 
each
> > direction xj, the maximizing point cannot occur more than B2/cj away from 
the
> > maximizing point of the linear part L, which if cj is assumed positive 
reduces
> > the box to [ max(-h,h-B2/cj) , h ]. Recenter in the new box and iterate 
until the
> > box size stabilizes.
> > 
> > Of course for a large B2, there may not be much or not any reduction in box 
size;
> > but as h goes to 0, since B2 ~ h^2, and since the linear parts in any new 
boxes will
> > eventually not differ by more than say a factor of 2 from cj, there will 
eventually
> > be convergence to one of the boxes. In practice, the convergence happens in 
a few to
> > several iterations. At that time, the corner point has been shown to be the 
actual
> > maximizing point; and of course combined with the Taylor remainder bound 
which
> > scales with order (n+1), we thus have order (n+1) convergence.
> 
> In this situation, the problem is in fact monotone, and using a
> bicentered form
> (as in my book p.59) with gradient computed by a Taylor form (to benefit
> from the
> cancellation effect), one even gets the exact range - infinite order. 
> High order statements are therefore in this case not meaningful.
> (But it suggests that it may be worth doing monotonicity tests using
> Taylor forms.)
> 
> The correct test case for higher order than 2 is close to stationary
> points 
> since there branch and bound methods of order 2 only suffer from the
> cluster effect
> (as shown by Kearfott and Du). But precisely in this case where it would
> be most 
> needed, Taylor models with LDB  *FAIL*  to show the higher order.
> 
> > 4. As pointed out by Baker, the numerically (but not scientifically) more
> > interesting region of the Gritton function is [1,2], and things are 
particularly
> > critical around 1.4. We repeat the calculation around the point 1.4, but 
for the
> > purpose of comparison, we also show the overestimations of the interval 
evaluation,
> > evaluation using the centered form (CF) and mean value form (MVF) as 
described
> > in many books, including Moore's 1979 book.
> 
> Actually, for optimization, things are particularly critical around
> 1.419332885742, 
> which is a local minimizer. And if you center your intervals around this
> point
> or a closeby point for which the minimizer is within the box, your
> method will only 
> show second order convergence. Thus it is inadmissible to claim that
> 
> > d) Again, indeed the Taylor method is superconvergent with order (n+1).


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 19:31:57 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g341VvF14916
	for reliable_computing-outgoing; Wed, 3 Apr 2002 19:31:57 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g341Vq314912
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 19:31:52 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g341Vm105881;
	Wed, 3 Apr 2002 20:31:49 -0500 (EST)
Message-ID: <000c01c1db78$3f323ce0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Vladik Kreinovich" <vladik [at] cs [dot] utep.edu>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <200204040003.g3403QR28168 [at] cs [dot] utep.edu>
Subject: NP-hard for what class of problems?
Date: Wed, 3 Apr 2002 20:30:02 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Vladik,

To what class of problems does your paper apply exactly? I am unable to open
the link to your paper. Certainly for some kinds of functions, for example
monotonic ones, we can even find the exact range of values.

Ramon Moore

Vladik wrote:

> Maybe I can somewhat reconciliate the positions by citing my own paper
that
> states that the problem of estimating theb range with cubic accuracy is
> NP-hard. This means that
>
> * on one hand, Arnold is right, Taylor's methods do not estimate the range
with
> cubic accuracy;
>
> * on the other hand, this fact does not in any way discredit Taylor
methods,
> because (unless P=NP) no feasible algorithm can do that.
>
> This paper started from similar mailing-list discussions that Arnold and
Martin
> had in 1999.
>
> I have a revised version somewhere, but I could not find it easily, so I
am
> sending a link to the not-perfect version (sorry):
> http://www.cs.utep.edu/vladik/1999/tr99-45.ps.gz
> It is in gzipped PostScript.
>
> Vladik



From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 19:41:07 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g341f6e15026
	for reliable_computing-outgoing; Wed, 3 Apr 2002 19:41:06 -0600 (CST)
Received: from cs.utep.edu (mail.cs.utep.edu [129.108.5.3])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g341f2315022
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 19:41:02 -0600 (CST)
Received: from aragorn (aragorn [129.108.5.35])
	by cs.utep.edu (8.11.3/8.11.3) with SMTP id g341et428962;
	Wed, 3 Apr 2002 18:40:55 -0700 (MST)
Message-Id: <200204040140.g341et428962 [at] cs [dot] utep.edu>
Date: Wed, 3 Apr 2002 18:40:54 -0700 (MST)
From: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Reply-To: Vladik Kreinovich <vladik [at] cs [dot] utep.edu>
Subject: Re: NP-hard for what class of problems?
To: vladik [at] cs [dot] utep.edu, rmoore17 [at] columbus [dot] rr.com
Cc: reliable_computing [at] interval [dot] louisiana.edu
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: sVMA/BiFd7WIgXdFgUO1fw==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc 
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Dear Ray, Thanks for the prompt reply.


NP-hard means, crudely speaking, that there is no algorithm that would solve 
all particular case of this problem in feasiable time. 

The fact that a problem is NP-hard does not mean that we cannot solve some 
particular cases of this problem in reasonable time. 

For example, the general problem of computing the range of a polynomial 
function is NP-hard, but - as you correctly mention - there are many particular 
cases when this problem is easily solvable. 

Similarly, historically the first example of NP-hardness, propositional 
satisfiability problem - given a propositional formula check if it is possible 
to make it true by some substitution of "true" and "false" into variables - has 
many paryicular classes for which a feasible algorithm exists. 

When the problem is NP-hard it DOES NOT mean that all paryicular cases of this 
problem are hard, it rather means that SOME cases are hard. 

Same thing with Taylor methods. Of course, there are many cases when these 
methods lead to good estimates, the argument is whether this is true for all 
cases (as Martin says) or not for all (as Arnold thinks). 

I hope this clarifies the issue. 

Vladik

P.S. I am sorry to hear that you could not open the file. I will try to put a 
pdf version on the website, will it help? 

> From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
> To: "Vladik Kreinovich" <vladik [at] cs [dot] utep.edu>
> Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
> Subject: NP-hard for what class of problems?
> Date: Wed, 3 Apr 2002 20:30:02 -0500
> MIME-Version: 1.0
> Content-Transfer-Encoding: 7bit
> X-Priority: 3
> X-MSMail-Priority: Normal
> X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
> 
> Dear Vladik,
> 
> To what class of problems does your paper apply exactly? I am unable to open
> the link to your paper. Certainly for some kinds of functions, for example
> monotonic ones, we can even find the exact range of values.
> 
> Ramon Moore
> 
> Vladik wrote:
> 
> > Maybe I can somewhat reconciliate the positions by citing my own paper
> that
> > states that the problem of estimating theb range with cubic accuracy is
> > NP-hard. This means that
> >
> > * on one hand, Arnold is right, Taylor's methods do not estimate the range
> with
> > cubic accuracy;
> >
> > * on the other hand, this fact does not in any way discredit Taylor
> methods,
> > because (unless P=NP) no feasible algorithm can do that.
> >
> > This paper started from similar mailing-list discussions that Arnold and
> Martin
> > had in 1999.
> >
> > I have a revised version somewhere, but I could not find it easily, so I
> am
> > sending a link to the not-perfect version (sorry):
> > http://www.cs.utep.edu/vladik/1999/tr99-45.ps.gz
> > It is in gzipped PostScript.
> >
> > Vladik
> 


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 19:50:40 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g341od415139
	for reliable_computing-outgoing; Wed, 3 Apr 2002 19:50:39 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g341oY315135
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 19:50:35 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g341oW103382;
	Wed, 3 Apr 2002 20:50:32 -0500 (EST)
Message-ID: <001401c1db7a$db72a020$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Vladik Kreinovich" <vladik [at] cs [dot] utep.edu>
Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
References: <200204040140.g341et428962 [at] cs [dot] utep.edu>
Subject: Re: NP-hard for what class of problems?
Date: Wed, 3 Apr 2002 20:48:45 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Thanks, Vladik. However, I do not believe that Martin ever said "for all
cases". Please correct me if I am wrong about that, Martin.

Ray Moore
----- Original Message -----
From: "Vladik Kreinovich" <vladik [at] cs [dot] utep.edu>
To: <vladik [at] cs [dot] utep.edu>; <rmoore17 [at] columbus [dot] rr.com>
Cc: <reliable_computing [at] interval [dot] louisiana.edu>
Sent: Wednesday, April 03, 2002 8:40 PM
Subject: Re: NP-hard for what class of problems?


> Dear Ray, Thanks for the prompt reply.
>
>
> NP-hard means, crudely speaking, that there is no algorithm that would
solve
> all particular case of this problem in feasiable time.
>
> The fact that a problem is NP-hard does not mean that we cannot solve some
> particular cases of this problem in reasonable time.
>
> For example, the general problem of computing the range of a polynomial
> function is NP-hard, but - as you correctly mention - there are many
particular
> cases when this problem is easily solvable.
>
> Similarly, historically the first example of NP-hardness, propositional
> satisfiability problem - given a propositional formula check if it is
possible
> to make it true by some substitution of "true" and "false" into
variables - has
> many paryicular classes for which a feasible algorithm exists.
>
> When the problem is NP-hard it DOES NOT mean that all paryicular cases of
this
> problem are hard, it rather means that SOME cases are hard.
>
> Same thing with Taylor methods. Of course, there are many cases when these
> methods lead to good estimates, the argument is whether this is true for
all
> cases (as Martin says) or not for all (as Arnold thinks).
>
> I hope this clarifies the issue.
>
> Vladik
>
> P.S. I am sorry to hear that you could not open the file. I will try to
put a
> pdf version on the website, will it help?
>
> > From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
> > To: "Vladik Kreinovich" <vladik [at] cs [dot] utep.edu>
> > Cc: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
> > Subject: NP-hard for what class of problems?
> > Date: Wed, 3 Apr 2002 20:30:02 -0500
> > MIME-Version: 1.0
> > Content-Transfer-Encoding: 7bit
> > X-Priority: 3
> > X-MSMail-Priority: Normal
> > X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
> >
> > Dear Vladik,
> >
> > To what class of problems does your paper apply exactly? I am unable to
open
> > the link to your paper. Certainly for some kinds of functions, for
example
> > monotonic ones, we can even find the exact range of values.
> >
> > Ramon Moore
> >
> > Vladik wrote:
> >
> > > Maybe I can somewhat reconciliate the positions by citing my own paper
> > that
> > > states that the problem of estimating theb range with cubic accuracy
is
> > > NP-hard. This means that
> > >
> > > * on one hand, Arnold is right, Taylor's methods do not estimate the
range
> > with
> > > cubic accuracy;
> > >
> > > * on the other hand, this fact does not in any way discredit Taylor
> > methods,
> > > because (unless P=NP) no feasible algorithm can do that.
> > >
> > > This paper started from similar mailing-list discussions that Arnold
and
> > Martin
> > > had in 1999.
> > >
> > > I have a revised version somewhere, but I could not find it easily, so
I
> > am
> > > sending a link to the not-perfect version (sorry):
> > > http://www.cs.utep.edu/vladik/1999/tr99-45.ps.gz
> > > It is in gzipped PostScript.
> > >
> > > Vladik
> >
>


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 19:53:02 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g341r1i15245
	for reliable_computing-outgoing; Wed, 3 Apr 2002 19:53:02 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g341qs315241
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 19:52:54 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g341qr106826
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 20:52:53 -0500 (EST)
Message-ID: <003501c1db7b$2e9a2980$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
Subject: Fw: NP-hard for what class of problems?
Date: Wed, 3 Apr 2002 20:51:04 -0500
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

Here is another version of Vladik's file.
----- Original Message -----
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "Richard Smith - Systems Engineer - Melbourne" <Richard.Smith [at] Sun [dot] COM>
Sent: Wednesday, April 03, 2002 8:50 PM
Subject: Re: NP-hard for what class of problems?


> Thanks, Richard.
>
> Ray Moore
> ----- Original Message -----
> From: "Richard Smith - Systems Engineer - Melbourne"
<Richard.Smith [at] Sun [dot] COM>
> To: <rmoore17 [at] columbus [dot] rr.com>
> Sent: Wednesday, April 03, 2002 8:41 PM
> Subject: Re: NP-hard for what class of problems?
>
>
> > Attached is the [uncompressed] postscript version.
> >
> >
>
============================================================================
> >    ,-_|\   Richard Smith - SE Melbourne
> >   /     \  Sun Microsystems Australia         Phone : +61 3 9869 6200
> > richard.smith [at] Sun [dot] COM                        Direct : +61 3 9869 6224
> >   \_,-._/  476 St Kilda Road                    Fax : +61 3 9869 6290
> >        v   Melbourne Vic 3004 Australia
> >
>
===========================================================================
> >
>


From owner-reliable_computing [at] interval [dot] louisiana.edu Wed Apr  3 20:03:05 2002
Received: (from daemon@localhost)
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) id g34234Z15385
	for reliable_computing-outgoing; Wed, 3 Apr 2002 20:03:04 -0600 (CST)
Received: from clmboh1-smtp3.columbus.rr.com (clmboh1-smtp3.columbus.rr.com [65.24.0.112])
	by interval.louisiana.edu (8.11.3/8.11.3/ull-interval-math-majordomo-1.2) with ESMTP id g3422u315381
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 20:02:56 -0600 (CST)
Received: from oemcomputer (dhcp065-024-174-102.columbus.rr.com [65.24.174.102])
	by clmboh1-smtp3.columbus.rr.com (8.11.2/8.11.2) with SMTP id g3422l122243
	for <reliable_computing [at] interval [dot] louisiana.edu>; Wed, 3 Apr 2002 21:02:47 -0500 (EST)
Message-ID: <005d01c1db7c$90135be0$66ae1841 [at] columbus [dot] rr.com>
From: "Ramon Moore" <rmoore17 [at] columbus [dot] rr.com>
To: "interval" <reliable_computing [at] interval [dot] louisiana.edu>
Subject: Fw: NP-hard for what class of problems?
Date: Wed, 3 Apr 2002 21:00:55 -0500
MIME-Version: 1.0
Content-Type: multipart/mixed;
	boundary="----=_NextPart_000_005A_01C1DB52.A5B3A6A0"
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: owner-reliable_computing [at] interval [dot] louisiana.edu
Precedence: bulk

This is a multi-part message in MIME format.

------=_NextPart_000_005A_01C1DB52.A5B3A6A0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

I left off the attached file, sorry.
----- Original Message -----
From: "Richard Smith - Systems Engineer - Melbourne" <Richard.Smith [at] Sun [dot] COM>
To: <rmoore17 [at] columbus [dot] rr.com>
Sent: Wednesday, April 03, 2002 8:41 PM
Subject: Re: NP-hard for what class of problems?


> Attached is the [uncompressed] postscript version.
>
>
============================================================================
>    ,-_|\   Richard Smith - SE Melbourne
>   /     \  Sun Microsystems Australia         Phone : +61 3 9869 6200
> richard.smith [at] Sun [dot] COM                        Direct : +61 3 9869 6224
>   \_,-._/  476 St Kilda Road                    Fax : +61 3 9869 6290
>        v   Melbourne Vic 3004 Australia
>
===========================================================================
>

------=_NextPart_000_005A_01C1DB52.A5B3A6A0
Content-Type: application/postscript;
	name="tr99-45.ps"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="tr99-45.ps"

%!PS-Adobe-2.0=0A=
%%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software=0A=
%%Title: tr99-45.dvi=0A=
%%Pages: 10=0A=
%%PageOrder: Ascend=0A=
%%BoundingBox: 0 0 612 792=0A=
%%DocumentPaperSizes: Letter=0A=
%%EndComments=0A=
%DVIPSCommandLine: dvips -o blo.ps tr99-45=0A=
%DVIPSParameters: dpi=3D600, comments removed=0A=
%DVIPSSource:  TeX output 1999.11.27:1530=0A=
%%BeginProcSet: tex.pro=0A=
/TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N=0A=
/X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72=0A=
mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1}=0A=
ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale=0A=
isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div=0A=
hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul=0A=
TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if}=0A=
forall round exch round exch]setmatrix}N /@landscape{/isls true N}B=0A=
/@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B=0A=
/FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{=0A=
/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N=0A=
string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N=0A=
end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{=0A=
/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]=0A=
N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup=0A=
length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{=0A=
128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub=0A=
get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data=0A=
dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N=0A=
/rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup=0A=
/base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx=0A=
0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff=0A=
setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff=0A=
.1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}=0A=
if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup=0A=
length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{=0A=
cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin=0A=
0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul=0A=
add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict=0A=
/eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook=0A=
known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X=0A=
/IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for=0A=
65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0=0A=
0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V=0A=
{}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7=0A=
getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}=0A=
ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false=0A=
RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1=0A=
false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform=0A=
round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg=0A=
rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail=0A=
{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}=0A=
B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{=0A=
4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{=0A=
p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p=0A=
a}B /bos{/SS save N}B /eos{SS restore}B end=0A=
%%EndProcSet=0A=
TeXDict begin 40258431 52099146 1000 600 600 (tr99-45.dvi)=0A=
@start /Fa 1 1 df<FFFFFFFFFEFFFFFFFFFEFFFFFFFFFE27037A8F34>0=0A=
D E /Fb 5 102 df<F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0=0A=
F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0043674811C>12=0A=
D<FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF80FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC0000=0A=
00FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FFFFFF=0A=
80FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF8019F86A8230>34=0A=
D<FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F=0A=
8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F80FFFFFF=0A=
80FFFFFF80FFFFFF80FFFFFF80FFFFFF80FFFFFF8019F8808230>I<FFFFFFFFFFFFFFFF=0A=
FFFFFFFFE000FFFFFFFFFFFFFFFFFFFFFFFFF000FFFFFFFFFFFFFFFFFFFFFFFFF000FFFF=0A=
FFFFFFFFFFFFFFFFFFFFF000FFFFFFFFFFFFFFFFFFFFFFFFF8007FFF00000000000000FF=0A=
FFFFF8007FFF0000000000000000FFFFFC003FFF800000000000000007FFFC001FFFC000=0A=
00000000000000FFFE000FFFE000000000000000001FFE000FFFE0000000000000000007=0A=
FE0007FFF0000000000000000001FF0003FFF80000000000000000007F0001FFFC000000=0A=
0000000000003F8001FFFC0000000000000000000F8000FFFE0000000000000000000780=0A=
007FFF00000000000000000003C0003FFF80000000000000000001C0003FFF8000000000=0A=
0000000000E0001FFFC0000000000000000000E0000FFFE0000000000000000000700007=0A=
FFE0000000000000000000300007FFF0000000000000000000300003FFF8000000000000=0A=
000000180001FFFC000000000000000000000000FFFC000000000000000000000000FFFE=0A=
0000000000000000000000007FFF0000000000000000000000003FFF8000000000000000=0A=
000000003FFF8000000000000000000000001FFFC000000000000000000000000FFFE000=0A=
0000000000000000000007FFF0000000000000000000000007FFF0000000000000000000=0A=
000003FFF8000000000000000000000001FFFC000000000000000000000000FFFE000000=0A=
000000000000000000FFFE0000000000000000000000007FFF0000000000000000000000=0A=
003FFF8000000000000000000000001FFFC000000000000000000000001FFFC000000000=0A=
000000000000000FFFE0000000000000000000000007FFF0000000000000000000000003=0A=
FFF0000000000000000000000003FFF8000000000000000000000001FFFC000000000000=0A=
000000000000FFFE0000000000000000000000007FFE0000000000000000000000007FFF=0A=
0000000000000000000000003FFF8000000000000000000000001FFFC000000000000000=0A=
000000000FFFC000000000000000000000000FFFE0000000000000000000000007FFF000=0A=
0000000000000000000003FFF8000000000000000000000003FFF8000000000000000000=0A=
000001FFFC000000000000000000000000FFFC0000000000000000000000007FF8000000=0A=
0000000000000000007FF00000000000000000000000003FF00000000000000000000000=0A=
001FE00000000000000000000000001FC00000000000000000000000003F800000000000=0A=
000000000000007F00000000000000000000000000FE00000000000000000000000000FE=0A=
00000000000000000000000001FC00000000000000000000000003F80000000000000000=0A=
0000000007F00000000000000000000000000FE00000000000000000000000001FC00000=0A=
000000000000000000001F800000000000000000000000003F8000000000000000000000=0A=
00007F00000000000000000000000000FE00000000000000000000000001FC0000000000=0A=
0000000000000003F800000000000000000000000007F000000000000000000000000007=0A=
F00000000000000000000000000FE00000000000000000000000001FC000000000000000=0A=
00000000003F800000000000000000000000007F00000000000000000000000000FE0000=0A=
0000000000000000000000FE00000000000000000000000001FC00000000000000000000=0A=
000003F800000000000000000000000007F00000000000000000001800000FE000000000=0A=
00000000003000001FC00000000000000000003000001F80000000000000000000700000=0A=
3F800000000000000000006000007F00000000000000000000E00000FE00000000000000=0A=
000001E00001FC00000000000000000003C00003F800000000000000000007C00007F000=0A=
00000000000000000F800007F00000000000000000001F80000FE0000000000000000000=0A=
7F80001FC0000000000000000000FF00003F80000000000000000003FF00007F00000000=0A=
00000000000FFF0000FE0000000000000000007FFE0000FE000000000000000003FFFE