Recent Papers and Preprints

by Arnold Neumaier

(but abstracts of my Physics/Chemistry papers are here, although links to these papers are also on this page!)
complete list of publications

It is God's privilege to conceal things, but the kings' pride is to research them.
(Proverbs 25:2)

A= Analysis, C = Combinatorics, F = Foundations,
L = Linear Algebra, N = Numerical Analysis, O = Optimization,
P = Physics/Chemistry, S = Statistics
* = book

For preprints of the papers listed below, abstracts and ps and/or pdf files are available online; for the published version see the references given.
For my remaining publications, scanned copies of the published version are at list of publications.
For manuscripts with an e-print number, you can also get the latex source (of some version of the paper) from an e-print archive such as http://xxx.uni-augsburg.de

I do not send out paper copies of my manuscripts. If you have problems downloading, decoding, or printing a file, look at downloading/printing problems?

Slides (to be papers soon)

Pxx9.
A. Neumaier, AD-like techniques in global optimization, Slides, 2008
pdf file (2283K)
Using tools from functional analysis and global optimization, methods are presented for obtaining, given an approximate solution of a partial differential equation, realistic error bounds for some response functional of the solution.

The method is based on computable bounds for the inverse of linear elliptic operators. Like in the dual weighted residual (DWR) method, our error bounds for response functionals have the quadratic approximation property (so that they are asymptotically optimal), but in contrast to DWR, our bounds are rigorous and also capture the higher order contributions to the error.

Using global optimization techniques, bounds can be found that not only cover the errors in solving the differential equations but also the errors caused by the uncertainty in the parameters. This provides reliable tools for the assessment of uncertainty in the solution of elliptic partial differential equations. Our bounds are independent of the way the approximations are obtained, hence can be used to independently verify the quality of an approximation computed by an arbitrary solver. The bounds not only account for discretization errors but also for other numerical errors introduced through numerical integration and boundary aproximations.

We also discuss how to represent model uncertainty in terms of so-called clouds, which describe the rough shapes of typical samples of various size, without fixing the details of the distribution. Clouds use only information from 1- and 2-dimensional marginal distributions, readily available in practice.

Pxx8.
A. Neumaier, FMathL - Formal Mathematical Language, Slides, 2009
pdf file (98K)
Slides for a lecture at the AUTOMATHEŲ 2009 workshop, giving an overview of our work in the FMathL project for creating a modeling and documentation language for mathematics, suited to the habits of mathematicians

Pxx8.
A. Neumaier, Towards optimization-based error bounds for uncertain PDEs, Slides, 2008
pdf file (347K)
Using tools from functional analysis and global optimization, methods are presented for obtaining, given an approximate solution of a partial differential equation, realistic error bounds for some response functional of the solution.

Pxx7.
A. Neumaier, Optical models for quantum mechanics, Slides, 2008
pdf file (156K)
This lecture (the second of three) discusses work towards a new, classical view of quantum mechanics. It is based on an analysis of polarized light, of the meaning of quantum ensembles in a field theory, of classical simulations of quantum computing algorithms, and resulting optical models for the simulation of quantum mechanics.
In particular, it is shown that classical second-order stochastic optics is precisely the quantum mechanics of a single photon, with all its phenomenological bells and whistles.

Pxx6.
A. Neumaier, Classical and quantum field aspects of light, Slides, 2008
pdf file (374K)
This lecture discusses foundational problems on the nature of light revealed by 1. attempts to define a probability concept for photons, 2. quantum models for photons on demands (and their realization through laser-induced emission by a calcium ion in a cavity), 3. models explaining the photo effect, and 4. Bell-type experiments for single photon nonlocality.

Oxx5.
A. Neumaier, Global Optimization and Constraint Satisfaction, Slides, 2006.
pdf file (173K)

Oxx4.
A. Neumaier, Constrained global optimization, Slides, 2005.
pdf file (225K)

Oxx3.
A. Neumaier, Worst case analysis of mechanical structures by interval methods, Slides, 2005.
pdf file (263K)

Oxx2.
A. Neumaier, Uncertainty modeling for robust verifiable design, Slides, 2004.
pdf file (318K)

Oxx1.
A. Neumaier and J.-P. Merlet, Constraint satisfaction and global optimization in robotics, Slides, 2002.
pdf file (449K)

Manuscripts submitted for publication

F000.
A. Neumaier and P. Schodl, A Semantic Turing Machine, Manuscript (2009).
pdf file (396K)
A semantic Turing machine (STM) is a variant of a programable register machine that combines the transparency and simplicity of the action of a Turing machine with a clearly arranged assembler-style programming language and a user-friendly representation of semantic information.
This paper describes the concept of the STM, its memory management and ow control, and shows how a semantic Turing machine can simulate any ordinary Turing machine. Analogous to a universal Turing machine, we give a universal semantic Turing machine (USTM), which is a special STM that can simulate every STM. The USTM serves both as a self-contained semantic explanation of many aspects of the STM, and as a check that an STM implementation works correctly.
Three appendices give the grammar of the STM programming language, tables for character code, and the essential parts of a MATLAB implementation of the STM.

F000.
A. Neumaier, The FMathL mathematical framework, Manuscript (2009).
pdf file (497K)
Several frameworks for mathematics have been constructed in the literature. To avoid the paradoxes of naive set theory, Zermelo and Fraenkel constructed a type-free system of sets, based on first order predicate logic, while von Neumann, Bernays and Goedel constructed a system with two types, sets and classes. These systems suffice for the common needs of a working mathematician. But they are inconvenient to use without pervasive abuse of language and notation, which makes human-machine communication of mathematics difficult.
In this document, we construct a new framework for mathematics, designed as part of the specification system FMathL for the formalized communication of mathematics between humans and machines, in a way close to the actual practice of mathematics. The framework is described in such a way that this description can become part of the FMathL system itself.
All axioms are given in the form of familiar existence requirements and properties that are used by mathematicians on an everyday basis. Thus mathematicians trusting the axiom of choice and hence the law of excluded middle can readily convince themselves of their truth in their private (but publicly educated) view of mathematical concepts.
The exposition is such that students exposed to the typical introductory mathematics courses should have no serious difficulty understanding the material.

N000.
A. Neumaier, Computer graphics, linear interpolation, and nonstandard intervals, Manuscript (2009).
pdf file (340K)
This document is an assessment of the value of optimal linear interpolation enclosures and of nonstandard intervals, especially with respect to applications in computer graphics, and of the extent a future IEEE interval standard should support these.
It turns out that essentially all present applications of nonstandard intervals to practical problems can be matched by similarly efficient approaches based on standard intervals only. On the other hand, a number of applications were inspired by the use of nonstandard arithmetic.
This suggests the requirement of a minimal support for nonstandard intervals, allowing implementations of nonstandard interval arithmetic to be compatible with the standard, while a full support by making one of the conflicting variants required seems not appropriate.

N000.
A. Neumaier, Vienna proposal for interval standardization, Manuscript (2008).
pdf file (179K)
This document contains a detailed proposal for a future IEEE 1788 standard on interval arithmetic. It is written in a form that should be not too difficult to transform into a formal, complete and fully precise document specifying the standard to be. Part 1 contains a concise summary of the basic assumptions (some of which may be controversial) upon which the remaining document is based. The items in Part 1 are grouped such that separate voting on each issue is meaningful. Parts 2-5 specify the internal representation of intervals and the operations defined on them. Part 6 specifies the external representation of intervals and the conversion between internal and external representations. Part 7 is optional and discusses useful modifications of the directed rounding behavior specified in the IEEE 754-2008 standard that would simplify an implementation of the proposed standard. This final version incorporates many suggestions and corrections by the people mentioned above. In particular, comprehensive discussions with Michel Hack, who read and commented in detail many intermediate versions, had a strong influence on this proposal.

P000.
A. Neumaier and D. Westra, Classical and Quantum Mechanics via Lie algebras.
arXiv:0810.1019
pdf file (2507K)
The goal of this book is to present classical mechanics, quantum mechanics, and statistical mechanics in an almost completely algebraic setting, thereby introducing mathematicians, physicists, and engineers to the ideas relating classical and quantum mechanics with Lie algebras and Lie groups. The book emphasizes the closeness of classical and quantum mechanics, and the material is selected in a way to make this closeness as apparent as possible.
Much of the material covered here is not part of standard textbook treatments of classical or quantum mechanics (or is only superficially treated there). For physics students who want to get a broader view of the subject, this book may therefore serve as a useful complement to standard treatments of quantum mechanics.
Almost without exception, this book is about precise concepts and exact results in classical mechanics, quantum mechanics, and statistical mechanics. The structural properties of mechanics are discussed independent of computational techniques for obtaining quantitatively correct numbers from the assumptions made. The standard approximation machinery for calculating from first principles explicit thermodynamic properties of materials, or explicit cross sections for high energy experiments can be found in many textbooks and is not repeated here.

O000.
F. Domes and A. Neumaier, Directed Cholesky factorizations and applications, submitted, 2008.
pdf file (261K)
downloading/printing problems?
In exact arithmetic, the Cholesky factorization of a nonsingular symmetric matrix exists iff the matrix is positive definite. Several applications require safe tests for definiteness or to derive valid inequalities that use computations involving a Cholesky factorization.This paper introduces directed versions of the Cholesky factorization, from which rigorous conclusions can be drawn in spite of rounding errors. Applications are given to checking definiteness and to finding tight box enclosures for ellipsoids defined by strictly convex quadratic inequalities. This also provides a convenient preprocessing step for constrained optimization problems. Numerical tests show that even nearly singular problems can be handled successfully.

Papers accepted for publication

O000.
F. Domes and A. Neumaier, Quadratic constraint propagation, Constraints, to appear (2009).
pdf file (185K)
downloading/printing problems?
This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of univariate quadratic problems. Care is taken to ensure that all methods correctly account for rounding errors in the computations.

O000.
M. Fuchs and A. Neumaier, A splitting technique for discrete search based on convex relaxation, J. Uncertain Systems, Special Issue on Global Optimization and Intelligent Algorithm, to appear (2009).
pdf file (175K)
In mixed integer programming branching methods are a powerful and frequently employed tool. This paper presents a branching strategy for the case that the integer constraints are associated with a finite set of points in a possibly multidimensional space. We use the knowledge about this discrete set represented by its minimum spanning tree and find a splitting based on convex relaxation. Typical applications include design optimization problems where design points specifying several discrete choices can be considered as such discrete sets.

N000.
A. Neumaier, Improving interval enclosures, Reliable Computing, to appear (2009).
pdf file (244K)
This paper serves as background information for the Vienna proposal for interval standardization, explaining what is needed in practice to make competent use of the interval arithmetic provided by an implementation of the standard to be.
Discussed are methods to improve the quality of interval enclosures of the range of a function over a box, considerations of possible hardware support facilitating the implementation of such methods, and the results of a simple interval challenge that I had posed to the reliable computing mailing list on November 26, 2008.
Also given is an example of a bound constrained global optimization problem in 4 variables that has a 2-dimensional continuum of global minimizers. This makes standard branch and bound codes extremely slow, and therefore may serve as a useful degenerate test problem.

A000.
P. Schodl and A. Neumaier, Continuity notions for multi-valued mappings, Reliable Computing, to appear.
pdf file (245K)
downloading/printing problems?
If we regard a multi-valued mapping as a generalization of a single-valued mapping, we may ask for generalizations of important properties as well, concerning fixed-points, projection, composition etc. The main interest in this paper are continuity notions for multi-valued mappings which allow non-connected images, but still have a certain fixed-point property. The starting point is a continuity notion introduced by the second author in his book 'Interval Methods for Systems of Equations', which was stated to possess a zero-property. However, we provide a counterexample to this theorem. Two other continuity notions are introduced and examined, and applied in a logical field.

S000.
V. Kreinovich and A. Neumaier, For Piecewise Smooth Signals, l^1 Method Is the Best Among l^p: An Interval-Based Justification of an Empirical Fact, Int. J. Gen. Systems, to appear.
pdf file (97K)
downloading/printing problems?
Traditional engineering techniques use the least squares method (i.e., in mathematical terms, the l^2-norm) to process data. It is known that in many practical situations, l^p-methods with other values of p lead to better results. In different practical situations, different values of p are optimal. It is known that in several situations when we need to reconstruct a piecewise smooth signal, the empirically optimal value of p is close to 1. In this paper, we provide a new interval-based theoretical explanation for this empirical fact.

Published papers

O145.
M. Fuchs and A. Neumaier, Potential based clouds in robust design optimization, J. Stat. Theory Practice 3 (2009), 225-238.
pdf file (970K)
downloading/printing problems?
Robust design optimization methods applied to real life problem face some major difficulties: how to deal with the estimation of probability densities when data are sparse, how to cope with high dimensional problems and how to use valuable information in the form of unformalized expert knowledge.
In this paper we introduce in detail the clouds formalism as means to process available uncertainty information reliably, even if limited in amount and possibly lacking a formal description, to providing a worst-case analysis with confidence regions of relevant scenarios which can be involved in an optimization problem formulation for robust design.

O000.
R. Fourer, C. Maheshwari, A. Neumaier, D. Orban, and H. Schichl, Convexity and Concavity Detection in Computational Graphs. Tree Walks for Convexity Assessment, INFORMS J. Computing, Articles in Advance, July 29, 2009.
pdf file (313K)
downloading/printing problems?
In this paper, we examine sets of symbolic tools associated to modeling systems for mathematical programming which can be used to automatically detect the presence or lack of convexity and concavity in the objective and constraint functions. As a consequence, convexity of the feasible set may be assessed to some extent. The coconut solver system focuses on nonlinear global continuous optimization and possesses its own modeling language and data structures. The Dr.AMPL meta-solver aims to analyze nonlinear differentiable optimization models and hooks into the ampl Solver Library [Gay02]. The symbolic analysis may be supplemented with a numerical disproving phase when the former returns inconclusive results. We report numerical results using these tools on sets of test problems for both global and local optimization.

O143.
M. Fuchs and A. Neumaier, Autonomous robust design optimization with potential clouds, Int. J. Reliability Safety 3 (2009), 23-34.
pdf file (230K)
downloading/printing problems?
The task of autonomous and robust design cannot be regarded as a single task, but consists of two tasks that have to be accomplished concurrently. First, the design should be found autonomously; this indicates the existence of a method which is able to find the optimal design choice automatically. Second, the design should be robust; in other words: the design should be safeguarded against uncertain perturbations. Traditional modeling of uncertainties faces several problems. The lack of knowledge about distributions of uncertain variables or about correlations between uncertain data, respectively, typically leads to underestimation of error probabilities. Moreover, in higher dimensions the numerical computation of the error probabilities is very expensive, if not impossible, even provided the knowledge of the multivariate probability distributions. Based on the clouds formalism we have developed new methodologies to gather all available uncertainty information from expert engineers, process it to a reliable worst-case analysis and finally optimize the design seeking the optimal robust design.

SO142.
V. Kreinovich, A. Neumaier, and Gang Xiang Towards a Combination of Interval and Ellipsoid Uncertainty, Vych. Techn. (Computational Technologies) 13 (2008), 5-16.
pdf file (217K)
downloading/printing problems?
In many real-life situations, we do not know the probability distribution of measurement errors but only upper bounds on these errors. In such situations, once we know the measurement results, we can only conclude that the actual (unknown) values of a quantity belongs to some interval. Based on this interval uncertainty, we want to find the range of possible values of a desired function of the uncertain quantities. In general, computing this range is an NP-hard problem, but in a linear approximation, valid for small uncertainties, there is a linear time algorithm for computing the range. In other situations, we know an ellipsoid that contains the actual values. In this case, we also have a linear time algorithm for computing the range of a linear function. In some cases, however, we have a combination of interval and ellipsoid uncertainty. In this case, the actual values belong to the intersection of a box and an ellipsoid. In general, estimating the range over the intersection enables us to get a narrower range for the function. In this paper, we provide two algorithms for estimating the range of a linear function over an intersection in linear time: a simpler O(n log(n)) algorithm and a (somewhat more complex) linear time algorithm. Both algorithms can be extended to the l^p-case, when instead of an ellipsoid we have a set defined by a p-norm.

O141.
M. Fuchs and A. Neumaier, Handling uncertainty in higher dimensions with potential clouds towards robust design optimization, pp. 376-382 in: Soft Methods for Handling Variability and Imprecision (D. Dubois et al., eds.), Advances in Soft Computing, Vol. 48, Springer 2008.
pdf file (265K)
downloading/printing problems?
Robust design optimization methods applied to real life problems face some major difficulties: how to deal with the estimation of probability densities when data are sparse, how to cope with high dimensional problems and how to use valuable information in the form of unformalized expert knowledge.
We introduce the clouds formalism as means to process available uncertainty information reliably, even if limited in amount and possibly lacking a formal description. We provide a worst-case analysis with confidence regions of relevant scenarios which can be involved in an optimization problem formulation for robust design.

O140.
M. Fuchs, D. Girimonte, D. Izzo, and A. Neumaier, Robust and automated space system design, Chapter (pp. 251-272) in: Robust intelligent systems (A. Schuster, ed.), Springer, 2008.
pdf file (357K)
downloading/printing problems?
Over the last few years, much research has been dedicated to the creation of decisions support systems for space system engineers or even for completely automated design methods capturing the reasoning of system experts. However, the problem of taking into account the uncertainties of variables and models defining an optimal and robust spacecraft design have not been tackled effectively yet. This chapter proposes a novel, simple approach based on the clouds formalism to elicit and process the uncertainty information provided by expert designers and to incorporate this information into the automated search for a robust, optimal design.

O139.
M. Fuchs and A. Neumaier, Uncertainty modeling with clouds in autonomous robust design optimization, pp. 1-22 in: Proc. 3rd Int. Workshop Reliable Engineering Computing, Savannah, Georgia, USA, 2008.
pdf file (399K)
downloading/printing problems?
The task of autonomous and robust design cannot be regarded as a single task, but consists of two tasks that have to be accomplished concurrently.
First, the design should be found autonomously; this indicates the existence of a method which is able to find the optimal design choice automatically.
Second, the design should be robust; in other words: the design should be safeguarded against uncertain perturbations. Traditional modeling of uncertainties faces several problems. The lack of knowledge about distributions of uncertain variables or about correlations between uncertain data, respectively, typically leads to underestimation of error probabilities. Moreover, in higher dimensions the numerical computation of the error probabilities is very expensive, if not impossible, even provided the knowledge of the multivariate probability distributions.
Based on the clouds formalism we have developed new methodologies to gather all available uncertainty information from expert engineers, process it to a reliable worst-case analysis and finally optimize the design seeking the optimal robust design.
The new methods are applied to problems for autonomous optimization in robust spacecraft system design at the European Space Agency (ESA).

O138.
W. Huyer and A. Neumaier, Snobfit - Stable Noisy Optimization by Branch and Fit, ACM Trans. Math. Software 35 (2008), Article 9.
pdf file (323K) Matlab files
downloading/printing problems?
The software package Snobfit for bound constrained (and soft constrained) noisy optimization of an expensive objective function is described. It combines global and local search by branching and local quadratic fits. The program is made robust and flexible for practical use by allowing for hidden constraints, batch function evaluations, change of search regions, etc..

O137.
F. Domes and A. Neumaier, A scaling algorithm for polynomial constraint satisfaction problems, J. Global Optimization 42 (2008), 327-345.
pdf file (223K)
downloading/printing problems?
Good scaling is an essential requirement for the good behavior of many numerical algorithms. In particular, for problems involving multivariate polynomials, a change of scale in one or more variable may have drastic effects on the robustness of subsequent calculations. This paper surveys scaling algorithms for systems of polynomials from the literature, and discusses some new ones, applicable to arbitrary polynomial constraint satisfaction problems.

AN136.
A. Neumaier, Certified error bounds for uncertain elliptic equations, J. Comput. Appl. Math. 218 (2008), 125-136.
pdf file (382K) ps.gz file (190K)
downloading/printing problems?
In many applications, partial differential equations depend on parameters which are only approximately known.
Using tools from functional analysis and global optimization, methods are presented for obtaining certificates for rigorous and realistic error bounds on the solution of linear elliptic partial differential equations in arbitrary domains, either in an energy norm, or of key functionals of the solutions, given an approximate solution.
Uncertainty in the parameters specifying the partial differential equations can be taken into account, either in a worst case setting, or given limited probabilistic information in terms of clouds.

O135.
M. Fuchs, A. Neumaier, and D. Girimonte, Uncertainty modeling in autonomous robust spacecraft system design, Proc. Appl. Math. Mech. 7 (2007), 2060041-2060042.
pdf file (179K)
downloading/printing problems?
In the last few years, much research has been dedicated to the development of decisions support systems for the space system engineers or even of completely automated design methods capturing the reasoning of the system experts. However, the problem of taking into account the uncertainties of the variables and models to determine an optimal and robust spacecraft design has not been tackled effectively yet. Based on the clouds formalism we propose a novel approach to process the uncertainty information provided by expert designers and incorporate it into the automated search for a robust optimal design.

AO134.
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.
ps.gz file (102K), pdf file (111K)
downloading/printing problems?
This paper discusses the problem what makes a computer-assisted proof trustworthy, the quest for an algorithmic support system for computer-assisted proof, relations to global optimization, an analysis of some recent proofs, and some current challenges which appear to be amenable to a computer-assisted treatment.

C133.
R. Woo and A. Neumaier, On graphs whose spectral radius is bounded by 3/2 sqrt(2), Graphs and Combinatorics 23 (2007), 1-14.
ps.gz file (135K), pdf file (144K) slides (99K)

downloading/printing problems?
The structure of graphs whose largest eigenvalue is bounded by 3/2 sqrt(2) (approx. 2.1312) is investigated. In particular, such a graph can have at most one circuit, and has a natural quipu structure.

OP132.
T. Vinko and A. Neumaier, New bounds for Morse clusters, J. Global Optimization 39 (2007), 483-494.
ps.gz file (166K), pdf file (197K)
downloading/printing problems?
This paper presents new, simple arguments improving the lower bounds for the total energy and the minimal inter-particle distance in minimal energy atom cluster problems with interactions given by a Morse potential, where the atom separation problem is difficult due to the finite energy at zero atom separation. Apart from being sharper than previously known bounds, they also apply for a wider range rho>4.967 of the parameter in the Morse potential. Most results also hold for more general pair potentials.

NO131.
A. Neumaier and A. Pownuk, Linear systems with large uncertainties, with applications to truss structures, Reliable Computing 13 (2007), 149-172.
ps.gz file (466K), pdf file (621K)
downloading/printing problems?
Linear systems whose coefficients have large uncertainties arise routinely in finite element calculations for structures with uncertain geometry, material properties, or loads. However, a true worst case analysis of the influence of such uncertainties was previously possible only for very small systems and uncertainties, or in special cases where the coefficients do not exhibit dependence.
This paper presents a method for computing rigorous bounds on the solution of such systems, with a computable overestimation factor that is frequently quite small. The merits of the new approach are demonstrated by computing realistic bounds for some large, uncertain truss structures, some leading to linear systems with over 5000 variables and over 10000 interval parameters, with excellent bounds for up to about 10% input uncertainty.
Also discussed are some counterexamples for the performance of traditional approximate methods for worst case uncertainty analysis.

O130.
H. Schichl and A. Neumaier, Transposition theorems and qualification-free optimality conditions, Siam J. Optimization 17 (2006), 1035-1055.
ps.gz file (175K), pdf file (211K)
downloading/printing problems?
New theorems of the alternative for polynomial constraints (based on the Positivstellensatz from real algebraic geometry) and for linear constraints (generalizing the transposition theorems of Motzkin and Tucker) are proved. Based on these, two Karush-John optimality conditions - holding without any constraint qualification - are proved for single- or multi-objective constrained optimization problems. The first condition applies to polynomial optimization problems only, and gives for the first time necessary and sufficient global optimality conditions for polynomial problems. The second condition applies to smooth local optimization problems and strengthens known local conditions. If some linear or concave constraints are present, the new version reduces the number of constraints for which a constraint qualification is needed to get the Kuhn-Tucker conditions.

N129.
R.B. Kearfott, M.T. Nakao, A. Neumaier, S.M. Rump, S.P. Shary, and P. van Hentenryck, Standardized notation in interval analysis, pp. 106-113 in: Proc. XIII Baikal International School-seminar "Optimization methods and their applications", Irkutsk, Baikal, July 2-8, 2005. Vol. 4 "Interval analysis". - Irkutsk: Institute of Energy Systems SB RAS, 2005.
dvi.gz file (16K), ps.gz file (81K), pdf file (137K), downloading/printing problems?
A standard for the notation of the most used quantities and operators in interval analysis is proposed.

NO128.
H. Schichl and A. Neumaier, Interval Analysis on Directed Acyclic Graphs for Global Optimization, J. Global Optimization 33 (2005), 541-562.
dvi.gz file (29K), ps.gz file (94K), pdf file (184K), Slides, Part 1, Slides, Part 2
downloading/printing problems?
A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation.
Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation.
The implementation is based on earlier work by Kolev on optimal slopes and by Bliek on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly.
Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian.
The linear underestimators can be found either by slope computations, or by recursive backward underestimation.
For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian).

P208.
A. Neumaier, Mathematik, Physik und Ewigkeit (mit einem Augenzwinkern betrachtet), Professorenforum-Journal 6 (2005), No. 3, 37-43.
pdf file (116K)

O126.
A. Neumaier, O. Shcherbina, W. Huyer and T. Vinko, A comparison of complete global optimization solvers, Math. Programming B 103 (2005), 335-356.
ps.gz file (232K), pdf file (406K) detailed results
downloading/printing problems?
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 test problems are available online in AMPL and were translated into the input formats of the various solvers using routines from the COCONUT environment. These translators are available online, too.

N125.
D. Daney, Y. Papegay and A. Neumaier, Interval methods for certification of the kinematic calibration of parallel robots, pp. 191-198 in: Proc. 2004 IEEE Int. Conf. Robotics Automation, New Orleans, LA, April 2004.
pdf file (261K)
downloading/printing problems?
In this paper, we demonstrate how methods based on interval arithmetic and interval analysis can be used to achieve numerical certification of the kinematic calibration of a parallel robots. After describing the usual calibration methods and the motivations for a numerical certification, we briefly present the interval methods we used and the kinematic calibration problem. In the main part, we develop our certified approach of this problem in the case of a Gough platform, and we show with numerical examples how this approach avoids wrong solutions produced by classical approach. Details on implementation and performance are also given.

NO124.
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.
dvi.gz file (157K), ps.gz file (262K), pdf file (581K)
downloading/printing problems?
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 (if there are finitely many). The core of the material is presented in sufficient detail that the survey may serve as a text for teaching constrained global optimization.
After giving motivations for and important examples of applications of global optimization, a precise problem definition is given, and a general form of the traditional first order necessary conditions for a solution. Then more than a dozen software packages for complete global search are described.
A quick review of incomplete methods for bound constrained problems and recipes for their use in the constrained case follows, an explicit example is discussed, introducing the main techniques used within branch and bound techniques. Sections on interval arithmetic, constrained propagation and local optimization are followed by a discussion of how to avoid the cluster problem. Then a discussion of important problem transformations follows, in particular of linear, convex, and semilinear (= mixed integer linear) relaxations that are important for handling larger problems.
Next, reliability issues - centering around rounding error handling and testing methodology - are discussed, and the COCONUT framework for the integration of the different techniques is introduced. A list of challenges facing the field in the near future concludes the survey.

NO123.
H. Schichl and A. Neumaier, Exclusion regions for systems of equations, SIAM J. Numer. Anal. 42 (2004), 383-408.
ps.gz file (784K), pdf file (826K)
downloading/printing problems?
Branch and bound methods for finding all zeros of a nonlinear system of equations in a box frequently have the difficulty that subboxes containing no solution cannot be easily eliminated if there is a nearby zero outside the box. 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 paper discusses the reasons for the occurrence of this so-called cluster effect, and how to reduce the cluster effect by defining exclusion regions around each zero found, that are guaranteed to contain no other zero and hence can safely be discarded.
Such exclusion regions are traditionally constructed using uniqueness tests based on the Krawczyk operator or the Kantorovich theorem. These results are reviewed; moreover, refinements are proved that significantly enlarge the size of the exclusion region. Existence and uniqueness tests are also given.

SO122.
A. Neumaier, Clouds, fuzzy sets and probability intervals, Reliable Computing 10 (2004), 249-272.
dvi.gz file (36K), ps.gz file (112K), pdf file (233K)
downloading/printing problems?
Clouds are a concept for uncertainty mediating between the concept of a fuzzy set and that of a probability distribution. A cloud is to a random variable more or less what an interval is to a number. We discuss the basic theoretical and numerical properties of clouds, and relate them to histograms, cumulative distribution functions, and likelihood ratios.
We show how to compute nonlinear transformations of clouds, using global optimization and constraint satisfaction techniques. We also show how to compute rigorous enclosures for the expectation of arbitrary functions of random variables, and for probabilities of arbitrary statements involving random variables, even for problems involving more than a few variables.
Finally, we relate clouds to concepts from fuzzy set theory, in particular to the consistent possibility and necessity measures of Jamison and Lodwick.

C121.
A. Neumaier, Dual polar spaces as extremal distance-regular graphs, Europ. J. Combinatorics 25 (2004), 269-274.
dvi file (24K), ps.gz file (54K), pdf file (146K), downloading/printing problems?
A new inequality for the parameters of distance-regular graphs is proved. It implies that if there are infinitely many distance-regular graphs with fixed lambda, mu, a_i and c_i containing an induced quadrangle then necessarily c_{i+1} >= 1+(mu -1)c_i. As the dual polar graphs show, this inequality is best possible. Some related results are also discussed.

O120.
W. Huyer and A. Neumaier, Integral approximation of rays and verification of feasibility, Reliable Computing 10 (2004), 195-207.
ps.gz file (134K), pdf file (423K)
downloading/printing problems?
An algorithm is presented that produces an integer vector nearly parallel to a given vector. The algorithm can be used to discover exact rational solutions of homogeneous or inhomogeneous linear systems of equations, given a sufficiently accurate approximate solution.
As an application, we show how to verify rigorously the feasibility of degenerate vertices of a linear program with integer coefficients, and how to recognize rigorously certain redundant linear constraints in a given system of linear equations and inequalities. This is a first step towards the handling of degeneracies and redundandies within rigorous global optimization codes.

NO119.
A. Neumaier and O. Shcherbina, Safe bounds in linear and mixed-integer programming, Math. Programming A 99 (2004), 283-296.
dvi.gz file (38K), ps.gz file (88K), pdf file (165K), AMPL file for counterexample (210K), downloading/printing problems?
Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MIP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.

P118.
U. Leonhardt and A. Neumaier, Explicit effective Hamiltonians for linear quantum-optical networks, J. Optics B: Quantum Semiclass. Opt. 6 (2004), L1-L4. quant-ph/0306123
download

N0117.
H. Schichl and A. Neumaier, The NOP-2 Modeling Language, Chapter 15 in: Modeling Languages in Mathematical Optimization (J. Kallrath, ed.), Applied Optimization, Vol. 88, Kluwer, Boston 2004.
html version
ps.gz file (197K), pdf.gz file (179K), downloading/printing problems?
We present a short overview over the modeling language NOP-2 for specifying general optimization problems, including constrained local or global nonlinear programs and constrained single and multistage stochastic programs. The proposed language is specifically designed to represent the internal (separable and repetitive) structure of the problem.

N116.
A. Neumaier, Mathematical Model Building, Chapter 3 in: Modeling Languages in Mathematical Optimization (J. Kallrath, ed.), Kluwer, Boston 2004.
html version
dvi.gz file (20K), ps.gz file (47K), pdf file (74K), downloading/printing problems?
Some notes on mathematical modeling, listing motivations, applications, a numerical toolkit, general modeling rules, modeling conflicts, useful attitudes, and structuring the modeling work into 16 related activities by means of a novel modeling diagram.

O115.
O. Shcherbina, A. Neumaier, Djamila Sam-Haroud, Xuan-Ha Vu and Tuan-Viet Nguyen, Benchmarking global optimization and constraint satisfaction codes, pp.211--222 in: Ch. Bliek, Ch. Jermann and A. Neumaier (eds.), Global Optimization and Constraint Satisfaction, Springer, Berlin 2003.
dvi.gz file (17K), ps.gz file (60K), pdf file (117K), downloading/printing problems?
A benchmarking suite describing over 1000 optimization problems and constraint satisfaction problems covering problems from different traditions is described, annotated with best known solutions, and accompanied by recommended benchmarking protocols for comparing test results.

PN113.
P. Frantsuzov, A. Neumaier and V.A. Mandelshtam, Gaussian resolutions for equilibrium density matrices, Chem. Phys. Letters 381 (2003), 117-122. quant-ph/0306124
download

PS112.
A. Neumaier, Ensembles and experiments in classical and quantum physics, quant-ph/0303047, Int. J. Mod. Phys. B 17 (2003), 2937-2980.
download

N111.
A. Neumaier, Enclosing clusters of zeros of polynomials, J. Comput. Appl. Math. 156 (2003), 389-401.
dvi.gz file (53K), ps.gz file (79K), pdf file (207K)
downloading/printing problems?
Lagrange interpolation and partial fraction expansion can be used to derive a Gerschgorin-type theorem that gives simple and powerful a posteriori error bounds for the zeros of a polynomial if approximations to all zeros are available. Compared to bounds from a corresponding eigenvalue problem, a factor of at least two is gained.
The accuracy of the bounds is analyzed, and special attention is given to ensure that the bounds work well not only for single zeros but also for multiple zeros and clusters of close zeros.
A Rouché-type theorem is also given, that in many cases reduces the bound even further.

O110.
W. Huyer and A. Neumaier, A new exact penalty function, SIAM J. Optimization 13 (2003), 1141-1158.
dvi.gz file (35K), ps.gz file (99K), pdf file (272K), downloading/printing problems?
For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They are proved exact in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that controls both the weight of the penalty terms and the regularization of the nonsmooth terms.

NO207.
A. Neumaier, Book review of L. Jaulin, M. Kieffer, O. Didrit and E. Walter, Applied Interval Analysis, 2001, SIAM Rev. 44 (2002), 736-739.
ps.gz file (31K), pdf file (86K), downloading/printing problems?

NOS109.
A. Neumaier, Fuzzy modeling in terms of surprise, Fuzzy Sets and Systems 135 (2003), 21-38.
dvi.gz file (33K), ps.gz file (84K), pdf file (216K)
downloading/printing problems?
This paper presents a new approach to fuzzy modeling based on the concept of surprise. The new concept is related to the traditional membership function by an antitone transformation. Advantages of the surprise approach include:
1. It has a consistent semantic interpretation.
2. It allows the joint use of quantitative and qualitative knowledge, using simple rules of logic.
3. It is a direct extension of (and allows combination with) the least squares approach to reconciling conflicting approximate numerical data.
4. It is ideally suited to optimization under imprecise or conflicting goals, specified by a combination of soft and hard interval constraints.
5. It gives a straightforward approach to constructing families of functions consistent with fuzzy associative memories as used in fuzzy control, with tuning parameters (reflecting linguistic ambiguity) that can be adapted to available performance data.

O108.
A. Neumaier, Rational functions with prescribed global and local minimizers, J. Global Optimization 25 (2003), 175-181.
ps.gz file (142K), pdf file (309K)
downloading/printing problems?
A family of multivariate rational functions is constructed. It has strong local minimizers with prescribed function values at prescribed positions. While there might be additional local minima, such minima cannot be global. Another family of multivariate rational functions is given, having prescribed global minimizers and prescribed interpolating data.

NS107.
J. Santos, W.A. Lodwick and A. Neumaier, A New Approach to Incorporate Uncertainty in Terrain Modeling, pp. 291-299 in: Geographic Information Science: Second International Conference, GIScience 2002, Proceedings (M. Egenhofer and D. Mark, eds.), Lecture Notes in Computer Science Vol. 2478, Springer, New York 2002.
pdf file (392K), downloading/printing problems?
A method for incorporating uncertainty in terrain modelling by expressing elevations as fuzzy numbers is proposed. Given a finite set of fuzzy elevations representative of the topographic surface in a certain region, we develop methods to construct surfaces that incorporate the uncertainty. The smoothness and continuity conditions of the surface generating method are maintained. Using this approach, we generalize some classic interpolators and compare them qualitatively. Extensions to wider classes of interpolators follow naturally from our approach. A numerical example is presented to illustrate this idea.

OP106.
C.A. Meyer, C.A. Floudas, and A. Neumaier, Global optimization with non-factorable constraints, Industrial and Engineering Chemistry Research, 25 (2002), 6413-6424.
ps.gz file (163K), pdf file (407K), downloading/printing problems?
A new inequality for the parameters of distance-regular graphs is proved. It implies that if there are infinitely many distance-regular graphs with fixed lambda, mu, a_i and c_i containing an induced quadrangle then necessarily c_{i+1} >= 1+(mu -1)c_i. As the dual polar graphs show, this inequality is best possible. Some related results are also discussed.

N105.
A. Neumaier, Taylor forms - use and limits, Reliable Computing 9 (2002), 43-79.
ps.gz file (150K), pdf file (489K), downloading/printing problems?
This review is a response to recent discussions on the reliable computing mailing list, and to continuing uncertainties about the properties and merits of Taylor forms, multivariate higher degree generalizations of centered forms. They were invented around 1980 by Lanford, documented in detail in 1984 by Eckmann, Koch and Wittwer, and independently studied and popularized since 1996 by Berz, Makino and Hoefkens. A highlight is their application to the verified integration of asteroid dynamics in the solar system in 2001.
Apart from summarizing what Taylor forms are and do, this review puts them into the perspective of more traditional methods, in particular centered forms, discusses the major applications, and analyzes some of their elementary properties. Particular emphasis is given to overestimation properties and the wrapping effect. A deliberate attempt has been made to offer value statements with appropriate justifications; but all opinions given are my own and might be controversial.

P104.
V.A. Mandelshtam and A. Neumaier, Further generalization and numerical implementation of pseudo-time Schrödinger equations for quantum scattering calculations, physics/0204049, J. Theor. Comput. Chemistry 1 (2002), 1-15.
download

N103.
A. Neumaier, Grand challenges and scientific standards in interval analysis, Reliable Computing 8 (2002), 313-320.
dvi.gz file (14K), ps.gz file (52K), pdf file (148K), downloading/printing problems?
This paper contains a list of 'grand challenge' problems in interval analysis, together with some remarks on improved interaction with mainstream mathematics and on raising scientific standards in interval analysis.

NO102.
W.A. Lodwick, A. Neumaier and F. Newman, Optimization under uncertainty: methods and applications in radiation therapy, Proc. 10th IEEE Int. Conf. Fuzzy Systems, December 2-5, 2001, Melbourne, Australia, pp.1219-1222.
ps.gz file (187K), rtf.gz file (144K),
downloading/printing problems?
This research focuses on the methods and application of optimization under uncertainty to radiation therapy planning, where it is natural and useful to model the uncertainity of the problem directly. In particular, we present methods of optimization under uncertainty in radiation therapy of tumors and compare their results. Two themes are developed in this study: (1) the modeling of inherent uncertainty of the problems and (2) the application of uncertainty optimization.

O101.
H. Schichl, A. Neumaier and S. Dallwig, The NOP-2 modeling language, Ann. Oper. Research 104 (2001), 281-312.
dvi.gz file (32K), ps.gz file (97K), downloading/printing problems?
An enhanced version NOP-2 of the NOP language for specifying global optimization problems is described. Because of its additional features, NOP-2 is comparable to other modeling languages like AMPL and GAMS, and allows the user to define a wide range of problems arising in real life applications such as global constrained (and even stochastic) optimization programs.
NOP-2 permits named variables, parameters, indexing, loops, relational operators, extensive set operations, matrices and tensors, and parameter arithmetic.
The main advantage that makes NOP-2 look and feel considerably different from other modeling languages is the display of the internal analytic structure of the problem. It is fully flexible for interfacing with solvers requiring special features such as automatic differentiation or interval arithmetic.

NS99.
A. Neumaier and T. Schneider, Estimation of parameters and eigenmodes of multivariate autoregressive models, ACM Trans. Math. Softw. 27 (2001), 27-57.
ps.gz file (728K), pdf file (319K), downloading/printing problems?
Dynamical characteristics of a complex system can often be inferred from analyses of a stochastic time series model fitted to observations of the system. Oscillations in geophysical systems, for example, are sometimes characterized by principal oscillation patterns, eigenmodes of estimated autoregressive (AR) models of first order. This paper describes the estimation of eigenmodes of AR models of arbitrary order. AR processes of any order can be decomposed into eigenmodes with characteristic oscillation periods, damping times, and excitations. Estimated eigenmodes and confidence intervals for the eigenmodes and their oscillation periods and damping times can be computed from estimated model parameters. As a computationally efficient method of estimating the parameters of AR models from high-dimensional data, a stepwise least squares algorithm is proposed. This algorithm computes model coefficients and evaluates criteria for the selection of the model order stepwise for AR models of successively decreasing order. Numerical simulations indicate that, with the least squares algorithm, the AR model coefficients and the eigenmodes derived from the coefficients are estimated reliably and that the approximate 95% confidence intervals for the coefficients and eigenmodes are rough approximations of the confidence intervals inferred from the simulations.

NS98.
T. Schneider and A. Neumaier, Algorithm 808: ARfit - A Matlab package for the estimation of parameters and eigenmodes of multivariate autoregressive models, ACM Trans. Math. Softw. 27 (2001), 58-65.
ps.gz file (203K), pdf file (195K), Matlab code, downloading/printing problems?
ARfit is a collection of Matlab modules for modeling and analyzing multivariate time series with autoregressive (AR) models. ARfit contains modules for fitting AR models to given time series data, for analyzing eigenmodes of a fitted model, and for simulating AR processes. ARfit estimates the parameters of AR models from given time series data with a stepwise least squares algorithm that is computationally efficient, in particular when the data are high-dimensional. ARfit modules construct approximate confidence intervals for the estimated parameters and compute statistics with which the adequacy of a fitted model can be assessed. Dynamical characteristics of the modeled time series can be examined by means of a decomposition of a fitted AR model into eigenmodes and associated oscillation periods, damping times, and excitations. The ARfit module that performs the eigendecomposition of a fitted model also constructs approximate confidence intervals for the eigenmodes and their oscillation periods and damping times.

PN97.
A. Neumaier and V.A. Mandelshtam, Pseudo-time Schrödinger equation with absorbing potential for quantum scattering calculations, Phys. Rev. Lett. 86 (2001), 5031-5034. physics/0101032
download

AN96.
A. Neumaier, Generalized Lyapunov-Schmidt reduction for parametrized equations at near singular points, Linear Algebra Appl. 324 (2001), 119-131.
dvi.gz file (19K), ps.gz file (74K), downloading/printing problems?
The Lyapunov-Schmidt reduction is generalized to the case of imperfect singularities. The results presented neither need very precise information about the location of the (near) singularities nor a precise knowledge of (near) null spaces.

NS95.
G.W. Weber, J. Kim, A. Neumaier, C.C. Magori, C.B. Saanane, W. Recheis and H. Seidler, Thickness mapping of the occipital bone on CT-data - a new approach applied on OH9, Acta Anthrop. Sin. Suppl. 19 (2000), 37-46.
pdf file (275K), downloading/printing problems?
A new approach for the analysis of cranial bone thickness is introduced. A semiautomatic algorithm detects a multitude of thicknesses from CT-data of the investigated bones. Every bone is characterized by its its own distribution pattern of cranial thickness, which is then analyzed statistically.

LN94.
R.B. Kearfott, J. Dian and A. Neumaier, Existence verification for singular zeros of nonlinear systems, SIAM J. Numer. Anal. 38 (2000), 360-379.
ps.gz file (127K), downloading/printing problems?
Computational fixed point theorems can be used to automatically verify existence and uniqueness of a solution to a nonlinear system of n equations in variables ranging within a given region of n-space. But such computations succeed only when the Jacobi matrix is nonsingular everywhere in this region. However, in many practical problems, the Jacobi matrix is singular, or nearly so, at the solution. In such cases, tiny perturbations of the problem result in problems either with no solution in the region, or with more than one; thus no general computational technique can prove existence and uniqueness. However, for systems in n complex variables, the multiplicity of such a solution can be verified.
Such verification is possible by computation of the topological degree, but such computations previously required a global search on the (n-1)-dimensional boundary of an n-dimensional region. Here, it is observed that preconditioning leads to a system of equations whose topological degree can be computed with a much lower-dimensional search. Formulas are given for this computation, and the special case of rank-defect one is studied, both theoretically and empirically.

LN93.
A. Neumaier, On Shary's algebraic approach for linear interval equations, SIAM J. Matrix Anal. Appl. 21 (2000), 1156-1162.
dvi.gz file (10K), ps.gz file (58K), pdf file (97K), downloading/printing problems?
A recent method by Shary for enclosing the solution set of a system of linear interval equations is derived in a new way. It is shown that the method converges to the fixed-point inverse, and that it has finite termination with probability 1.

O92.
W. Huyer and A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optimization 14 (1999), 331-355.
ps.gz file (146K), pdf file (361K), Matlab code (30K), downloading/printing problems?
Inspired by the DIRECT method by Jones, Perttunen and Stuckman, we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results.

LN91.
A. Neumaier, A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations, Reliable Computing 5 (1999), 131-136. Erratum, Reliable Computing 6 (2000), 227.
dvi.gz file (10K), Erratum, dvi.gz file, ps.gz file (69K), Erratum, ps.gz file, downloading/printing problems?
Recently, Ning and Kearfott derived a formula for the interval enclosure of the solution set of linear systems of interval equations in the case when the coefficient matrix is an H-matrix. The enclosure is optimal when the midpoint matrix is diagonal, and when the midpoint is the identity, it reduces to the Hansen-Bliek-Rohn method for enclosing preconditioned systems. An elementary proof of this formula is given using only simple properties of H-matrices and Schur complements. The new proof gives additional insight into why the theorem is true. It is also shown how to preserve rigor in the enclosure when finite precision arithmetic is used.

OPS90.
A. Neumaier, S. Dallwig, W. Huyer and H. Schichl, New techniques for the construction of residue potentials for protein folding, pp. 212-224 in: Algorithms for Macromolecular Modelling (P. Deuflhard et al., eds.), Lecture Notes Comput. Sci. Eng. 4, Springer, Berlin 1999.
download

O89.
C.S. Adjiman, S. Dallwig, C.A. Floudas and A. Neumaier, A global optimization method, alphaBB, for general twice-differentiable constrained NLPs - I. Theoretical advances, Computers and Chemical Engineering 22 (1998), 1137-1158.
ps.gz file (193K), downloading/printing problems?
C.S. Adjiman, I.P. Androulakis and C.A. Floudas, A global optimization method, alphaBB, for general twice-differentiable constrained NLPs - II. Implementation and computational results, Computers and Chemical Engineering 22 (1998), 1159-1179.
ps.gz file of part II (163K) containing implementation details and computational studies
A deterministic global optimization method called alphaBB is presented. It finds the global minimizer of constrained nonlinear programs with twice-differentiable objective and constraint functions and finite bounds on the variables. Based on a branch and bound strategy and convex relaxed subproblems, the minimizer is found with guarantee, apart from influences of roundoff errors and the possibility of overflow of work space if too many subproblems need to be considered.
The convex underestimators are generated optimally for bilinear and trilinear terms, whereas for general functions, convexity is achieved by adding a suitable separable quadratic function. The coefficients of this function are calculated using interval arithmetic; a number of different schemes for finding these coefficients are discussed and compared.

LNS88.
A. Neumaier, Solving ill-conditioned and singular linear systems: A tutorial on regularization,
SIAM Review 40 (1998), 636-666.
dvi.gz file (57K), ps.gz file (142K), pdf file (339K), downloading/printing problems?
It is shown that the basic regularization procedures for finding meaningful approximate solutions of ill-conditioned or singular linear systems can be phrased and analyzed in terms of classical linear algebra that can be taught in any numerical analysis course. Apart from rewriting many known results in a more elegant form, we also derive a new two-parameter family of merit functions for the determination of the regularization parameter. The traditional merit functions from generalized cross validation (GCV) and generalized maximum likelihood (GML) are recovered as special cases.

O205.
A. Neumaier, Book review of Janos D. Pinter, Global Optimization in Action, J. Global Optimization 12 (1998), 319-321.
html file

NOS87.
A. Neumaier and E. Groeneveld, Restricted maximum likelihood estimation of covariances in sparse linear models, Genet. Sel. Evol. 30 (1998), 3-26.
shortened published version of the following manuscript: pdf file (246K), ps.gz file (134K), software, downloading/printing problems?
This paper surveys the theoretical and computational development of the restricted maximum likelihood (REML) approach for the estimation of covariance matrices in linear stochastic models.
A new derivation of this approach is given, valid under very weak conditions on the noise.
Then the calculation of the gradient of restricted loglikelihood functions is discussed, with special emphasis on the case of large and sparse model equations with a large number of unknown covariance components and possibly incomplete data. It turns out that the gradient calculations require hardly any extra storage, and only a small multiple of the number of operations needed to calculate the function values alone.
The analytic gradient procedure was integrated into the VCE package for covariance component estimation in large animal breeding models. It resulted in dramatic improvements of performance over the previous implementation with finite difference gradients. An example with more than 250 000 normal equations and 55 covariance components took hours instead of days of CPU time, and this was not an untypical case.

NOP85.
A. Neumaier, Molecular modeling of proteins and mathematical prediction of protein structure, SIAM Rev. 39 (1997), 407-460.
download

LN84.
A. Neumaier, Scaling and structural condition numbers, Linear Algebra Appl. 263 (1997), 157-165.
dvi.gz file (10K), ps.gz file (59K), downloading/printing problems?
We introduce structural condition numbers and discuss their significance for the proper scaling of nonsymmetric and symmetric matrices.

O83.
S. Dallwig, A. Neumaier and H. Schichl, GLOPT - A Program for Constrained Global Optimization, pp. 19-36 in: I. Bomze et al., eds., Developments in Global Optimization, Kluwer, Dordrecht 1997.
dvi.gz file (20K, no figures), ps.gz file (80K), downloading/printing problems?
GLOPT is a Fortran77 program for global minimization of a block-separable objective function subject to bound constraints and block-separable constraints. It finds a nearly globally optimal point that is near a true local minimizer. Unless there are several local minimizers that are nearly global, we thus find a good approximation to the global minimizer.
GLOPT uses a branch and bound technique to split the problem recursively into subproblems that are either eliminated or reduced in their size. This is done by an extensive use of the block separable structure of the optimization problem.
In this paper we discuss a new reduction technique for boxes and new ways for generating feasible points of constrained nonlinear programs. These are implemented as the first stage of our GLOPT project. The current implementation of GLOPT uses neither derivatives nor simultaneous information about several constraints. Numerical results are already encouraging. Work on an extension using curvature information and quadratic programming techniques is in progress.

O82.
A. Neumaier, NOP - a Compact Input Format for Nonlinear Optimization Problems, pp. 1-18 in: I. Bomze et al., eds., Developments in Global Optimization, Kluwer, Dordrecht 1997.
dvi.gz file (22K), ps.gz file (93K), downloading/printing problems?
This paper defines a compact format for specifying general constrained nonlinear optimization problems. The proposed format is a nonlinear analogue of an explicit representation of sparse matrices by means of index lists and values of the corresponding matrix entries. Thus the format abstracts from the meaning of the problem and hence does not allow names for variables or parameters, but it explicitly displays the internal structure of the problem. This is a very useful feature for global or large scale local optimization.

O80.
A. Neumaier, Second-order sufficient optimality conditions for local and global nonlinear programming, J. Global Optim. 9 (1996), 141-151.
dvi.gz file (18K), ps.gz file (83K), downloading/printing problems?
This paper presents a new approach to the sufficient conditions of nonlinear programming. Main result is a sufficient condition for the global optimality of a Kuhn-Tucker point. This condition can be verified constructively, using a novel convexity test based on interval analysis, and is guaranteed to prove global optimality of strong local minimizers for sufficiently narrow bounds. Hence it is expected to be a useful tool within branch and bound algorithms for global optimization.

NO79/86.
L.C. Kaufman and A. Neumaier, Image reconstruction through regularization by envelope guided conjugate gradients
ps.gz file (441K), downloading/printing problems?
For publication, the paper was split into two parts:

PET regularization by envelope guided conjugate gradients, IEEE Trans. Medical Imag. 15 (1996), 385-389.
Regularization of ill-posed problems by envelope guided conjugate gradients, J. Comput. Graph. Stat. 6 (1997), 451-463.

In this paper we propose a new way to iteratively solve large scale ill-posed problems, and in particular the image reconstruction problem from noisy images or noisy data linearly related to the pixel intensities. This is done by exploiting the relation between Tikhonov regularization and multiobjective optimization to obtain iteratively approximations to the Tikhonov L-curve and its corner. Monitoring the change of the approximate L-curves allows us to adjust the regularization parameter adaptively during a preconditioned conjugate gradient iteration, so that the desired image can be reconstructed with a low number of iterations. Nonnegativity constraints are taken into account automatically. We present test results on image reconstruction in positron emission tomography (PET).

LN78.
A. Neumaier and M. Olschowka, A new pivoting strategy for Gaussian elimination, Linear Algebra Appl. 240 (1996), 131-151.
dvi.gz file (26K), ps.gz file (83K), downloading/printing problems?
This paper discusses a method for determining a good pivoting sequence for Gaussian elimination, based on an algorithm for solving assignment problems. The worst case complexity is O(n^3), while in practice O(n^{2.25}) operations are sufficient.

COS77.
C. Elster and A. Neumaier, Screening by conference designs, Biometrika 82 (1995), 589-602.
dvi.gz file (28K), ps.gz file (92K), pdf file (215K), downloading/printing problems?
Screening experiments are addressed to the identification of the relevant variables within some process or experimental outcome potentially depending on a large number of variables. In this paper we introduce a new class of experimental designs called edge designs. These designs are very useful for screening experiments since they allow a model-independent estimate of the set of relevant variables, thus providing more robustness than traditional designs.
We give a bound on the determinant of the information matrix of certain edge designs, and show that a large class of edge designs meeting this bound can be constructed from conference matrices. We also show that the resulting conference designs have an optimal space exploration property which is important as a guard against unexpected nonlinearities. We survey the existence of and constructions for conference matrices, and give, for n<50 variables, explicit such matrices when n is a prime, and references to explicit constructions otherwise.

O81.
C. Elster and A. Neumaier, A trust region method for the optimization of noisy functions, Computing 58 (1997), 31-46.
dvi.gz file (21K), ps.gz file (73K), downloading/printing problems?
The optimization of noisy or not exactly known functions is a common problem occuring in various applications as for instance in the task of experimental optimization. The traditional tool for the treatment of such problems is the method of Nelder-Mead (NM). In this paper an alternative method based on a trust region approach (TR) is offered and compared to Nelder-Mead. On the standard collection of test functions for unconstrained optimization by Moré et al., TR performs substantially more robust than NM. If performance is measured by the number of function evaluations, TR is on the average twice as fast as NM.

O76.
C. Elster and A. Neumaier, A grid algorithm for bound constrained optimization of noisy functions, IMA J. Numer. Anal. 15 (1995), 585-608.
dvi.gz file (39K), ps.gz file (108K), pdf file (228K), downloading/printing problems?
The optimization of noisy functions is a common problem occurring in various applications. In this paper, a new approach is presented for low-dimensional bound constrained problems, based on the use of quadratic models and a restriction of the evaluation points to successively refined grids. In the noiseless case, global convergence of the algorithm to a stationary point is proved; in the noisy case a bound for the limit accuracy is derived.
An extensive numerical comparison with two widely used methods - a quasi-Newton method and the simplex method of Nelder and Mead - performed on a standard collection of test problems, shows that the new algorithm is comparable with quasi-Newton in the noiseless case, and is much more robust than Nelder-Mead in the noisy case. If performance is measured solely by the number of function evaluations needed to achieve a prescribed reduction of the difference to the minimal function value (as for instance in the optimization of experiments), the new algorithm is also significantly faster than Nelder-Mead.

C75.
R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least -1-sqrt{2}, Linear Algebra Appl. 226-228 (1995), 577-592.
ps.gz file (87K), downloading/printing problems?
Main result: If the smallest eigenvalue of a graph H exceeds a fixed number larger than the smallest root (approx. -2.4812) of the polynomial x^3+2x^2-2x-2, and if every vertex of H has sufficiently large valency, then the smallest eigenvalue of H is at least -1-sqrt{2} and the structure of H is completely characterized through a new generalization of line graphs.

NP73.
T. Rage, A. Neumaier and C. Schlier, Rigorous verification of chaos in a molecular model, Phys. Rev. E. 50 (1994), 2682-2688.
download

N72.
A. Neumaier, Global, rigorous and realistic bounds for the solution of dissipative differential equations. Part I: Theory, Computing 52 (1994), 315-336.
dvi.gz file (37K), pdf file (215K), ps.gz file (115K), downloading/printing problems?
It is shown how interval analysis can be used to calculate rigorously valid enclosures of solutions to initial value problems for ordinary differential equations. In contrast to previously known methods, the enclosures obtained are valid over larger time intervals, and for uniformly dissipative systems even globally.
This paper discusses the underlying theory; main tools are logarithmic norms and differential inequalities.

N70.
A. Neumaier, The wrapping effect, ellipsoid arithmetic, stability and confidence regions, Computing Supplementum 9 (1993), 175-190.
dvi.gz file (55K), ps.gz file (109K), pdf file (169K), downloading/printing problems?
The wrapping effect is one of the main reasons that the application of interval arithmetic to the enclosure of dynamical systems is difficult. In this paper the source of wrapping is analyzed algebraically and geometrically. A new method for reducing the wrapping effect is proposed, based on an interval ellipsoid arithmetic.
Applications are given to the verification of stability regions for nonlinear discrete dynamical systems and to the computation of rigorous confidence regions for nonlinear functions of normally distributed random vectors.

N54.
A. Neumaier, The enclosure of solutions of parameter-dependent systems of equations. In: Reliability in Computing (ed. by R.E. Moore). Acad. Press, San Diego 1988, pp. 269-286.
scanned text

Unpublished papers

P989.
W. Huyer and A. Neumaier, Benchmarking of MCS on the Noiseless Function Testbed, Manuscript (2009).
pdf file (6815K)
downloading/printing problems?
Benchmarking results with the MCS algorithm for boundconstrained global optimization on the noiseless BBOB 2009 testbed are described.

P985.
L. Pal, M.C. Markot, T. Csendes and A. Neumaier, BBO-Benchmarking of the GLOBAL method for the Noiseless Function Testbed, Manuscript (2009).
pdf file (880K)
downloading/printing problems?
GLOBAL is a multistart type stochastic method for bound constrained global optimization problems. Its goal is to find all the local minima that are potentially global. For this reason it involves a combination of sampling, clustering, and local search. We report its results on the noisy free problems given.

P986.
L. Pal, M.C. Markot, T. Csendes and A. Neumaier, BBO-Benchmarking of the GLOBAL method for the Noiseless Function Testbed, Manuscript (2009).
pdf file (863K)
downloading/printing problems?
GLOBAL is a multistart type stochastic method for bound constrained global optimization problems. Its goal is to find all the local minima that are potentially global. For this reason it involves a combination of sampling, clustering, and local search. We report its results on the noisy free problems given.

P987.
W. Huyer and A. Neumaier, Benchmarking of SNOBFIT on the Noisy Function Testbed, Manuscript (2009).
pdf file (7373K)
downloading/printing problems?
Benchmarking results with the SNOBFIT algorithm for noisy bound-constrained global optimization on the noisy BBOB 2009 testbed are described.

P988.
W. Huyer and A. Neumaier, Benchmarking of MCS on the Noisy Function Testbed, Manuscript (2009).
pdf file (7582K)
downloading/printing problems?
Benchmarking results with the MCS algorithm for boundconstrained global optimization on the noisy BBOB 2009 testbed are described.

P990.
A. Neumaier, A simple hidden variable experiment, arXiv:0706.0155
ps.gz file (170K), pdf file (97K)
downloading/printing problems?
An experiment is described which proves, using single photons only, that the standard hidden variables assumptions (commonly used to derive Bell inequalities) are inconsistent with quantum mechanics. The analysis is very simple and transparent. In particular, it demonstrates that a classical wave model for quantum mechanics is not ruled out by experiments demonstrating the violation of the traditional hidden variable assumptions.

P991.
A. Neumaier, On the foundations of thermodynamics, arXiv:0705.3790
ps.gz file (324K), pdf file (587K)
downloading/printing problems?
On the basis of new, concise foundations, this paper establishes the four laws of thermodynamics, the Maxwell relations, and the stability requirements for response functions, in a form applicable to global (homogeneous), local (hydrodynamic) and microlocal (kinetic) equilibrium.
The present, self-contained treatment needs very little formal machinery and stays very close to the formulas as they are applied by the practicing physicist, chemist, or engineer. From a few basic assumptions, the full structure of phenomenological thermodynamics and of classical and quantum statistical mechanics is recovered.
Care has been taken to keep the foundations free of subjective aspects (which traditionally creep in through information or probability). One might describe the paper as a uniform treatment of the nondynamical part of classical and quantum statistical mechanics ``without statistics'' (i.e., suitable for the definite descriptions of single objects) and ``without mechanics'' (i.e., independent of microscopic assumptions). When enriched by the traditional examples and applications, this paper may serve as the basis for a course on thermal physics.

P992.
A. Neumaier, M. Fuchs, E. Dolejsi, T. Csendes, J. Dombi, B. Bá&nhelyi, Z. Gera, Application of clouds for modeling uncertainties in robust space system design, Final Report, ARIADNA Study 05/5201, European Space Agency (ESA), 2007.
pdf file (587K)
downloading/printing problems?
Ariadna Completed Studies
This report discusses a case study for modeling uncertainties in a Matlab model for space system design, with the goal of determining robust feasible designs for the model.
The problem structure involves all difficulties an optimization problem can have: discrete variables, strong nonlinearities, discontinuities due to branching decisions, multiple objectives, multiple local minima.
The formal modeling of uncertainty by means of clouds, and the robust optimization of a resulting uncertain model was considered. A heuristic approach using surrogate function modeling, corner searches, and discrete line searches was used to solve the robust optimization problem in case of interval uncertainties. This approach works satisfactorily for the model problem for the case of interval uncertainty.
Solving the model problem with uncertainty revealed significant robustness advantages of the approach using uncertainty. The influence on assumed knowledge about additional uncertainty information was illustrated by for a few model choices.

P993.
A. Neumaier, Collapse challenge for interpretations of quantum mechanics, Manuscript (2005). quant-ph/0505172
dvi.gz file (7K), ps.gz file (61K), pdf file (62K)
downloading/printing problems?

NO994.
A. Neumaier, Constraint propagation for univariate quadratic constraints, Manuscript (January 5, 2005).
dvi.gz file (6K), ps.gz file (67K), pdf file (58K), downloading/printing problems?
We present formulas for rigorous constraint propagation of quadratic equality or inequality constraints involving a single nonlinear variable. Since the analysis is very elementary, probably everything in here has been known for a long time. The present approach, based on directed rounding only, provide efficient alternatives to the procedures discussed by Hansen and Walster, which employ interval arithmetic.

S995.
A. Neumaier, On the structure of clouds, Manuscript (2003).
dvi.gz file (15K), ps.gz file (60K), pdf file (156K)
downloading/printing problems?
Clouds, recently introduced by the author, give - within the traditional probabilistic framework - a concept for imprecise probability, with which quantitative conclusions can be derived from uncertain probabilistic information. A cloud is to a random variable more or less what an interval is to a number.
In this paper, some structural results about clouds are derived. In particular, it is shown that every cloud contains some random variable.

O996.
C. Bliek, P. Spellucci, L.N. Vicente, A. Neumaier, L. Granvilliers, E. Monfroy, F. Benhamou, E. Huens, P. Van Hentenryck, D. Sam-Haroud and B. Faltings, Algorithms for Solving Nonlinear Constrained and Optimization Problems: The State of the Art. A progress report of the COCONUT project, 2001.
html file of abstract, with links to the 222 page report in ps and pdf.
The goal of this document is to summarize the state of the art of algorithms for solving nonlinear constrained and optimization problems.

PS997.
A. Neumaier, W. Huyer and E. Bornberg-Bauer, Hydrophobicity Analysis of Amino Acids, WWW-Document (1999).
html file,
Based on a principal component analysis of 47 published attempts to quantify hydrophobicity in terms of a single scale, we define a representation of the 20 amino acids as points in a 3-dimensional hydrophobicity space and display it by means of a minimal spanning tree. The dominant scale is found to be close to two scales derived from contact potentials.

O998.
A. Neumaier, On convergence and restart conditions for a nonlinear conjugate gradient method,
Manuscript (1997).
dvi.gz file (15K), ps.gz file (71K), downloading/printing problems?
A global convergence theorem for unconstrained minimization algorithms with an efficient line search is derived. The theorem applies to a new version of the conjugate gradient method derived here in terms of minimizing the effect of zigzagging. The global convergence condition makes much weaker demands on the line search than previous methods.
Local Q-linear convergence in a neighborhood of a strong local minimizer follows under additional conditions that define natural restart conditions based on line search accuracy and loss of conjugacy of successive gradients.

LS999.
B. Graf and A. Neumaier, A greedy ball algorithm for classification, Manuscript (1997).
ps.gz file (132K), downloading/printing problems?
We propose a classification scheme that generates a set of balls separating points belonging to different points sets in n-dimensional space such that all points of a given training set are classified correctly. The method is very fast in training. Applications discussed include breast cancer prognosis and character recognition.

Downloading/printing problems

I do not send out paper copies of my manuscripts; but here are some hints of how to make your own copy.

To uncompress the files obtained you need the GNU program gunzip.

Some browsers seem to save *.dvi.gz files as *.dvi, so that one thinks one has a dvi-file while one actually may still have to do a gunzip. And some other browsers appear to do an automatic gunzip, while leaving the file name with the suffix .gz! In both cases, the file needs to be renamed appropriately for further processing.

See The gzip homepage or Compression for gunzip, dvi.exe or TeX Facilities or LaTeX Home Page for a dvi-viewer, Ghostscript for the popular free postscript viewer, and

Help for printing PostScript Files.

If you still have difficulties obtaining or printing one of the papers above, please tell me details about the difficulties you encountered.

Global Optimization
Protein Folding
Interval Methods
Regularization
Mathematical Software
Computational Mathematics Links
Mathematics Links
Statistics Links
my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)