Applications_of_Interval_Computations_Kearfott_and_Kreinovich

Prévia do material em texto

<p>R. Baker Kearfott and Vladik Kreinovich (Eds.) APPLICATIONS OF INTERVAL COMPUTATIONS Kluwer Academic Publishers</p><p>Applications of Interval Computations</p><p>Applied Optimization Volume 3 The titles published in this series are listed at the end of this volume.</p><p>Applications of Interval Computations Edited by R. Baker Kearfott University of Southwestern Louisiana and Vladik Kreinovich University of Texas at El Paso KLUWER ACADEMIC PUBLISHERS</p><p>A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN-13: 978-1-4613-3442-2 e-ISBN-13: 978-1-4613-3440-8 DOI: 10.1007/978-1-4613-3440-8 Published by Kluwer Academic Publishers, P.O. Box 17, 3300 AA Dordrecht, The Netherlands. Kluwer Academic Publishers incorporates the publishing programmes of D. Reidel, Martinus Nijhoff, Dr W. Junk and MTP Press. Sold and distributed in the U.S.A. and Canada by Kluwer Academic Publishers, 101 Philip Drive, Norwell, MA 02061, U.S.A. In all other countries, sold and distributed by Kluwer Academic Publishers Group, P.O. Box 322, 3300 AH Dordrecht, The Netherlands. Printed on acid-free paper All Rights Reserved 1996 Kluwer Academic Publishers Softcover reprint of the hardcover 1st edition 1996 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.</p><p>CONTENTS PREFACE xiii 1 APPLICATIONS OF INTERVAL COMPUTATIONS: AN INTRODUCTION R. Baker Kearfott and Vladik Kreinovich 1 1 What are Interval Computations? 1 2 International Workshop on Applications of Interval Computations: How This Book Originated 8 3 General Optimization Problems 10 4 General Systems of Equations and Inequalities 14 5 Linear Interval Problems 15 6 Interval Computations Can Also Handle Possible Additional Information About the Input Data 18 7 Software and Hardware Support for Interval Computations 20 REFERENCES 21 2 A REVIEW OF TECHNIQUES IN THE VERIFIED SOLUTION OF CONSTRAINED GLOBAL OPTIMIZATION PROBLEMS R. Baker Kearfott 23 1 Introduction, Basic Ideas and Literature 23 2 On Constrained Optimization Problems 32 3 On Use of Interval Newton Methods 40 4 Applications 52 5 Summary and Present Work 53 REFERENCES 54</p><p>vi APPLICATIONS OF INTERVAL COMPUTATIONS 3 THE SHAPE OF THE SYMMETRIC SOLUTION SET Götz Alefeld, Vladik Kreinovich, and Günter Mayer 61 1 Introduction 61 2 Notation 62 3 Results 63 4 Examples 74 REFERENCES 79 4 LINEAR INTERVAL EQUATIONS: COMPUTING ENCLOSURES WITH BOUNDED RELATIVE OVERESTIMATION IS NP-HARD Jiri Rohn 81 1 Introduction 81 2 The Result 82 3 The Symmetric Case 86 4 Concluding Remark 87 REFERENCES 88 5 QUALITY IMPROVEMENT VIA OPTIMIZATION OF TOLERANCE INTERVALS DURING THE DESIGN STAGE Sevgui Hadjihassan, Eric Walter, and Luc Pronzato 91 1 Introduction 91 2 Some Basic Models, and their Origins 97 3 Model of Performance Characteristic is Known Beforehand 101 4 Model Parameters Estimated in Controlled Conditions 111 5 Controlled Conditions are Unavailable 117 6 Temperature Controller 123 7 Conclusions 126 REFERENCES 128</p><p>Contents vii 6 APPLICATIONS OF INTERVAL COMPUTATIONS TO REGIONAL ECONOMIC INPUT-OUTPUT MODELS Max E. Jerrell 133 1 Economic Input-Output Models 133 2 Technical Coefficients are Only Known with Uncertainty 135 3 Statistical Methods are Not Directly Applicable, Hence, Interval Computations May Be Useful 136 4 Computational Algorithms 138 5 An Example 140 REFERENCES 142 7 INTERVAL ARITHMETIC IN QUANTUM MECHANICS Charles L. Fefferman and Luis A. Seco 145 1 Quantum Mechanics 146 2 Computer-Assisted Set-up 151 3 The Thomas-Fermi Equation 154 4 The Aperiodicity Inequality 160 REFERENCES 164 8 INTERVAL COMPUTATIONS ON THE SPREADSHEET Eero Hyvönen and Stefano De Pascale 169 1 Limitations of Spreadsheet Computing 169 2 Extended IA on a Spreadsheet 174 3 Global IA on a Spreadsheet 184 4 Interval Constraint Spreadsheets 195 5 Discussion 204 REFERENCES 205 9 SOLVING OPTIMIZATION PROBLEMS WITH HELP OF THE UNICALC SOLVER Alexander L. Semenov 211 1 Introduction 211 2 The UniCalc Solver 212</p><p>viii APPLICATIONS OF INTERVAL COMPUTATIONS 3 The Algorithm of Subdefinite Calculations 213 4 Solving Integer Programming Problems 219 5 Real-Valued Optimization 221 6 Future Developments 223 REFERENCES 224 10 AUTOMATICALLY VERIFIED ARITHMETIC ON PROBABILITY DISTRIBUTIONS AND INTERVALS Daniel Berleant 227 1 Introduction 227 2 Correctly Representing PDFs and Intervals with His- tograms 229 3 Arithmetic Operations 232 REFERENCES 243 11 NESTED INTERVALS AND SETS: CONCEPTS, RELATIONS TO FUZZY SETS, AND APPLICATIONS Hung T. Nguyen and Vladik Kreinovich 245 1 Introduction 246 2 Nested Intervals and Nested Sets 250 3 Other Problems Where Nested Sets and Nested Intervals Can Be Used: Identification, Optimization, Control, and Decision Making 267 4 Applications of Nested Sets and Nested Intervals 273 APPENDIX A Proofs 279 REFERENCES 283 12 FUZZY INTERVAL INFERENCE UTILIZING THE CHECKLIST PARADIGM AND BK-RELATIONAL PRODUCTS Ladislav J. Kohout and Wyllis Bandler 291 1 Introduction 291 2 Many-Valued Logics for Interval Fuzzy Inference Based on the Checklist Paradigm 293 3 Groups of Logic Transformations of Interval Connectives 310</p><p>Contents ix 4 Special Types of Compositions of Relations 314 5 An Application: The Basic Knowledge Handling Mechanisms of CLINAID by Means of Relational Inference 321 6 Toward Successful Utilization of Interval Methods in Soft Computing 328 REFERENCES 329 13 COMPUTING UNCERTAINTY IN INTERVAL BASED SETS Luis Mateus Rocha, Vladik Kreinovich, and R. Baker Kearfott 337 1 Introduction 337 2 Evidence Sets as a Description of Uncertainty 338 3 Different Measures of Uncertainty, and How to Describe them Numerically 355 4 L-Fuzzy Sets, Interval Based L-Fuzzy Sets, and L-Evidence Sets 370 5 3-D Uncertainty Unit Cube 374 REFERENCES 377 14 SOFTWARE AND HARDWARE TECHNIQUES FOR ACCURATE, SELF-VALIDATING ARITHMETIC Michael J. Schulte and Earl E. Swartzlander, Jr. 381 1 Introduction 381 2 Software Tools 383 3 Hardware Designs 388 4 A Variable-Precision, Interval Arithmetic Coprocessor 391 5 Conclusions and Areas for Future Research 396 REFERENCES 398 15 STIMULATING HARDWARE AND SOFTWARE SUPPORT FOR INTERVAL ARITHMETIC G. William Walster 405 1 Introduction 405 2 The Participants 406 3 Stable Equilibrium 410</p><p>X APPLICATIONS OF INTERVAL COMPUTATIONS 4 The Interval Paradigm Shift 411 5 System Supplier Demand 412 6 End-user Demand 412 7 Action Plan 414 REFERENCES 415 INDEX 417</p><p>CONTRIBUTORS Götz Alefeld Max E. Jerrell Institut für Angewandte Mathematik College of Business Administration Universität Karlsruhe Northern Arizona University D-76128 Karlsruhe, Germany, Flagstaff, AZ 86011-5066, USA email: email: uni-karlsruhe.de R. Baker Kearfott Wyllis Bandler Department of Mathematics Department of Computer Science University of Southwestern Louisiana Florida State University U.S.L. Box 4-1010 Tallahassee, Florida 32306-4019, USA Lafayette, LA 70504-1010, USA email: Daniel Berleant Dept. of Computer Systems Engineering Ladislav J. Kohout University of Arkansas Department of Computer Science Fayetteville, AR 72701, USA Florida State University email: Tallahassee, Florida 32306-4019, USA email: Charles L. Fefferman Vladik Kreinovich Department of Mathematics Princeton University Department of Computer Science Princeton NJ 08544, USA University of Texas at El Paso El Paso, TX 79968, USA Sevgui Hadjihassan email: vladik@cs.utep.edu Laboratoire des Signaux et Systèmes CNRS/ESE, Plateau de Moulon, Günter Mayer 91192 Gif sur Yvette, France Fachbereich Mathematik Universität Rostock email: sevgui@lss.supelec.fr D-18051 Rostock, Germany Eero Hyvönen email: VTT Information Technology uni-rostock.de P.O. Box 1201 Hung T. Nguyen 02044 VTT Finland Department of Mathematical Sciences email: New Mexico State University Las Cruces, NM 88003-8001, USA email: hungueyn@nmsu.edu</p><p>xii CONTRIBUTORS Stefano De Pascale Alexander L. Semenov VTT Information Technology Novosibirsk Division of the P.O. Box 1201 Russian Research Institute of 02044 VTT Finland Artificial Intelligence email: pr. Lavrent'eva 6 Novosibirsk, Russia, 630090 Luc Pronzato email: Laboratoire I3S, CNRS URA-1376 250 av. A. Einstein, Sophia Antipolis Earl E. Swartzlander, Jr. 66560 Valbonne, France Department of Electrical email: and Computer Engineering University of Texas at Austin Luis Mateus Rocha Austin, TX, 78712, USA Department of Systems Science and Industrial Engineering G. William Walster T.J. Watson School SunSoft, State University of New York A Sun Microsystems, Inc. Business Binghamton, NY 13902, USA 2550 Garcia Avenue, MS UMTV12-40 email: Mountain View, CA 94043-1100, USA binghamton.edu Jiri Rohn Eric Walter Faculty of Mathematics and Physics Laboratoire des Signaux et Systèmes Charles University CNRS/ESE, Plateau de Moulon Malostranské nám. 25 91192 Gif sur Yvette, France 118 00 Prague, Czech Republic email: walter@lss.supelec.fr and Institute of Computer Science Academy of Sciences Pod vodárenskou 2 182 07 Prague, Czech Republic email: rohnQuivt.cas.cz Michael J. Schulte Department of Electrical and Computer Engineering University of Texas at Austin Austin, TX, 78712, USA email: Luis A. Seco Department of Mathematics University of Toronto Toronto, Canada M5S 1A4 email:</p><p>PREFACE Primary Audience for the Book Specialists in numerical computations who are interested in algorithms with automatic result verification. Engineers, scientists, and practitioners who desire results with automatic verification and who would therefore benefit from the experience of suc- cessful applications. Students in applied mathematics and computer science who want to learn these methods. Goal Of the Book This book contains surveys of applications of interval computations, i.e., appli- cations of numerical methods with automatic result verification, that were pre- sented at an international workshop on the subject in El Paso, Texas, February 23-25, 1995. The purpose of this book is to disseminate detailed and surveyed information about existing and potential applications of this new growing field. Brief Description of the Papers At the most fundamental level, interval arithmetic operations work with sets: The result of a single arithmetic operation is the set of all possible results as the operands range over the domain. For example, [0.9, 1.1] + [2.9, 3.1] = [3.8,4.2], where [3.8,4.2] = E [0.9,1.1] and E The power of interval arithmetic comes from the fact that (i) the elementary operations and standard functions can be computed for intervals with formulas and subroutines; and (ii) directed roundings can be used, that the images of these operations (e.g.</p><p>xiv APPLICATIONS OF INTERVAL COMPUTATIONS [3.8,4.2] in the preceding example) rigorously contain the exact result of the computations. These facts allow rigorous enclosure of roundoff error, truncation error, and errors in data; computation of rigorous bounds on the ranges of functions. In fact, interval arithmetic is a convenient and effective means of obtaining information used in place of Lipschitz constants. Such information, combined with bounds on the ranges of functions that interval arithmetic supplies, is widely recognized as valuable in algorithms for global optimization. In "A Review of Techniques in the Verified Solution of Constrained Global Optimiza- tion Problems," Kearfott reviews the literature, including several books on the subject, outlines some of the basic techniques, including some of his own ex- perimental ones, and gives advice. A related fundamental problem, the numerical analysis of linear systems of equations, is treated in the articles by Alefeld et al. and by Rohn. Interval arithmetic computations, naively arranged, sometimes implicitly assume inde- pendent variation among quantities among which there actually are relation- ships. This interval dependency leads to overestimation (i.e. lack of sharpness) in computed solution sets. For example, handling a symmetric linear system with uncertainty in the coefficients as an arbitrary, unsymmetric system leads to such interval dependency. In "The Shape of the Symmetric Solution Set," Alefeld, Kreinovich and Mayer describe the exact solution set to symmetric lin- ear systems as an intersection of linear and quadratic inequalities. In "Linear Interval Equations: Computing Enclosures with Bounded Relative Or Abso- lute Overestimation is NP-Hard," Jirí Rohn shows that there is no polynomial time algorithm that computes bounds on the solution sets to all interval linear systems with overestimation less than 8, for any 8 > 0. This result can guide algorithm developers. Fortunately, heuristic methods such as interval Gaussian elimination or the interval Gauss-Seidel method work well for many systems in practice, when the widths of the coefficient intervals are small and also in many other cases. Hadjihassan et al. and Jerrell use these fundamental numerical analysis con- siderations in manufacturing design and in economic input-output models, re- spectively. In both works, uncertainties in the input data are encompassed by describing them as intervals. In "Quality Improvement via the Optimiza- tion of Tolerance Intervals During the Design Stage," Hadjihassan, Walter and Pronzato use a combination of interval and non-interval techniques to optimize</p><p>Preface XV the tolerance of manufactured items, subject to uncertainties in the inputs. In "Applications of Interval Computations to Regional Economic Input-Output Models," Jerrell effectively uses fundamental properties of interval linear sys- tems in Leontief input/output models. Jerrell thus obtains meaningful bounds for the impact of Northern Arizona University on the economy of Coconino County, Arizona. Related to global optimization, computational existence and uniqueness proofs are possible with interval computations. Fefferman and Seco's contribution, "Interval Arithmetic in Quantum Mechanics" is an example of a computer- assisted proof outside of general global optimization algorithms. Fefferman and Seco discuss the role of interval arithmetic in establishment of an inequality related to a precise asymptotic formula for the ground state of a non-relativistic atom. Also related to global optimization is constraint propagation, increasingly pop- ular in recent years in fields such as robotics and computer-aided geometric design, to verify intersection or non-intersection, etc. Several authors have also applied the technique in general global optimization and nonlinear equa- tion systems codes and software. In this technique, sometimes implemented in languages such as Prolog, relationships among intermediate quantities in arith- metic expressions in constraints are used recursively to compute ever-narrower bounds on solution variables. This volume contains two software systems that allow such computations. In "Interval Computations on the Spreadsheet," Hyvönen and De Pascale explain an extension of Microsoft Excel that allows interval computations, and constraint propagation in particular. In "Solving Optimization Problems with Help of the UniCalc Solver," Semenov describes an integrated interactive environment, available commercially, that uses sub- definite programming, related to interval constraint propagation, to solve vari- ous types of optimization problems. Experts in statistics and in fuzzy logic have found the ability of intervals to represent uncertainties valuable. Various higher-order structures have been de- fined and utilized. In "Automatically Verified Arithmetic on Probability Dis- tributions and Intervals," Berleant surveys statistical applications of interval computations, while the surveys "Nested Intervals and Sets: Concepts, Re- lations to Fuzzy Sets, and Applications" by Nguyen and Kreinovich, "Fuzzy Interval Inference Utilizing the Checklist Paradigm and BK-Relational Prod- ucts" by Kohout and Bandler, and "Computing Uncertainty in Interval Based Sets" by Rocha, Kreinovich, and Kearfott describe applications to fuzzy logic and expert systems.</p><p>xvi APPLICATIONS OF INTERVAL COMPUTATIONS In the past, widespread application of interval computations has been limited by availability of hardware and software support. Also, experts in interval com- putations have urged the development of faster, hardware-oriented systems. In "Software and Hardware Techniques for Accurate, Self-Validating Arith- metic," Schulte and Swartzlander review some of the available programming language extensions, packages and problem solving environments for interval computations. They then discuss hardware design alternatives and propose a specific hardware design and software interface for variable precision interval arithmetic. In "Stimulating Hardware and Software Support for Interval Arith- metic," Walster presents his view of why many hardware and software vendors do not presently provide interval computations as integral parts of their prod- ucts. He then discusses steps the community of interval computations experts should take to make such capabilities more widely available. Finally, our introduction gives a more detailed elementary explanation of the fundamentals of interval arithmetic, as well as lengthier elementary explana- tions of the surveys that follow. Our Thanks: to all the authors for their excellent job; to the anonymous referees for their thorough and unrewarding job of re- viewing the papers: refereeing was especially tough because of the strict deadlines; to Kluwer Academic Publishers, especially to John Martindale, who pro- posed the idea of this book and helped us make it happen, and to his helpful assistant Arlene Apone; to Professor Pardalos, who kindly agreed to publish this volume in the optimization series that he is supervising, and who encouraged us in this endeavor; to the sponsors whose support made the workshop possible: to the Institute of Manufacturing and Materials Management; to the University of Texas at El Paso; to the journal of Reliable Computing; to the organizations that helped us by publishing the information about this workshop:</p><p>Preface xvii to the American Mathematical Society; to the Special Interest Group on Artificial Intelligence (SIGART) of the Association for Computing Machinery (ACM); to the Computer Society (CS) of the Institute of Electrical and Elec- tronic Engineers (IEEE); to the granting agencies: this work was supported in part by: the National Science Foundation (NSF), through grants CCR- 9203730, CDA-9015006, and EEC-9322370, and the National Aeronautics and Space Administration (NASA), through grant No. NAG 9-757. and, last but not the least, thanks to you, readers of this book, because it is for you that this book has been composed. Thanks to all of you! R. Baker Kearfott and Vladik Kreinovich August, 1995</p><p>1 APPLICATIONS OF INTERVAL COMPUTATIONS: AN INTRODUCTION R. Baker Kearfott* and Vladik Kreinovich** *Department of Mathematics, University of Southwestern Louisiana, U.S.L. Box 4-1010, Lafayette, LA 70504-1010, USA, email: rbk@usl.edu **Department of Computer Science, University of Texas at El Paso, El Paso, TX 79968, email vladik@cs.utep.edu ABSTRACT The main goal of this introduction is to make the book more accessible to readers who are not familiar with interval computations: to beginning graduate students, to researchers from related fields, etc. With this goal in mind, this introduction describes the basic ideas behind interval computations and behind the applications of interval computations that are surveyed in the book. 1 WHAT ARE INTERVAL COMPUTATIONS? Most Real-Life Application Problems Lead to (Constrained or Unconstrained) Global Optimization In a typical real-life application problem, we need to find an alternative x that satisfies given constraints and that optimizes the value of a given characteristic Y = f(x) (the optimized function f(x) is usually called an objective function). For example: in data processing, we must find a model x that best fits the known data; in this case, f(x) describes how well x fits; 1 R. B. Kearfott and V. Kreinovich (eds.), Applications of Interval Computations, 1-22. 1996 Kluwer Academic Publishers.</p><p>2 CHAPTER 1 in control, we must find the control strategy x that optimizes the given criterion f(x) (e.g., smoothness of the resulting trajectory); in decision making, we must find an alternative x from a given set X of possible alternatives that guarantees the best outcome f(x). From the mathematical viewpoint, all these real-life application problems can be described as (constrained and unconstrained) global optimization problems. In Some Cases, We Must Solve Systems of Equations and/or Inequalities In some real-life problems, there are many constraints on the problem that even finding a single solution x that satisfies all these constraints is a difficult task. This often happens in design problems; e.g., if we want to design a spacecraft that can fulfill the task of taking photos of a distant planet under restrictions on weight and cost. For these problems, there is no question of a choice between several possible solutions (we are lucky if we have one), and therefore, it makes no practical sense to choose an objective function for this choice. Therefore, such problems are formulated as the problems of satisfying given constraints. Each of these constraints is either an inequality (e.g., "total cost a given amount"), or an equality (e.g., "at a given moment of time, the position of the spacecraft must be exactly a given number of miles above the explored planet"). Therefore, in mathematical terms, these problems are formulated as solution of a system of equations and/or inequalities. In other cases (e.g., in economic problems), we know the constraints well, but the objective is only informally formulated (e.g., "welfare of the nation"). In these cases, it is difficult to formulate the objective function in precise math- ematical terms; therefore, it makes sense to provide the decision-makers with the entire set of the alternatives x that satisfy all given constraints, that these decision-makers will make the final decision. In such problems, we also need to solve a system of equations and/or inequalities.</p><p>Applications of Interval Computations: An Introduction 3 Numerical Algorithms Usually Result in Approximate Solutions There exist many numerical algorithms for solving optimization problems (see, e.g., [50]). Algorithms also exist for solving systems of equations and inequali- ties. The majority of these algorithms are iterative, so, when we stop after a certain number of steps, we only get an approximation to the desired solution x. For Many Practical Cases, We Need Guaranteed Estimates of the Solution's Accuracy A natural question is: how good is the approximate solution x? That is, how close is the approximate solution to the desired solution x? In many practical problems, we need a guaranteed solution, i.e., a solution that is guaranteed to be sufficiently close to an optimum (i.e., for which the distance p(x, x) between x and x does not exceed a certain given number E). To get such a guarantee, we definitely need to estimate the closeness p(x,x). Traditional Error Estimating Techniques of Numerical Mathematics Do Not Always Lead to Satisfactory Estimates In the majority of traditional numerical methods, at each step of the iteration process, we get a number (or, a sequence of numbers) that represents an increas- ingly better approximation to the solution. After we compute this approximate solution, we use some estimates (e.g., estimates based on Lipschitz constants) to describe how close is to The resulting method does not always lead to good estimates: For some numerical algorithms, no methods are known yet for estimating the distance Designing such an estimation technique for each new algorithm is usually a very complicated problem. Heuristic algorithms are constantly appearing, and there are simply not enough researchers in the numerical analysis community to find estimates for all of them.</p><p>4 CHAPTER 1 Error estimates of numerical mathematics are usually overestimating. One of the reasons for that is that these methods are usually based only on the final result x of the computations. We could get better estimates if we could use more information about the behavior of the function f(x). To get this information, we either need to do more numerical experiments with the function f, or we can use the values that have been computed during the previous computation steps. In both cases, we need extra com- putation time, and this computation time is added to the running time of the numerical algorithm itself, which is often already large. An Alternative Error Estimation Approach - A Natural Idea An ideal situation would be if we could estimate the errors of the result not after the iteration process (thus, adding time), but simultaneously with the iteration process. This is the main idea behind the interval computations methodology originally proposed by R. E. Moore [13, 14, 15]. This idea will help us solve the above-mentioned problems: First, it will enable us to estimate errors for the approximate solution while computing the solution itself, thus saving computation time. Second, since the error estimation will take place throughout the entire process of computing x, we will be able to use intermediate results in this error estimation and therefore, hopefully, come up with better estimation results (i.e., results that are less overestimating). Finally, this idea will enable us to easily find estimates for new algorithms: Indeed, it is difficult to compute an error estimate for the result of a lengthy computation. However, each lengthy computation consists of a sequence of elementary steps (+, Thus, if we trace this error step-by-step, then this complicated problem is reduced to the problems of estimating the error of a sum (product, etc.) of two previous quantities, when we already know the errors in each quantity. Why "Interval"? If we follow the idea described above, then on each computation step, instead of a single (approximate) number we will compute r and an upper bound</p><p>Applications of Interval Computations: An Introduction 5 A for the error of this approximation. In other words, after each computation step, we will get a pair (F,A). If we know and this means that the actual value r of the corresponding quantity can take any value from - A to In other words, this pair means that instead of the (ideal) single value of r, there is a set of possible values of r, and this set is an interval r = where and Because of this, the above idea is called interval computations. Basic Formulas of Interval Arithmetic For intervals, the above-mentioned step-by-step process works as follows: at each elementary computation step, we perform one of the arithmetic operations := aob, where the two values a and b have already estimated on the previous steps of this algorithm. Since the values a and b have already been estimated by our algorithm, this means that we already have the intervals [a,a] and of possible values of a and b. Since we know that a E [a, a] and b E we can conclude that c belongs to the set of all possible values of a for such a and b, i.e., to the set Example. If = +, and if we know that a E [0.9,1.1] and b E [2.9,3.1], then we can conclude that One can easily see that this set is the interval [3.8,4.2]. In general, the new set (of possible values of c) is called the result of applying the operation to intervals [a, a] and [b,b], and it is denoted by For basic arithmetic operations, it is easy to find explicit expressions for the resulting set:</p><p>6 CHAPTER 1 These operations are called interval arithmetic. To these operations, we must add interval analogues of standard functions (exp, sin, max, etc). For iterative algorithms, we can also take into consideration the fact that, in these algorithms, we repeatedly compute estimates for one and the same quan- tity. Usually, we use a previous estimate to compute the next (usually, better) estimate If we use interval operations, then on these two suc- cessive steps, we get intervals and Since both intervals contain the desired value x, we can conclude that x belongs to the intersection of these intervals. Therefore, as an interval that contains x, on the next step of interval computations, we can take not the interval but the (usually smaller) interval These Formulas Must be Modified to Take Roundoff Errors into Consideration The formulas of interval arithmetic are only valid for idealized computers, in which all arithmetic operations are performed exactly. Real-life computers truncate or round the result of multiplication and division, thus adding addi- tional roundoff errors. To take these errors into consideration, we must modify the above formulas by using the so-called directed roundings, i.e.: a rounding that always returns a lower bound <r, such that -(r) r is a machine number; and a rounding that always returns an upper bound r, such that <r is a machine number. For example, the modified formula for is</p><p>Applications of Interval Computations: An Introduction 7 This Methodology can Also Take into Consideration Uncertainty in the Input Data In many real-life situations, the input data come from measurements. Mea- surements are not 100% precise. Therefore, if we have made the measurement with an accuracy and obtain the measurement result this means that the actual value of the measured quantity can take any value from the interval y = - The desired solution depends on the exact value of Y from this interval. Hence, it makes sense to produce the set of all possible solutions x that correspond to all possible values To generate this estimate, we can start with the intervals for input data (instead of the precise values), and then follow interval computations step-by-step. Brief Summary: The Power of Interval Computations The power of interval arithmetic comes from the following facts: 1. The elementary operations and standard functions (such as sin, cos, and exp, found in standard Fortran) can be computed for intervals by using simple formulas and subroutines; and 2. directed roundings can be used, that the images of these operations (e.g. [3.8,4.2] in the preceding example) rigorously contain the exact result of the (ideal) These facts allow rigorous enclosure of roundoff error, truncation error, and errors in data; computation of rigorous bounds on the ranges of functions. Naive and Sophisticated Interval Computations Interval computations were first applied (in the 1960's) naively, that is, to existing numerical algorithms. In some cases, reasonable estimates appeared as a result. In other cases, the resulting intervals were too wide to be useful. These overestimates made many researchers and practitioners reluctant to use</p><p>8 CHAPTER 1 interval methods. Many researchers, not familiar with the field, are still under the impression that interval computations are not a useful tool. However, in the last three decades, many sophisticated ideas and algorithm modifications have been proposed that enable replacing the excessively wide intervals of naive interval computations with reasonably narrow ones. In some cases, radically new algorithms emerged that were specifically tailored for in- terval computations. For a general survey of basic modern interval techniques, see, e.g., [6]; basic interval optimization techniques are described in [7]. As a result of these improvements, modern interval computations have been successfully applied to many real-life problems. 2 INTERNATIONAL WORKSHOP ON APPLICATIONS OF INTERVAL COMPUTATIONS: HOW THIS BOOK ORIGINATED To promote real-life applications of interval computations, an International Workshop on Applications of Interval Computations (APIC'95) was organized in El Paso, Texas, on February 23-25, 1995. For this workshop, 80 researchers from 15 countries (Austria, Brazil, Canada, China, Czech Republic, Denmark, Finland, France, Germany, Mexico, Poland, Russia, Spain, Ukraine, and the USA) submitted papers describing numerous applications of interval computa- tions: To Engineering: to manufacturing, including: quality control; detection of defects in computer chips; flexible manufacturing; to automatic control, including: control of airplane engines; control of electric power plants; to robotics;</p><p>Applications of Interval Computations: An Introduction 9 to airplane inertial navigation; to civil engineering, including traffic control. To Ergonomics and Social Sciences: to learning curves (that describe how people learn); to project management; to service systems; to sociology. To Physics: to laser beams; to particle accelerators; to astrophysics (planet atmospheres); to image processing in radioastronomy. To Geology and Geophysics. To Chemistry, including: to spectral analysis. To Computer Science and Engineering: to expert systems; to communication networks, especially computer networks. To Economics: to planning; to banking. Extended abstracts of these presentations appeared in [12]. The majority of these papers described specific applications. (Technical details of different spe- cific applications will also appear in the special issue of the international journal Reliable Computing.) In addition to the papers describing technical details of specific applications, we also had several general survey papers, of general interest to the public. It is these surveys that we present in this book. This book contains surveys of the applications of interval computations, i.e., applications of numerical methods with automatic result verification.</p><p>10 CHAPTER 1 3 GENERAL OPTIMIZATION PROBLEMS A General Survey Interval arithmetic is a convenient and effective means of obtaining informa- tion used in the place of Lipschitz constants. Such information, combined with bounds on the ranges of functions that interval arithmetic supplies, is is widely recognized as valuable in algorithms for global optimization. In this book, a general survey of such algorithms, titled "A Review of Techniques in the Ver- ified Solution of Constrained Global Optimization Problems" [10] is given by Kearfott. In this survey, Kearfott: reviews the literature on the subject (including several books); outlines the basic techniques (including some of his own experimental ones); and gives advice on the use of different techniques. Optimization Techniques Based on Constraint Propagation Traditionally, before applying numerical techniques to a problem, we analyze it to formulate a compact and understandable description. Namely: First, we describe all the physical properties characterizing the object, and all the equations and inequalities that describe relations between these properties. Usually, some of these variables can be expressed in terms of the others. As a result, we can express these variables (called dependent) in terms of the remaining few independent variables. We can then reformulate all the restrictions in terms of these independent variables. Thus, we obtain a constrained optimization problem f(x) max with few variables x = xn) and with (often rather complicated) objective func- tion and constraints. (They are complicated because they come from repeated substitution of expressions into other ones, and each such substitution increases the complexity of the resulting expression.)</p><p>Applications of Interval Computations: An Introduction 11 This reduction is useful, because the running time of existing global optimiza- tion techniques grows rapidly with the number of variables, so, the fewer vari- ables we have, the faster we can find the optimum. The reduction itself, however, is time-consuming. It makes sense if we have many similar problems. In this case, we do this reduction once, for a generic problem, and then use the results of this reduction to save time on all these problems. There are fields, however, such as robotics and computer-aided geometric de- sign, in which preliminary reduction is not possible. In problems arising, many variables describe the system: e.g.: To describe the state of a robot, we need to know the coordinates and velocities of all its joints, as well as the coordinates of all the points of the geometric environment in which the robot currently operates. To characterize a design, we also usually need many design parameters. Not all of these characteristics are independent: the lengths of the joints restrict their respective positions; design demands impose heavy restrictions on the design parameters that only few of them remain independent, etc. So, in all these cases, we can apply reduction to get an optimization problem with fewer variables. However, we cannot make these reductions once and forever, because the problems are constantly changing: For a manufacturing robot, the problem drastically changes if a new part is added. For a design problem, the reduction changes every time we add or delete one of the design requirements. (Such change in design requirements is typical for a design process.) In these cases, we should solve unreduced optimization problems, i.e., problems in which there are many different variables, but also many constraints that in effect leave only few of the variables independent. Because of the large number of variables, general optimization techniques do not behave well for such problems, we need new methods. The corresponding technique is called constraint propagation. In this tech- nique, relationships among intermediate quantities in arithmetic expressions in</p><p>12 CHAPTER 1 constraints are used recursively to compute ever-narrower bounds on solution variables. It turns out that constraint propagation can be successfully applied not only to the above-mentioned problems like robotics, in which symbolic reduction is not practical, but also to general optimization and equation-solving prob- lems. Often, even if there is a way to reduce the number of constraints, it is actually advantageous to put in more constraints (but make these constraints simpler) and then apply constraint propagation techniques. Thus, constraint propagation is a new powerful general optimization tool. Several authors have applied the technique in global optimization and nonlinear equation systems codes and software. It turns out that the In the survey "Solving Optimization Problems with Help of the UniCalc Solver" [21], presented in this book, Semenov describes an integrated interactive envi- ronment, available commercially, that uses so-called sub-definite programming (a generalization of interval computations to sets more general than intervals) to solve various types of optimization problems. Two Surveys of Specific Techniques In addition to the general surveys of different interval optimization techniques, the book also contains two surveys of interval optimization techniques tailored to problems in two specific fields: manufacturing (Hadjihassan et al [5]) and quantum mechanics (Fefferman and Seco [39]). Applications to Manufacturing In "Quality Improvement via The Optimization Of Tolerance Intervals Dur- ing The Design Stage" [5], Hadjihassan et al use the fundamental numerical analysis considerations described above in manufacturing design. Uncertainties in the input data are encompassed by describing them as intervals. Namely, in [5], Hadjihassan, Walter and Pronzato use a combination of interval and non-interval techniques to solve the following real-life optimization problem: In mass manufacturing, we can usually only reproduce the parameters of the manufactured objects with a certain accuracy 8 (typically, 5% or 10%). As a result, when we fix the nominal values of these parameters, we can only guarantee that the actual values of the parameters of the manufactured objects are inside the interval [x; - Hence, even if we choose nominal</p><p>Applications of Interval Computations: An Introduction 13 design parameters x = that guarantee the desired value y* of the performance characteristic Y = n(x1, the actual values of Y may differ from The quality f(x) of a design can be characterized, crudely speaking, by the worst case deviation of Y from y*. In Hadjihassan et al [5], interval computations help to solve the problem of finding the optimal (best quality) design, i.e., a design x for which f(x) is minimum. Applications to Quantum Mechanics Many optimization problems occur in fundamental physics. Actually, funda- mental physical theories are usually formulated not in terms of differential equations (as in Newton's time), but in terms of an appropriate variational principle: The characteristics x of the particles and fields must be chosen to optimize the value of an objective function S(x) (called action). This use of op- timization is not simply a mathematical trick: it has a fundamental justification in quantum mechanics (see, e.g., [4]). Because of the optimization formulation of fundamental physical theories, nu- merical optimization techniques, especially interval-type techniques that pro- vide automatic verification, appear to be of great use to physicists. The majority of unsolved fundamental problems in physics, however, are mainly related to areas such as quantum field theory, (quantum) cosmology, etc, for which the equations are not yet confidently known. Since we are not sure about the equations anyway, there is not much need for a guaranteed solution. Therefore, physicists use heuristic techniques, and additional computational efforts needed to estimate the accuracy do not seem to be justified. There is, however, a class of fundamental problems where the corresponding optimization criterion (and related equations) have been known for over 70 years, and the main problems are computational: these are the problems of non-relativistic quantum mechanics. The fundamental equation was described by Schroedinger as early as 1924; this equation describes all the properties of the simplest atoms (hydrogen and helium) with such a good accuracy that physicists were convinced that what was previously known as chemistry would be replaced by fundamental quantum physics. This did not happen because, to describe an atom with n electrons, we need to find a function of 3n variables (by solving an optimization problem or an equivalent differential equation). Even if we take 2 possible values of each of these coordinates, we stil! need 23n values only to describe function. For realistic this problem is clearly computationally intractable.</p><p>14 CHAPTER 1 To solve this problem, several approximate equations and optimization formu- lations have been proposed: Some of them are computationally easy, but lead to very crude (and thus practically useless) estimates. Other approximate equations lead to better estimates, but are still rel- atively computationally complicated. One such approximation, called Thomas-Fermi theory, is considered in the survey "Interval Arithmetic in Quantum Mechanics" [39] by Fefferman and Seco, that is presented in the book. We are interested in the characteristics of the atoms with large n (because for small n, we can simply solve the exact equations). It is known that for large very N, these characteristics tend to behave in a regular fashion, so, to get a good estimate, we can expand the values of the characteristics into an asymptotic series in 1/n, and take only a few terms in this expansion. Hence, we need to find asymptotic formulas for n Several heuristic optimization methods have been proposed to find the asymp- totics of the optimum in this problem. These methods, however, are known to produce good results for some physical problems, but poor estimates for oth- ers. Therefore, there is a real need to apply techniques with automatic result verification, and thus get guaranteed estimates on the asymptotics. Such estimates are obtained in a survey [39] by Fefferman and Seco. Their contribution is thus an example of a computer-assisted proof outside of general global optimization algorithms. Fefferman and Seco explicitly discuss the role of interval arithmetic in establishment of an inequality related to a precise asymptotic formula for the ground state of a non-relativistic atom. 4 GENERAL SYSTEMS OF EQUATIONS AND INEQUALITIES In this book, a survey of constraint propagation techniques for solving such systems is presented. In this technique, sometimes implemented in languages such as Prolog, relationships among intermediate quantities in arithmetic ex- pressions in constraints are used recursively to compute ever-narrower bounds</p><p>Applications of Interval Computations: An Introduction 15 on solution variables. As we have already mentioned, constraint propagation is increasingly popular in recent years in fields such as robotics and computer- aided geometric design. Systems of equations that it allows us to solve can tell, e.g., whether there is an intersection or non-intersection, e.g.: whether after a planned movement the robot will hit the obstacle, or move safely; whether a cutting instrument of a manufacturing robot will actually start cutting the desired part; whether in a computer design all components of the car's design will ac- tually fit into the car frame (intersection in this case will mean that they won't), etc. Several authors have applied this technique in general global optimization and nonlinear equation systems codes and software. This volume contains descriptions of two software systems that allow such com- putations. We have already mentioned a survey by Semenov [21]. In "Interval Computations on the Spreadsheet" [7], Hyvönen and De Pascale explain an extension of Microsoft Excel that allows interval computations, and constraint propagation in particular. 5 LINEAR INTERVAL PROBLEMS Why Linear Problems? In many real-life situations, the general problem (outlined in the beginning of this introduction) can be simplified. A typical situation in which simplification is possible is when we know that the components x1, .., Xn of the desired solution x are relatively small. Then, we can expand all the terms in all the equations that determine x into power series in Xi, and neglect quadratic and higher order terms. As a result, we get a problem with:</p><p>16 CHAPTER 1 a linear objective function = f(x) = and linear constraints: i.e., linear equalities linear inequalities This problem is called a linearization of the original non-linear problem. In other words, in many real-life situations, we must solve linear problems. If all the coefficients Aij, bi, and Cj of the corresponding linear functions are precisely known, then we have a linear programming problem for which many efficient algorithms are known. If we do not know the objective functions, then, as we have mentioned, we must describe the set X of all the vectors x that satisfy the given linear constraints. This description can also be given by linear programming. Interval Linear Problems In many real-life problems, the only source of the values of the coefficients Aij and bi is measurement. Since measurements are never absolutely precise, as a result of these measurements, we only get intervals aij and that contain the (unknown) values of these coefficients. In this case, we are interested in describing the set X of all the vectors x that satisfy the given linear constraints, for some Aij E aij and bj E bj. How to Describe the Solution of an Interval Linear Problem For symmetric and non-symmetric Aij, the set X described above is character- ized in the paper "The Shape of the Symmetric Solution Set" [1] by Alefeld, Kreinovich, and Mayer, presented in this book. Namely, this set is an an inter- section of half-spaces (sets described by linear inequalities) and quadrics (i.e., sets defined by quadratic inequalities). General Interval Linear Problems are Hard to Solve The description of a solution of an interval linear problem provided in Alefeld et al [1] is computationally complicated. A natural question is: is it really a</p><p>Applications of Interval Computations: An Introduction 17 hard problem and no easy algorithm is possible, or there is a simple algorithm, but we simply have not found it yet? The answer to this question is given in a paper by Rohn "Linear Interval Equa- tions: Computing Enclosures with Bounded Relative Or Absolute Overesti- mation is NP-Hard" [19], presented in the book. Namely, Rohn shows that, crudely speaking, there is no feasible (polynomial time) algorithm that com- putes bounds on the solution sets X to all interval linear systems with overes- timation less than 8, for any 8 > 0. Existing Algorithms Can Often Solve Interval Linear Problems Efficiently This general negative result means that, for every algorithm for solving interval linear problems, there are hard cases in which this algorithm either runs too long, or results in a drastic overestimation of X. In practice, several (heuristic) methods such as interval Gaussian elimination or the interval Gauss-Seidel method work well for many real-life systems. In particular, they work well when the widths of the coefficient intervals are small, and also in many other cases. Applications to Economics One case where linear models naturally appear is economics. Namely, the dependency = f(x1, of the amount of goods produced in an economic sector on the amounts of goods X; used in production in this production can be described (with a reasonably good accuracy) by a linear function. The corresponding linear model was first proposed by the Nobel laureate economist W. Leontief, and is therefore called a Leontief model. A typical problem here is to determine the desired amounts of production for each sector that all consumer demands are satisfied, and there is no unnecessary production (i.e., all goods are either directly consumed, or used in production of other goods in the chain that leads to consumption). In his pioneering research, Leontief assumed that the coefficients are known precisely. In this case, we have a linear programming problem, that is (in principle) feasible. In real life, however, the only way to determine the coefficients is from the empirical data. Empirical economic data is not precise. Therefore, instead of</p><p>18 CHAPTER 1 precise values for the coefficients, we have intervals of possible values. Thus, in real life, Leontief's problem leads to an interval linear system. Luckily, in spite of the general computational complexity result, specific interval linear systems stemming from these economic problems are feasible. In this book, a survey of corresponding methods and applications is given by Jerrell in "Applications of Interval Computations to Regional Economic Input-Output Models" [9]. As a case study, Jerrell obtains meaningful bounds for the impact of Northern Arizona University on the economy of Coconino County, Arizona, and on the state of Arizona in general. 6 INTERVAL COMPUTATIONS CAN ALSO HANDLE POSSIBLE ADDITIONAL INFORMATION ABOUT THE INPUT DATA We have already mentioned that interval computations can naturally handle situations in which, instead of the exact values of the input parameters p, intervals p of possible values of these parameters are known. In many real-life cases, in addition to these intervals, we have additional infor- mation about p: In some cases, we know not only the interval of possible values of p, but we also have some information about the probabilities of different values. If we know all the probabilities for all possible values of all parameters, then we can apply traditional statistical techniques. However, if we only know some probabilities for some of the parameters, and only interval information for the others, we need a special technique for combining these two types of information. In this book, a survey of such techniques and their applications is given by Berleant "Automatically Verified Arithmetic on Probability Distributions and Intervals" [4]. In some cases, in addition to the interval in which the value of p is guar- anteed to lie, we have experts who produce narrower intervals to which, they claim, the actual values "most certainly" belong. In this case, in addition to the interval of "definitely possible" values of x (produced by interval computation techniques), it is desirable to supply the user with</p><p>Applications of Interval Computations: An Introduction 19 narrower intervals that result from the experts' narrower input intervals. (These new intervals will be correct enclosures if the experts did not err in their estimates.) In this book, this problem is described and analyzed in a survey "Nested Intervals and Sets: Concepts, Relations to Fuzzy Sets, and Applications" [16] by Nguyen and Kreinovich. It turns out that the resulting formalism is very close to the formulas proposed in so-called fuzzy logic (often without rigorous justification). Namely, to get these formulas, as a "fuzzy truth value" of a statement A, we must take, crudely speaking, the ratio = N(A)/N of those experts (N(A)) who believe A to be true to the total number N of the experts asked. Thus, this ver- sion of interval computation leads to a new justification of the formulas of fuzzy logic. Two other surveys from this book describe further modifications of this idea: The first modification is described by Kohout and Bandler in "Fuzzy Interval Inference Utilizing the Checklist Paradigm and BK- Relational Products" [11]. This modification is based on the fact that we can only ask many questions to the experts. In particular, if we have, say, n statements A1, An of interest, then we can ask an expert's opinion about these n statements, maybe about some of their logical combinations (of the type A1&A2), but not about all > possible logical combinations of these statements. As a result, there may be some statements and Aj for which we only know the truth values and but not Suppose that we are interested in knowing the degree of belief in If, e.g., = = 0.5. Then there are two possibilities: * It could be that the same experts believe in as in Aj. In this case, = = 0.5. It can also be that the experts who believe in are exactly those who do not believe in Aj. In this case, = 0. In general, for a given and we have an interval of possible values of If we already have intervals of possible values for and then we need an interval operation to compute the interval of possible values of u(A&B). Here, interval computations come in handy. As a case study, Kohout and Bandler describes an implementation of this idea in an expert medical system Clinaid. Another modification is described by Rocha et al in "Computing Un- certainty in Interval Based Sets" [18]. The underlying idea is that experts are often inconsistent. Therefore, instead of a single small</p><p>20 CHAPTER 1 interval of possible values, we get several (often non-intersecting) in- tervals that supposedly describe the same quantity. Some intervals are supported by more experts, some by less. To describe the degree of support for each interval x, we can use a ratio N(x)/N similar to that described above. Since each expert selects some interval, these ratios add up to 1 and can thus be mathematically interpreted as (subjec- tive) probabilities. Therefore, to describe the expert's opinions, we must have a probability distribution on the set of all intervals. An interval is a particular case of this distribution, when only one prob- ability is different from 0. In Rocha et al [18], standard operations of interval arithmetic are extended to these new objects. Applications to knowledge representation in expert systems are described. 7 SOFTWARE AND HARDWARE SUPPORT FOR INTERVAL COMPUTATIONS If interval methods are good, why aren't they widely applied? One of the main reasons is lack of easily available software. Now, people rarely program "from scratch": they try to use existing software as much as possible. Therefore, to make interval computations usable, the computations must be supported by software packages. This brings us to the next issue: a software package will not be used if it is not sufficiently fast. Everyone is interested in buying a faster computer, and "a faster computer" means that computer on which typical "benchmarking" programs run faster. The bulk of existing software does not use intervals at all; therefore, when designing new computers, computer engineers try to speed up the operations with numbers that are most frequently used in the usual programs. As a result, operations with numbers are fast, while elementary operations with intervals (that form the basis for interval computations) are much slower. Because of that, experts in interval computations have urged the development of faster, hardware-oriented systems for interval computations. In their survey "Software and Hardware Techniques for Accurate, Self- Validating Arithmetic" [20], Schulte and Swartzlander review some of the avail- able programming language extensions, packages and problem solving environ- ments for interval computations. They then discuss hardware design alterna-</p><p>Applications of Interval Computations: An Introduction 21 tives, and propose a specific hardware design and software interface for variable precision interval arithmetic. Finally, in "Stimulating Hardware and Software Support for Interval Arith- metic" [22], Walster presents his view of why many hardware and software vendors do not presently provide interval computations as integral parts of their products. He then discusses steps the community of interval computa- tions experts should take to make such capabilities more widely available. Acknowledgements This work was supported in part by the National Science Foundation (NSF), through grants CCR-9203730, CDA-9015006, and EEC-9322370, and by the National Aeronautics and Space Administration (NASA), through grant No. NAG 9-757. REFERENCES [1] G. Alefeld, V. Kreinovich, and G. Mayer, "The Shape of the Symmetric Solution Set," This Volume. [2] D. Berleant, "Automatically Verified Arithmetic on Probability Distribu- tions and Intervals", This Volume. [3] C. L. Fefferman and L. A. Seco, "Interval Arithmetic in Quantum Me- chanics", This Volume. [4] R. P. R. B. Leighton, and M. L. Sands, The Feynman Lectures On Physics, Addison-Wesley, Redwood City, CA, 1989. [5] S. Hadjihassan, E. Walter, and L. Pronzato, "Quality Improvement via The Optimization Of Tolerance Intervals During The Design Stage," This Volume. [6] R. Hammer, M. Hocks, U. Kulisch, D. Ratz, Numerical toolbox for verified computing. I. Basic numerical problems, Springer Verlag, Heidelberg, N.Y., 1993. [7] E.R. Hansen, Global optimization using interval analysis, Marcel Dekker, N.Y., 1992.</p><p>22 CHAPTER 1 [8] E. Hyvönen and S. De Pascale, "Interval Computations on the Spread- sheet", This Volume. [9] M. E. Jerrell, "Applications of Interval Computations to Regional Eco- nomic Input-Output Models," This Volume. [10] R. B. Kearfott, "A Review of Techniques in the Verified Solution of Con- strained Global Optimization Problems," This Volume. [11] L. J. Kohout and W. Bandler, "Fuzzy Interval Inference Utilizing the Checklist Paradigm and BK-Relational Products", This Volume. [12] V. Kreinovich (ed.), Reliable Computing, 1995, Supplement (Extended Ab- stracts of APIC'95: International Workshop on Applications of Interval Computations, El Paso, TX, Febr. 23-25, 1995). [13] R. E. Moore, Automatic error analysis in digital computation, Lockheed Missiles and Space Co. Technical Report LMSD-48421, Palo Alto, CA, 1959. [14] R. E. Moore and C. T. Yang, Interval analysis, Lockheed Missiles and Space Co. Technical Report LMSD-285875, Palo Alto, CA, 1959. [15] R. E. Moore, Interval analysis, Prentice Hall, Englewood Cliffs, NJ, 1966. [16] H. T. Nguyen and V. Kreinovich, "Nested Intervals and Sets: Concepts, Relations to Fuzzy Sets, and Applications", This Volume. [17] P. M. Pardalos and J. B. Rosen, Constrained Global Optimization: Algo- rithms and Applications, Springer-Verlag, New York, 1987. [18] L. M. Rocha, V. Kreinovich, and R. B. Kearfott, "Computing Uncertainty in Interval Based Sets", This Volume. [19] J. Rohn, "Linear Interval Equations: Computing Enclosures with Bounded Relative Or Absolute Overestimation is NP-Hard," This Volume. [20] M. J. Schulte and E. E. Swartzlander, Jr., "Software and Hardware Tech- niques for Accurate, Self-Validating Arithmetic," This Volume. [21] A. L. Semenov, "Solving Optimization Problems with Help of the UniCalc Solver," This Volume. [22] G. W. Walster, "Stimulating Hardware and Software Support for Interval Arithmetic," This Volume.</p><p>2 A REVIEW OF TECHNIQUES IN THE VERIFIED SOLUTION OF CONSTRAINED GLOBAL OPTIMIZATION PROBLEMS R. Baker Kearfott* Department of Mathematics University of Southwestern Louisiana U.S.L. Box 4-1010, Lafayette, LA 70504-1010, USA email: rbk@usl.edu *This work was supported in part by National Science Foundation grant CCR-9203730. ABSTRACT Elements and techniques of state-of-the-art automatically verified constrained global optimization algorithms are reviewed, including a description of ways of rigorously verifying feasibility for equality constraints and a careful consideration of the role of active inequality constraints. Previously developed algorithms and general work on the subject are also listed. Limitations of present knowledge are mentioned, and advice is given on which techniques to use in various contexts. Applications are discussed. 1 INTRODUCTION, BASIC IDEAS AND LITERATURE We consider the constrained global optimization problem minimize subject to ci(X) (2.1) where X = A general constrained optimization problem, includ- ing inequality constraints g(X) 0 can be put into this form by introducing slack variables replacing by + g(X) = 0, and appending the bound con- straint 0 see $2.2. 23 R. B. Kearfott and V. Kreinovich (eds.), Applications of Interval Computations, 23-59. 1996 Kluwer Academic Publishers.</p><p>24 CHAPTER 2 We wish to find all minimizers in problem 2.1, and to verify bounds on the local minimum. Because of this, the methods used must go beyond (and build upon) traditional methods utilizing descent, line searches, trust regions, etc. in floating-point arithmetic, such as those in the books [7], [13] [46], or in the software package of [4]: these "approximate minimization" methods find only one approximate minimizer per run, may terminate near points other than minimizers without indications that they have done so, may converge to local minimizers that are not global minimizers, etc. The efficiency of such approximate methods, however, makes them practical. They can be used as in [22] and [24] or [3] to make verification algorithms efficient. The conditions 1,...,q represent actual bound constraints intrinsic to the problem formulation. In rigorous branch and bound algorithms, an overall search region is generally defined through similar bounds: = (2.2) only those bounds corresponding to the index set {ij}}=1 should be treated as actual bound constraints. Deterministic location of the global minima and all global minimizers of the non-convex constrained optimization problem 2.1 is in general very difficult (and, indeed, NP-complete; cf. $2.2 and $2.3). However, interval branch and bound methods have exhibited a degree of success in many instances. Various authors, including Moore [43] and Skelboe [65], Hansen ([17], [18] and [19]), Ichida [21], Ratschek and Rokne [52], Jansson and Knüppel ([23] and [24]), Caprani, Godthaab and Madsen [3] have contributed to the knowledge of such algorithms. See [52] for a coherent explanation of this type of algorithm, as well as for the requisite introduction to interval The basic ideas behind versions of such algorithms for unconstrained opti- mization (where m = 0) can be stated with minimal notation and without reference to details of interval arithmetic. The principles include a check on the range of and a computational existence / uniqueness test. We let X = = be the interval vector ("box") rep- resenting the search region Xi Branch and bound algorithms maintain one or more of these lists: a list L of boxes X to be pro- cessed, a list of boxes the algorithm has reduced to small diameter, and a list C of boxes that have been verified to contain critical points. The general pattern is as follows. 1 Other texts, such as [1], [15], [19], [43] and [48] also give good introductions to the subject, and contain techniques relevant to global optimization.</p><p>Constrained Global Optimization 25 Algorithm 1 (Abstract Branch-and-Bound Pattern) 1. Initialize L by placing the initial search region in it. 2. DO WHILE L # (a) Remove the box X from L; (b) (Process X) Do one of the following: reject X; reduce the size of X; determine that X contains a unique critical point, then find the critical point to high accuracy. subdivide X to make it more likely to succeed at rejecting, reduc- ing, or verifying uniqueness. (c) Insert one or more boxes derived from X onto L, U or C, depend- ing on the size of the resulting box(es) from step 2b and whether the (possible) computational existence test in that step has determined a unique critical point. End Algorithm 1 Many details, such as stopping criteria and tolerances, are absent from Algo- rithm 1, which represents a general description. Such details differ in particular actual algorithms. A combination of several techniques is used in state-of-the-art interval global optimization codes to do step 2b of Algorithm 1. Algorithm 2 (Range Check and Critical Point Verification) 1. Input a box X and the current best rigorous upper bound 10 on the global minimum. 2. (Feasibility check; for constrained problems only) (a) (Exit if infeasibility is proven) DO for i = 1 to m: boxes in L are in general inserted in a particular order, depending on the actual algorithm</p><p>26 CHAPTER 2 i. Compute an enclosure (X) for the range of over X. ii. IF 0 ci(X) THEN discard X and EXIT. (b) Prove computationally, if possible, that there exists at least one feasi- ble point in X. 3. (Range check or "midpoint test") (a) Compute a lower bound on the range of over X. (b) IF > 10 THEN discard X and EXIT. 4. (Update the upper bound on the minimum.) IF the problem is uncon- strained or feasibility was proven in step 2b, THEN (a) Use interval arithmetic to compute an upper bound of the ob- jective function over X. (b) 5. ("monotonicity test") (a) Compute an enclosure of the range of over X. (Note: If X is "thin", i.e. if some bound constraints are active over X, then a reduced gradient can be used; see $2.3 and [32].) (b) IF 0 & THEN discard X and EXIT. 6. ("concavity test") If the Hessian cannot be positive definite anywhere in X THEN discard X and EXIT. 7. (Quadratic convergence and computational existence / uniqueness) Use an interval Newton method4 (with the Fritz-John conditions as in 3.5 in the constrained case) to possibly do one or more of the following: reduce the size of X; discard X; verify that a unique critical point exists in X. 8. (Bisection or geometric tessellation) If step 7 did not result in a sufficient change in X, then bisect X along a coordinate direction (or otherwise tessellate X), returning all resulting boxes for subsequent processing. End Algorithm 2 3 or reduced Hessian matrix, as in step 5 4 possibly in a subspace, as in steps 5 and 6</p><p>Constrained Global Optimization 27 Since techniques for constrained problems are somewhat more involved, step 2, checking for infeasibility and verifying feasibility, will be explained separately in $2.1. Step 3 is called the "midpoint test" because the upper bound is often ob- tained by evaluating at the midpoint vector of X, properly taking account of rounding errors for rigor. Of course, step 5 is called the "monotonicity test " since is monotone over X in the i-th variable if the i-th component of does not vanish over X. Improved techniques for carrying out step 6, checking non-convexity, are desir- able. Presently, sufficient conditions, such as checking the sign of the diagonal entries of an interval evaluation can be used. One method of verify- ing convexity appears as Theorem 14.1 in [15] and Lemma 2.7.2 in [54]. Also, Neumaier [49] has shown that every element matrix of an interval matrix A is positive-definite, provided some point matrix A E A is positive definite and A is regular according to Definition 3 of §3 below. This result can be sharpened as follows. Theorem 1 (Shi, [64, Appendix B]) If A E A is symmetric, A has p negative eigenvalues and A is regular, then every symmetric point matrix in A has p negative eigenvalues. Theorem 1 will allow a sharper concavity test. Interval global optimization algorithms, viewed abstractly, are similar to branch and bound algorithms that do not explicitly use interval arithmetic to bound ranges, such as that in [50, Ch. 6]. Interval global optimization algorithms differ among themselves in the ordering of the lists L, U and C in step 2c of Algorithm 1, and in how (and which) steps of Algorithm 2 are carried out. 1.1 Early and Simplified Algorithms Early algorithms worked only with the list L, without lists U and C. Also, although the processes in steps 3 through 7 of Algorithm 2 make actual imple- mentations practical and efficient, they are not an essential part of the branch and bound structure. In the early but well-known Moore / Skelboe algorithm, only the list L appears, and the boxes X E L are ordered in order of increasing In step 8 of Algorithm 2, X is bisected along the largest coordinate</p><p>28 CHAPTER 2 direction, and both progeny are placed in order in L. Steps 3 through 7 of Algorithm 2 are absent. When the algorithm is terminated, the first box in the list is taken to approximate the global minimizer. An algorithm attributed to Ichida [21] improves upon the Moore / Skelboe algorithm by including the midpoint test (step 3 of Algorithm 2) to avoid plac- ing boxes generated during bisection onto L if they cannot contain Additionally, the algorithm described in [21] contains a method for grouping together clusters of boxes corresponding to particular minimizers. Hansen's algorithms, described in [17], [18] and [19] generally use second-order information (step 7 of Algorithm 2) and other sophisticated techniques. How- ever an algorithm sometimes called "Hansen's algorithm" is a simplified version. In "Hansen's algorithm," L is ordered not in terms of the function, but in or- der of decreasing diameter (i.e. width of largest coordinate interval) of the X. Furthermore, in the midpoint test, the entire list L is culled (and not just the boxes that have just been produced by bisection) whenever a new is obtained. (We note that in Hansen's actual codes, as in the experiments in [66], the list is ordered such that the first box is the one with smallest lower bound on Hansen and Walster claim this is much better than ordering in terms of de- creasing diameter.) Various modifications of the list ordering, such as that in [54, $2.2.5.1], have appeared more recently. None of these simplified methods employs interval-Newton acceleration. Convergence properties of the Moore / Skelboe, Ichida and Hansen algorithms, as well as some numerical experiments with Hansen's algorithm are analyzed in [44]. A wide-ranging survey that concentrates on these methods (but also mentions some newer techniques) is the book [52]. 1.2 Recent Practical Algorithms More recent algorithms and practical implementations usually involve interval Newton methods for computational existence and uniqueness of critical points and for quadratic convergence properties. However, some successful newer al- gorithms are derivative-free, and concentrate on use of approximate optimizers, order in which the list is searched, properties of the inclusion function, or par- allelization.</p><p>Constrained Global Optimization 29 A thorough exposition of background, starting with the elements of interval arithmetic, and of numerous techniques for interval unconstrained optimiza- tion along with a substantial number of careful numerical experiments appears in Ratz [54]. Some of these ideas are implemented in the Pascal-XSC code described in [15]. Ratz, continuing development of his algorithms, has concentrated on better choice of coordinate in the bisection process of step 8 of Algorithm 2, and on splitting strategies, cf. [55]. Regarding bisection strategies, Ratz claims better success when choosing the coordinate to bisect according to the scaling rather than merely bisecting along the longest coordinate direction of X; cf. [54], pp. 41-42 and [6]. Convergence ofgeneralized bisection based global op- timization algorithms with this coordinate selection strategy is also proven in [6]. This scheme is related to the maximal smear scheme introduced in [30]. Box splitting is a process, first discussed by Hansen in relation to the interval Gauss-Seidel method, by which extended interval arithmetic in the sense of Kahan is used to obtain two disjoint boxes. If applied wherever possible, too many boxes are produced, thus slowing the overall branch and bound algorithm. Coordinate choice in bisection, box-splitting strategies, and the ordering in the list L can be crucial in an overall global optimization algorithm. Hansen's book [19] provides an informal description of many sophisticated tech- niques and heuristics for use in global optimization algorithms. Many examples are given, although thorough numerical experiments are absent. Good numer- ical experiments with an earlier optimization algorithm incorporating many of the same ideas appear in [66]. In [23] and [24], Jansson and Knüppel have presented a method without deriva- tives (no gradient test or interval Newton method), but with a sophisticated use of bisection and local optimization. In particular, a local optimization (to obtain an approximate optimizer) is performed at certain stages of the process, and the results are used to update Though heuristic, the algorithm performs well on many reasonably complicated functions, including non-differentiable ones, such as maximizing the smallest singular value of a matrix. The report [24] also contains a collection of test examples, along with numerical results and three-dimensional graphs of those (numerous) test problems that are two- variable functions. Jansson [25, $2.5] proposes a variant in which derivatives</p><p>30 CHAPTER 2 are used only in an interval Newton method to verify and sharpen bounds for approximate optima. This variant is carefully tested on forty test problems in [26]. In [3] Caprani, Godthaab, and Madsen also propose use of an approximate minimizer obtained through a local method with floating point arithmetic. In their algorithm, an approximate local minimizer is found, then a box X is constructed about this minimizer. An interval Newton method is then applied to X to determine existence or uniqueness of a critical point. If existence can be proven, X is expanded as much as possible, subject to success of the interval Newton method in verifying uniqueness, then X is removed from the region by cutting the complement of X into remaining boxes to be processed. The minimizer-inflation technique is related to "e-inflation" as in [57, p. 58] or [41] used to provide error bounds on approximate solutions to linear and nonlinear systems. It is illustrated in [3] that the Caprani/Godthaab/Madsen method parallelizes well. In [45], basic algorithms for non-differentiable and differentiable objective func- tions are reviewed, then a sophisticated coarse-grained algorithm for optimiza- tion on a distributed-memory multicomputer, implemented on a distributed system of workstations, is explained. In this algorithm, each processor shares a portion of the list L. The load is dynamically balanced as the computations proceed. The algorithm was programmed in C++, based on a system for in- terval arithmetic developed by Leclerc; an encapsulated explanation appears in [40]. The numerical experiments feature a very difficult parameter-fitting problem. In [10] and [11] Eriksson et al also study parallelization of an unconstrained global optimization algorithm, implemented on an Intel hypercube. Various load balancing strategies are compared on a set of six test problems, one of which was designed specifically to test different parallelization schemes. In [32], experimental results are reported for a FORTRAN-77 code containing techniques for the monotonicity test and iteration / verification, as well as use of a local optimization process for computing ("midpoint test "). The spe- cial preconditioners preconditioning techniques of [29] and [31] for the interval Gauss-Seidel method (a type of interval Newton method) in the optimization context, as well as a technique for handling bound constraints the tessellation are studied there5. A more flexible Fortran-90 code utilizing the 5 The latter two techniques are more fully explored in [54].</p><p>Constrained Global Optimization 31 Method 7 Midpoint Monotonicity Concavity Interval Paralleli- Use of Local Ref. Authors Test Test Test Newton sation Moore 7 [43] and Skelboe [65] Ichida yes 21 "Hansen's yes, and algorithm" to cull list Hansen's yes yes yes yes [19] actual Kearfott '92 yes yes yes yes 32 Rats yes yes yes yes yes [54] and [15] Jansson 7 yes yes yes 24 Caprani 7 [3] Godthaab / yes yes yes yes Madsen Hansen 7 subject Moore / yes yes yes yes of study Leclerc Eriksson yes yes yes subject of study Wolfe yes yes yes Table 1 Summary attributes of various global optimization algorithms system of [10] and including techniques for constrained problems is presently under development. Theoretical and empirical consequences of the order of the interval extension used to obtain are studied in [8] and [37]. However, exhaustive studies on a practical algorithm do not appear there. Some (but not all) of the attributes of the algorithms in this section and in are summarized in Table 1. Here, the label "Kearfott '92" refers to the code of [32]. "Hansen's actual" is used to denote the most recent algorithms of Hansen, described in [19] and forming the basis of the work in [45] and [40]. Blank spaces in the table indicate that the feature is not present. 1.3 Notation In the remainder of this paper, we will use the following notation. We will use boldface to denote intervals, lower case to denote scalar quantities, and upper case to denote vectors and matrices. We will use underscores to denote lower bounds of intervals and overscores to denote upper bounds of intervals. For components of vectors, we will use corresponding lower case letters. For example, we may have: X = X2, , ,</p><p>32 CHAPTER 2 where Xi = The notation X will denote a representative point, usually in the interval vector X. The magnitude of an interval is defined as = max The width of an interval is denoted by w(x) = The width of an interval vector X, denoted w(X), is defined component-wise. We use w(X) in the context of = The symbol denotes an interval extension of over X. Whenever is used, it will mean 1100. We will use calligraphic letters such as L, U and C, as above, to denote stacks and lists of boxes. Brackets [.] will be used to delimit both intervals and matrices and vectors. For example, we have the interval [1, and the interval vector [[1, 2], [3, 4]]'. Meanings should be clear from the context. The notation int(X) will be used to denote the topological interior of an interval vector X. Interval arithmetic will not be reviewed here, as numerous introductions, such as those in [1], [43], [48], [52] or even [28], exist. We will also assume familiarity with general concepts of numerical methods for constrained and unconstrained optimization, such as are found in [13]. 2 ON CONSTRAINED OPTIMIZATION PROBLEMS The book [52] contains an explanation of fundamental interval means of han- dling inequality constraints, while [19] contains an in-depth treatment of many interval techniques for both inequality and equality constraints. However, ex- tensive numerical results using these techniques have not been published. (See Table 2; blank spaces mean the feature is absent.) Handling of simple bound constraints through the tessellation process has been explored in [32] and [54]. In general, the computational effort for this technique</p>