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