Numbers, Insights, and Pictures: Using Mathematics and Computing to Understand Mathematical Models
M. Wright
Mathematical models are omnipresent in science, engineering, medicine, health, and business—there are models of interacting chemical species, the collision of stars, multifunctional materials, bridges buffeted by high winds, groundwater pollution, a beating heart, spreading epidemics, and tomorrow's stock prices. Models are indispensable because the real world's behavior is almost always too complicated to understand, and certainly too difficult to predict accurately, by observation alone. In extreme cases, certain real-world phenomena that need to be studied, such as nuclear explosions or ingestion of carcinogens by babies, do not permit systematic observation or even experimentation. Combined with intuition, experience, and data, the abstraction and generality of mathematics allow us to create models that can be analyzed, tinkered and computed with, and visualized.
Throughout the process of developing any model, mathematical issues arise, such as accuracy, uniqueness of the model's solution, unwanted artifacts, and the degree to which realism has been sacrificed for simplicity and mathematical tractability. But mathematics should go far beyond these questions: since mathematics provides insight into reality through models, mathematics (and its close colleague, computing) should also generate insights into the models themselves. As the world becomes increasingly dependent on models that are complex both mathematically and computationally, requiring in some instances days of high-performance computations, research in the mathematical sciences is needed to create theoretical and numerical foundations for analyzing and understanding mathematical models.
We highlight four areas (among many others) for application of mathematics to models.
1. Properties of a model
Once a trial model has been formulated, it is natural to ask: What are its properties? Does it do what I want? If not, why not? These questions can be, and typically are, answered in a loose way by experiment, but it is obviously desirable to have an array of mathematics that can address these questions more rigorously.
Major progress has been made recently on modeling languages, both general and domain-specific, which are in turn tied to the mathematics of symbolic computation. When the model includes constraints posed in a suitable modeling language, techniques from symbolic computation should be able to determine important mathematical properties of the constraint set. Initial steps toward this goal have already been taken through "pre-solve" features that can identify and automatically remove linear dependencies among certain classes of constraints. However, as models become larger, more complex, and more nonlinear, increasingly sophisticated analytical methods of this type are needed.
In particular, it is of great interest to determine whether the region satisfied by the given constraints is convex, unbounded, or empty; and, if empty, some indication should be given of the "most offending" constraints and what perturbations could make them feasible. Analysis of regions defined by hyperplanes is a standard feature of linear programming, but the mathematics needed to characterize (say) constraints defined by nonlinear algebraic equations or positive semidefiniteness conditions is far beyond today's state of the art. Issues of geometry enter in unusual ways, for instance in finding bounds on the number of constraints that must hold exactly at the solution, or the multiplicity of critical eigenvalues in eigenvalue optimization problems.
In models based on partial differential equations, a longstanding question about the properties of a model involves the effects of the mesh used to solve a discretized version of the model (which is, in effect, a model of the model). Some general relationships are known between the mesh size and accuracy for many classes of equations, but these results are less certain, or unknown, for models based on adaptive meshing or with features that imply more favorable accuracy estimates.
2. Connections between parts of a model
Consider a continuous constrained optimization model in which the Lagrange multipliers define the relationship at the solution between the active constraints and the objective function. Using these multipliers, it is possible to identify the most significant constraints and to gauge the local effect if a single constraint is removed. This kind of information, useful as it is, is only the tip of the iceberg of the valuable information about models that could be gleaned from deeper analysis. At least three roles are clear in this regard.
(a) Closed-form relationships. For models posed in sufficiently expressive modeling languages, new analytical techniques should be able to produce closed-form specifications of relationships among the parts of a model. These relationships need not be restricted to the constraints and objective function, but could also include subexpressions and subcalculations that occur in defining the problem. For models not posed as constrained optimization problems, the combination of a suitable modeling language and symbolic computation techniques would allow arbitrary elements in the model to be expressed in terms of other elements.
(b) Numerical relationships at an arbitrary point. Generalizing a standard approach from linear programming, any model without constraints can be transformed into a related constrained problem by imposing "artificial constraints", namely bounds or constraints on variables at their present values, thereby creating an optimization problem of which the current point is a solution. Specification of an appropriate objective function, such as the degree of satisfaction of a partial differential equation, could then provide the ingredients needed to compute the local sensitivities of the model's elements to one another.
(c) Visualization. Computer graphics offers a highly developed means for producing wonderful images, but has not (yet) been adapted to represent conceptual and numerical relationships among entities in a model. Collaboration with computer scientists could lead to techniques that display mathematically meaningful connections among parts of a model, and, ideally, that also allow models to be interactively modified based on the visualization. Especially for models with enormous ranges of scale, the associated visualization needs to draw from the underlying mathematics to reflect the scales correctly.
3. Effects of perturbations
The qualitative and quantitative effects of perturbations, longstanding topics in mathematics, are of obvious importance in understanding models. Every model that requires numerical solution on a real computer in any of its parts should, as a matter of course, undergo a complete analysis of the effects of finite-precision calculation, yet even this elementary step suffers from a lack of mathematical support.
The most-studied form of perturbation analysis for models based on optimization involves characterizing the effects on the solution of small changes in the objective function and constraints. Depending on the problem, these effects can vary from smooth to violently discontinuous. In inequality-constrained optimization, for example, small changes in the constraints can totally alter the solution.
For well-behaved models satisfying regularity assumptions, matrix analysis can be applied in the immediate locality. For linear equations, the singular value decomposition explicitly gives, for both the residual and error in the solution, the worst-case perturbations in the matrix and in the right-hand side. However, much remains unknown about perturbation analysis for more complicated problems, such as eigenvalue distribution for unsymmetric matrices and the nature of invariant subspaces. Very limited results are known today, and only for the simplest of problems, for "medium" (rather than small) perturbations, yet these are often the most interesting in practice.
In real-world modeling, because of restrictions implicit in the problem domain, neither the constraints nor the class of admissible perturbations may be fully general. Under various sets of appropriately defined restrictions, it is desirable to know the worst-case and average-case effects of perturbations—if the most pathological cases are excluded, how bad can things be? How bad are they likely to be? Research is needed on determining the effects of structured perturbations as well as of general perturbations in structured problems. An example of the latter occurs in geometric computation, where certain elements in the model are exact (such as the coefficients in a geometric formula) and others are subject to uncertainty.
As mentioned earlier, Lagrange multipliers are highly enlightening, but they cannot necessarily capture non-local behavior. If a constraint is very close to, but not quite, active, its Lagrange multiplier will be zero, whereas a small change in that constraint could lead to a completely different solution. A more general mathematical concept of "multiplier" is needed, as well as strategies for computing numerical bounds that apply to a particular model. (Bounds involving the order of unknown constants are of mathematical interest, but will not help a modeler who needs to know how much change in the flow rate can be tolerated before the dam breaks.)
In addition to perturbations in the model formulation, the effects of uncertainties, changes, and errors in data need a much more careful analysis. In many applications, the model itself includes massive data sets, or else the model's results are constantly compared with observed data. For either of these cases, it is crucial to know whether there is a guaranteed "band of reliability" within which small changes in the data do not affect the quality of the solution, where "quality" may be defined in various ways. It is also important to quantify the potential numerical effects of perturbations in the data, to provide a concrete bound on how much the solution may change. If some of the data points are suspect, for instance, the model should not have to tie itself in knots just to match them.
The mathematical challenges include not only analyzing the vast field of possible nonlinear behavior for continuous problems, but also defining and discovering the effects of perturbation on discrete variables. Perturbation analysis for the latter is increasingly needed because of the growing popularity of hybrid systems, which contain interacting discrete and continuous components.
4. Dependence on parameters
Several decades of research have been devoted to analyzing linear programs whose objective and constraints depend in a specific way on one or more parameters. (This is a much more structured problem than the study of perturbations.) For models posed as general nonlinear optimization problems, obtaining tight results about parametric dependence is extremely challenging, even when stringent restrictions are imposed on allowable functional forms. Very recent work on interior-point methods, for example, shows that problems not satisfying regularity conditions can behave in peculiar ways as the controlling parameter goes to zero. Important questions involve the forms of the solution's dependence on the parameters (continuously? smoothly? almost linearly?), and the assumptions needed to make any meaningful statements at all.
In addition to analytical expressions and order estimates, approaches such as numerical solution techniques and problem-specific heuristics warrant exploration for models that occur widely in practice, such as differential algebraic equations. Another example is semi-infinite optimization problems (finite-dimensional problems containing an infinite number of inequality constraints), where there are interesting issues about how parameters affect the topology of the feasible region.
In some instances, the modeler wants parameter-dependent information about relationships in the model. For example, a parameterized constraint may be redundant when the parameter falls within a certain range. Languages that allow modelers the freedom to specify arbitrary elements as "parameters," combined with the kind of mathematical techniques that will (it is hoped) be developed, would allow this kind of information to be produced.