Typical and non-typical IA applications
Ian McIntosh wrote in ''requiring hardware is futile'':
As an IA newbee, I'd appreciate (off list is ok) pointers to descriptions
(preferably online) of typical and non-typical IA application usage and
needs.
There are some earlier contributions on these topics to the stds-1788
list (by Baker Kearfott, myself, Jean-Pierre Merlet, and Nate Hayes).
Posing a corresponding query to the reliable computing mailing list
produced in the preceding week a number of responses.
The attachment contains all these contributions, though I condensed
some responses to the essentials.
Arnold Neumaier
Typical and non-typical IA applications
---------------------------------------
=====================================================================
[the following was sent to the stds-1788 list on Nov. 26]
=====================================================================
[Kearfott]
If we are looking towards successful applications driving the
standardization process, we should perhaps look at global optimization,
software for handling systems of constraints, and applications
in robotics.
[Neumaier]
Interval arithmetic is part of all global optimization solvers
which are based upon the branch and bound principle, and of all
solvers for constraint satisfaction solvers with continuous constraints.
In particular, it is part of the software package BARON for
global optimization, for which the creators, Nick Sahinidis and
Mohit Tawarmalani, obtained the prestigious
2006 Beale-Orchard-Hays Prize of the Mathematical Programming Society.
http://www.mathprog.org/prz/citations/boh_2006.htm
BARON is the best global optimization package around that solves
constrained global optimization problems. it can be tried online
via the NEOS server at
http://www-neos.mcs.anl.gov/neos/solvers/go:BARON/GAMS.html
Since range problems are global optimization problems, all problems
tackled by interval methods will sooner or later be seen as global
optimization problems, and will use the techniques provided there.
Therefore if the standard caters for global optimization in the best
possible way for global optimization, it will benefit all applications
of interval arithmetic, whether present or future.
[Merlet]
We have had success in some domains. Baker mentions robotics and as I
am working also in this field I can say that in this domain this is a
recognized method. But we must be humble: for sure we have been able
to solve problems without solution up to now but at the same time some
other problems are still too difficult for us and we cannot always
compete with some other tough opponents, such as algebraic geometry.
We may just hope (and work for) that interval analysis will become
part of the classical "arsenal" that is considered when end-users are
confronted to a numerical problem, especially when guarantees on the
result have to be provided.
[Hayes]
Don't forget computer graphics!
We aren't in production yet, but we have already solved problems out
of reach of traditional methods.
Unfortunately the main reason we aren't in production now is due to
speed. So that is something I'm counting on the 1788 group to help with.
My company is developing commercial products based on interval
arithmetic, so we hope to see this new interval standard become a
success. All of our infrastructure is modal intervals, even though we
use a mixture of set-theoretical and modal interval approaches.
So I think this is a testimony to the flexibility of modal intervals:
they provide great "backwards" compatibility with practical and
traditional approaches while at the same time they give us an advanced
and formal framework to solve problems that the traditional approaches
don't do too well at.
In my profiling, what I've been able to do is count machine
instructions when rendering a large scene. The data shows as much as
50% of the executed machine instructions are due exclusively to the
modal interval multiplication and division operators.
As we continue to fine-tune the software, this percentage count
continues to rise. For example, as we continue to improve the
higher-level algorithms and eliminate bottlenecks that are not due
specifically to interval computations (or result in wasted interval
computations), the ultimate barrier to speed is the emulation of the
interval multiplication and division operators.
In some cases the speed of our software currently outperforms
competing products such as Mental Ray or RenderMan. However, in other
circumstances there are just so many arithmetic operations that the
software emulation piles up and we end up being slower.
[Stadtherr]
There are links to some "typical" applications from my group at
http://www.nd.edu/~markst/publications.html
Items 2, 9 and 22 on this list highlight some of the applications.
[Pinter]
Corliss, G.F., and Kearfott, R.B. (1999)
Rigorous global search: Industrial applications.
pp. 1-16 in: Csendes, T., ed.
Developments in Reliable Computing,
Kluwer Academic, Dordrecht.
[Kearfott]
http://www.cs.utep.edu/interval-comp/scan08kearfott.pdf
The original has pointers to other talks (and abstracts)
in the SCAN 2008 conference.
http://www.cs.utep.edu/interval-comp/scan08kearfott.pdf
{This should be replaced by a link to the improved slides given
in the attachment to Kearfott's mail]
[Moore]
Vladik's interval page
http://www.cs.utep.edu/interval-comp/icpersons.html
gives links to persons working in many areas of application.
[Titus]
Interval analysis has been applied to product design - the early
stages of product design are characterized by uncertainty and
ambiguity, which can be handled by interval methods - this is a recent
application. It is also applied in concurrent engineering, where
multiple stakeholders are involved in collaborative design of
products.
There is a design paradigm called set-based design developed by Ward
et al.(Quantitiave Inference in a mechanical design "compiler") that
also uses interval methods. Ward and his collaborators discovered that
something analogous to set-based design is being used at Toyota.
[Hu]
Thanks for mention our recent work on applying interval computing in
computational finance and economics at SCAN 2008. Here are some of the
results published (or accepted for publication) recently.
1. L. T. He, C. Hu, M. Casey, Prediction of Variability in Mortgage
Rates: Interval-Computing Solutions, , J. Risk Finance, accepted for
publication.
2. L. T. He, C. Hu, Impacts of Interval Computing on Stock Market
Variability Forecasting, J. Computational Economics, online available
at http://dx.doi.org/10.1007/s10614-008-9159-x, in printing.
3. L. T. He, C. Hu, Midpoint Method and Accuracy of Variability
Forecasting, J. Empirical Economics, accepted for publication.
4. D. Collins, C. Hu, Studying Interval Valued Matrix Games with Fuzzy
Logic, DOI 10.1007/s00500-007-0207-6, J. Soft Computing, 12(2), 147-155,
2008
5. A. Han, X. Chen, C. Hu, S. Xu, Interval Computing in Econometrics,
J. Management Review, in Chinese, Vol. 20, No. 5, pp. 37-43, 2008
6. L. T. He, C. Hu, Impacts of Interval Measurement on Studies of
Economic Variability: Evidence from Stock Market Variability
Forecasting, DOI: 10.1108/15265940710834771, J. Risk Finance, 8(5),
489-507, 2007.
[Jansson]
there is survey written by Arnold Neumaier
A. Neumaier,
Complete Search in Continuous Global Optimization and Constraint
Satisfaction,
pp. 271-369 in: Acta Numerica 2004 (A. Iserles, ed.),
Cambridge University Press 2004.
This survey covers the state of the art of techniques for solving
general purpose constrained global optimization problems and continuous
constraint satisfaction problems, with emphasis on complete techniques
that provably find all solutions. Sections on interval arithmetic,
constrained propagation and local optimization of important problem
transformations follows, in particular of linear, convex, and semilinear
(= mixed integer linear) relaxations that are important for handling
larger problems.
In practice, a user needs a reliable and robust software that works
(in most cases) also for larger problems. In the paper
A. Neumaier, O. Shcherbina, W. Huyer and T. Vinko,
A comparison of complete global optimization solvers,
Math. Programming B 103 (2005), 335-356.
results are reported of testing a number of existing state of the art
solvers for global constrained optimization and constraint
satisfaction on a set of over 1000 test problems in up to 1000
variables, collected from the literature. The solver are BARON,
COCOS, GlobSol, ICOS, LGO/GAMS, LINGO, OQNLP PremiumSolver, and for
comparison the local solver MINOS). Two of them are interval solvers
(GlobSol, ICOS). The other solvers do not provide rigorous results.
Recently, Christian Keil has written
A Comparison of Software Packages for Verified Linear Programming
http://www.ti3.tu-harburg.de/
where only solver are compared providing rigorous results. The solvers
are the linear programming solvers that use rational arithmetic
(exlp, per Plex, QSopt_ex), his lp-package Lurupa
(see http://www.ti3.tu-harburg.de/) that uses
interval arithmetic and duality theory, and the general purpose solver
GlobSol, ICOS and Numerica, that use interval arithmetic and
branch-and-bound.
At first glance it seems not to be fair to take only lp-testproblems
for the general purpose solver. It is evident that a specialized
lp-solver is much faster. But it also evident that a solver cannot
solve NONLINEAR problems better and of higher dimension than
LINEAR ones. So this comparison gives a good impression about
the maximal dimension of the problems that can be solved by these
softwarepackage. And this is important for user.
A central part in optimization is convex programming with (due to its
history) almost uncountable many applications. I have written a survey
``On Verified Numerical Computations in Convex Programming''
( to appear soon in JJIAM)
which contains many applications. Moreover, I have written a software
package called
VSDP (VerifiedSemiDefinite Programming)
which uses MATLAB and INTLAB. The package and the survey can be
downloaded from
http://www.ti3.tu-harburg.de.
In the last decade it turned out that very many convex programming
applications can be reformulated as semidefinite programming problems.
These include linear, quadratical convex, and second order cone
problems.
With VSDP and Lurupa several applications could be rigorously solved,
out of the areas Control theory, Circuit design, Combinatorial
optimization, Robust optimization, Signal processing, Quantum chemistry,
stochastic forestry problems, oil refinary problems, flap settings of
aircraft, pilot models, audit staff scheduling, truss structure
problems, airline schedule planning, industrial production and
allocation models, image restoration problems, multisector economic
planning problems....,
Most, but not all, are problems from NETLIB LP Library (a collection
of difficult to solve lp-problems) and the problems in the SDPLIB.
These are problems up to thousands of constraints and millions of
variables.
If you download the packages Lurupa and VSDP, you can try these
applications. Its very easy.
[Neumaier]
Applications to computer-assisted proofs can be found in
A. Neumaier,
Computer-assisted proofs,
in: (W. Luther and W. Otten, eds.) Proc. 12th GAMM-IMACS Symp.
Sci. Comp., (SCAN 2006). IEEE Computer Society, 2007.
http://www.mat.univie.ac.at/~neum/papers.html#caps
Applications to uncertain large-scale truss structures are in
A. Neumaier and A. Pownuk,
Linear systems with large uncertainties, with applications to
truss structures,
Reliable Computing 13 (2007), 149-172.
http://www.mat.univie.ac.at/~neum/papers.html#linunc
Applications to uncertain partial differential equations are in
A. Neumaier,
Certified error bounds for uncertain elliptic equations,
J. Comput. Appl. Math. 218 (2008), 125-136.
http://www.mat.univie.ac.at/~neum/papers.html#pdebounds