Hamilton-Jacobi equations and other types of partial differential equa- tions of the first order are dealt with in many branches of mathematics, mechanics, and physics. These equations are usually nonlinear, and func- tions vital for the considered problems are not smooth enough to satisfy these equations in the classical sense. An example of such a situation can be provided by the value function of a differential game or an optimal control problem. It is known that at the points of differentiability this function satisfies the corresponding Hamilton-Jacobi-Isaacs-Bellman equation. On the other hand, it is well known that the value function is as a rule not everywhere differentiable and therefore is not a classical global solution. Thus in this case, as in many others where first-order PDE's are used, there arises necessity to introduce a notion of generalized solution and to develop theory and methods for constructing these solutions. In the 50s-70s, problems that involve nonsmooth solutions of first- order PDE's were considered by Bakhvalov, Evans, Fleming, Gel'fand, Godunov, Hopf, Kuznetzov, Ladyzhenskaya, Lax, Oleinik, Rozhdestven- ski1, Samarskii, Tikhonov, and other mathematicians. Among the inves- tigations of this period we should mention the results of S.N. Kruzhkov, which were obtained for Hamilton-Jacobi equation with convex Hamilto- nian. A review of the investigations of this period is beyond the limits of the present book. A sufficiently complete bibliography can be found in [58, 126, 128, 141].

Constraint Programming is a problem-solving paradigm that establishes a clear distinction between two pivotal aspects of a problem: (1) a precise definition of the constraints that define the problem to be solved and (2) the algorithms and heuristics enabling the selection of decisions to solve the problem. It is because of these capabilities that Constraint Programming is increasingly being employed as a problem-solving tool to solve scheduling problems. Hence the development of Constraint-Based Scheduling as a field of study. The aim of this book is to provide an overview of the most widely used Constraint-Based Scheduling techniques. Following the principles of Constraint Programming, the book consists of three distinct parts: The first chapter introduces the basic principles of Constraint Programming and provides a model of the constraints that are the most often encountered in scheduling problems. Chapters 2, 3, 4, and 5 are focused on the propagation of resource constraints, which usually are responsible for the "hardness" of the scheduling problem. Chapters 6, 7, and 8 are dedicated to the resolution of several scheduling problems. These examples illustrate the use and the practical efficiency of the constraint propagation methods of the previous chapters. They also show that besides constraint propagation, the exploration of the search space must be carefully designed, taking into account specific properties of the considered problem (e.g., dominance relations, symmetries, possible use of decomposition rules). Chapter 9 mentions various extensions of the model and presents promising research directions.

Shortly after the end of World War II high-speed digital computing machines were being developed. It was clear that the mathematical aspects of com putation needed to be reexamined in order to make efficient use of high-speed digital computers for mathematical computations. Accordingly, under the leadership of Min a Rees, John Curtiss, and others, an Institute for Numerical Analysis was set up at the University of California at Los Angeles under the sponsorship of the National Bureau of Standards. A similar institute was formed at the National Bureau of Standards in Washington, D. C. In 1949 J. Barkeley Rosser became Director of the group at UCLA for a period of two years. During this period we organized a seminar on the study of solu tions of simultaneous linear equations and on the determination of eigen values. G. Forsythe, W. Karush, C. Lanczos, T. Motzkin, L. J. Paige, and others attended this seminar. We discovered, for example, that even Gaus sian elimination was not well understood from a machine point of view and that no effective machine oriented elimination algorithm had been developed. During this period Lanczos developed his three-term relationship and I had the good fortune of suggesting the method of conjugate gradients. We dis covered afterward that the basic ideas underlying the two procedures are essentially the same. The concept of conjugacy was not new to me. In a joint paper with G. D."

The book of Professor Evtushenko describes both the theoretical foundations and the range of applications of many important methods for solving nonlinear programs. Particularly emphasized is their use for the solution of optimal control problems for ordinary differential equations. These methods were instrumented in a library of programs for an interactive system (DISO) at the Computing Center of the USSR Academy of Sciences, which can be used to solve a given complicated problem by a combination of appropriate methods in the interactive mode. Many examples show the strong as well the weak points of particular methods and illustrate the advantages gained by their combination. In fact, it is the central aim of the author to pOint out the necessity of using many techniques interactively, in order to solve more dif ficult problems. A noteworthy feature of the book for the Western reader is the frequently unorthodox analysis of many known methods in the great tradition of Russian mathematics. J. Stoer PREFACE Optimization methods are finding ever broader application in sci ence and engineering. Design engineers, automation and control systems specialists, physicists processing experimental data, eco nomists, as well as operations research specialists are beginning to employ them routinely in their work. The applications have in turn furthered vigorous development of computational techniques and engendered new directions of research. Practical implementa tion of many numerical methods of high computational complexity is now possible with the availability of high-speed large-memory digital computers."

Problems with multiple objectives and criteria are generally known as multiple criteria optimization or multiple criteria decision-making (MCDM) problems. So far, these types of problems have typically been modelled and solved by means of linear programming. However, many real-life phenomena are of a nonlinear nature, which is why we need tools for nonlinear programming capable of handling several conflicting or incommensurable objectives. In this case, methods of traditional single objective optimization and linear programming are not enough; we need new ways of thinking, new concepts, and new methods - nonlinear multiobjective optimization. Nonlinear Multiobjective Optimization provides an extensive, up-to-date, self-contained and consistent survey, review of the literature and of the state of the art on nonlinear (deterministic) multiobjective optimization, its methods, its theory and its background. The amount of literature on multiobjective optimization is immense. The treatment in this book is based on approximately 1500 publications in English printed mainly after the year 1980. Problems related to real-life applications often contain irregularities and nonsmoothnesses. The treatment of nondifferentiable multiobjective optimization in the literature is rather rare. For this reason, this book contains material about the possibilities, background, theory and methods of nondifferentiable multiobjective optimization as well. This book is intended for both researchers and students in the areas of (applied) mathematics, engineering, economics, operations research and management science; it is meant for both professionals and practitioners in many different fields of application. The intention has been to provide a consistent summary that may help in selecting an appropriate method for the problem to be solved. It is hoped the extensive bibliography will be of value to researchers.

Convexity of sets in linear spaces, and concavity and convexity of functions, lie at the root of beautiful theoretical results that are at the same time extremely useful in the analysis and solution of optimization problems, including problems of either single objective or multiple objectives. Not all of these results rely necessarily on convexity and concavity; some of the results can guarantee that each local optimum is also a global optimum, giving these methods broader application to a wider class of problems. Hence, the focus of the first part of the book is concerned with several types of generalized convex sets and generalized concave functions. In addition to their applicability to nonconvex optimization, these convex sets and generalized concave functions are used in the book's second part, where decision-making and optimization problems under uncertainty are investigated. Uncertainty in the problem data often cannot be avoided when dealing with practical problems. Errors occur in real-world data for a host of reasons. However, over the last thirty years, the fuzzy set approach has proved to be useful in these situations. It is this approach to optimization under uncertainty that is extensively used and studied in the second part of this book. Typically, the membership functions of fuzzy sets involved in such problems are neither concave nor convex. They are, however, often quasiconcave or concave in some generalized sense. This opens possibilities for application of results on generalized concavity to fuzzy optimization. Despite this obvious relation, applying the interface of these two areas has been limited to date. It is hoped that the combination of ideas and results from the field of generalized concavity on the one hand and fuzzy optimization on the other hand outlined and discussed in Generalized Concavity in Fuzzy Optimization and Decision Analysis will be of interest to both communities. Our aim is to broaden the classes of problems that the combination of these two areas can satisfactorily address and solve.

There have been significant developments in the theory and practice of combinatorial optimization in the last 15 years. This progress has been evidenced by a continuously increasing number of international and local conferences, books and papers in this area. This book is also another contribution to this burgeoning area of operations research and optimization. This volume contains the contributions of the participants of the recent NATO Ad vanced Study Institute, New Frontiers in the Theory and Practice of Combinatorial Op timization, which was held at the campus of Bilkent University, in Ankara, Turkey, July 16-29, 1990. In this conference, we brought many prominent researchers and young and promising scientists together to discuss current and future trends in the theory and prac tice of combinatorial optimization. The Bilkent campus was an excellent environment for such an undertaking. Being outside of Ankara, the capital of Turkey, Bilkent University gave the participants a great opportunity for exchanging ideas and discussing new theories and applications without much distraction. One of the primary goals of NATO ASIs is to bring together a group of scientists and research scientists primarily from the NATO countries for the dissemination of ad vanced scientific knowledge and the promotion of international contacts among scientists. We believe that we accomplished this mission very successfully by bringing together 15 prominent lecturers and 45 promising young scientists from 12 countries, in a university environment for 14 days of intense lectures, presentations and discussions.

One of the basic tenets of science is that deterministic systems are completely predictable-given the initial condition and the equations describing a system, the behavior of the system can be predicted 1 for all time. The discovery of chaotic systems has eliminated this viewpoint. Simply put, a chaotic system is a deterministic system that exhibits random behavior. Though identified as a robust phenomenon only twenty years ago, chaos has almost certainly been encountered by scientists and engi neers many times during the last century only to be dismissed as physical noise. Chaos is such a wide-spread phenomenon that it has now been reported in virtually every scientific discipline: astronomy, biology, biophysics, chemistry, engineering, geology, mathematics, medicine, meteorology, plasmas, physics, and even the social sci ences. It is no coincidence that during the same two decades in which chaos has grown into an independent field of research, computers have permeated society. It is, in fact, the wide availability of inex pensive computing power that has spurred much of the research in chaotic dynamics. The reason is simple: the computer can calculate a solution of a nonlinear system. This is no small feat. Unlike lin ear systems, where closed-form solutions can be written in terms of the system's eigenvalues and eigenvectors, few nonlinear systems and virtually no chaotic systems possess closed-form solutions."

While domain decomposition methods have a long history dating back well over one hundred years, it is only during the last decade that they have become a major tool in numerical analysis of partial differential equations. This monograph emphasizes domain decomposition methods in the context of so-called virtual optimal control problems and treats optimal control problems for partial differential equations and their decompositions using an all-at-once approach.

The English edition differs only slightly from the Russian original. The main struc tural difference is that all the material on the theory of finite noncooperative games has been collected in Chapter 2, with renumbering of the material of the remain ing chapters. New sections have been added in this chapter: devoted to general questions of equilibrium theory in nondegenerate games, subsections 3.9-3.17, by N.N. Vorob'ev, Jr.; and 4, by A.G. Chernyakov; and 5, by N.N. Vorob'ev, Jr., on the computational complexity of the process of finding equilibrium points in finite games. It should also be mentioned that subsections 3.12-3.14 in Chapter 1 were written by E.B. Yanovskaya especially for the Russian edition. The author regrets that the present edition does not reflect the important game-theoretical achievements presented in the splendid monographs by E. van Damme (on the refinement of equilibrium principles for finite games), as well as those by J.e. Harsanyi and R. Selten, and by W. Giith and B. Kalkofen (on equilibrium selection). When the Russian edition was being written, these direc tions in game theory had not yet attained their final form, which appeared only in quite recent monographs; the present author has had to resist the temptation of attempting to produce an elementary exposition of the new theories for the English edition; readers of this edition will find only brief mention of the new material."

Optimization in Quality Control presents a broad survey of the state of the art in optimization in quality, and focuses on industrial and national competitiveness. Each chapter has been carefully developed and refereed anonymously by experts in the area of optimization in quality control. Some of the topics covered in this volume include: * fundamentals of optimization techniques * contemporary approaches to optimization models in process control * economic design of control charts * determining optimal target values in multiple criteria economic selection models * examining quality improvement schemes by trading off between expected warranty servicing costs and increasing manufacturing costs * designing optimal inspection plans. This book will serve as an important reference source for academics, professionals and researchers.

This book is about time-domain modelling, stability, stabilization, control design and filtering for JTDS. It gives readers a thorough understanding of the basic mathematical analysis and fundamentals, offers a straightforward treatment of the different topics and provides broad coverage of the recent methodologies.

This book provides a systematic and comprehensive account of asymptotic sets and functions from which a broad and useful theory emerges in the areas of optimization and variational inequalities. A variety of motivations leads mathematicians to study questions about attainment of the infimum in a minimization problem and its stability, duality and minmax theorems, convexification of sets and functions, and maximal monotone maps. For each there is the central problem of handling unbounded situations. Such problems arise in theory but also within the development of numerical methods. The book focuses on the notions of asymptotic cones and associated asymptotic functions that provide a natural and unifying framework for the resolution of these types of problems. These notions have been used largely and traditionally in convex analysis, yet these concepts play a prominent and independent role in both convex and nonconvex analysis. This book covers convex and nonconvex problems, offering detailed analysis and techniques that go beyond traditional approaches. The book will serve as a useful reference and self-contained text for researchers and graduate students in the fields of modern optimization theory and nonlinear analysis.

The problem of obtaining dynamical models directly from an observed time-series occurs in many fields of application. There are a number of possible approaches to this problem. In this volume a number of such points of view are exposed: the statistical time series approach, a theory of guaranted performance, and finally a deterministic approximation approach. This volume is an out-growth of a number of get-togethers sponsered by the Systems and Decision Sciences group of the International Institute of Applied Systems Analysis (IIASA) in Laxenburg, Austria. The hospitality and support of this organization is gratefully acknowledged. Jan Willems Groningen, the Netherlands May 1989 TABLE OF CONTENTS Linear System Identification- A Survey page 1 M. Deistler A Tutorial on Hankel-Norm Approximation 26 K. Glover A Deterministic Approach to Approximate Modelling 49 C. Heij and J. C. Willems Identification - a Theory of Guaranteed Estimates 135 A. B. Kurzhanski Statistical Aspects of Model Selection 215 R. Shibata Index 241 Addresses of Authors 246 LINEAR SYSTEM IDENTIFICATION* A SURVEY M. DEISTLER Abstract In this paper we give an introductory survey on the theory of identification of (in general MIMO) linear systems from (discrete) time series data. The main parts are: Structure theory for linear systems, asymptotic properties of maximum likelihood type estimators, estimation of the dynamic specification by methods based on information criteria and finally, extensions and alternative approaches such as identification of unstable systems and errors-in-variables. Keywords Linear systems, parametrization, maximum likelihood estimation, information criteria, errors-in-variables.

Complementarity theory is a new domain in applied mathematics and is concerned with the study of complementarity problems. These problems represent a wide class of mathematical models related to optimization, game theory, economic engineering, mechanics, fluid mechanics, stochastic optimal control etc. The book is dedicated to the study of nonlinear complementarity problems by topological methods. Audience: Mathematicians, engineers, economists, specialists working in operations research and anybody interested in applied mathematics or in mathematical modeling.

As our title reveals, we focus on optimal control methods and applications relevant to linear dynamic economic systems in discrete-time variables. We deal only with discrete cases simply because economic data are available in discrete forms, hence realistic economic policies should be established in discrete-time structures. Though many books have been written on optimal control in engineering, we see few on discrete-type optimal control. More over, since economic models take slightly different forms than do engineer ing ones, we need a comprehensive, self-contained treatment of linear optimal control applicable to discrete-time economic systems. The present work is intended to fill this need from the standpoint of contemporary macroeconomic stabilization. The work is organized as follows. In Chapter 1 we demonstrate instru ment instability in an economic stabilization problem and thereby establish the motivation for our departure into the optimal control world. Chapter 2 provides fundamental concepts and propositions for controlling linear deterministic discrete-time systems, together with some economic applica tions and numerical methods. Our optimal control rules are in the form of feedback from known state variables of the preceding period. When state variables are not observable or are accessible only with observation errors, we must obtain appropriate proxies for these variables, which are called "observers" in deterministic cases or "filters" in stochastic circumstances. In Chapters 3 and 4, respectively, Luenberger observers and Kalman filters are discussed, developed, and applied in various directions. Noticing that a separation principle lies between observer (or filter) and controller (cf."

A unified approach is proposed for applied mechanics and optimal control theory. The Hamilton system methodology in analytical mechanics is used for eigenvalue problems, vibration theory, gyroscopic systems, structural mechanics, wave-guide, LQ control, Kalman filter, robust control etc. All aspects are described in the same unified methodology. Numerical methods for all these problems are provided and given in meta-language, which can be implemented easily on the computer. Precise integration methods both for initial value problems and for two-point boundary value problems are proposed, which result in the numerical solutions of computer precision. Key Features of the text include: -Unified approach based on Hamilton duality system theory and symplectic mathematics. -Gyroscopic system vibration, eigenvalue problems. -Canonical transformation applied to non-linear systems. -Pseudo-excitation method for structural random vibrations. -Precise integration of two-point boundary value problems. -Wave propagation along wave-guides, scattering. -Precise solution of Riccati differential equations. -Kalman filtering. -HINFINITY theory of control and filter.

During the last three decades, interest has increased significantly in the representation and manipulation of imprecision and uncertainty. Perhaps the most important technique in this area concerns fuzzy logic or the logic of fuzziness initiated by L. A. Zadeh in 1965. Since then, fuzzy logic has been incorporated into many areas of fundamental science and into the applied sciences. More importantly, it has been successful in the areas of expert systems and fuzzy control. The main body of this book consists of so-called IF-THEN rules, on which experts express their knowledge with respect to a certain domain of expertise. Fuzzy IF-THEN Rules in Computational Intelligence: Theory and Applications brings together contributions from leading global specialists who work in the domain of representation and processing of IF-THEN rules. This work gives special attention to fuzzy IF-THEN rules as they are being applied in computational intelligence. Included are theoretical developments and applications related to IF-THEN problems of propositional calculus, fuzzy predicate calculus, implementations of the generalized Modus Ponens, approximate reasoning, data mining and data transformation, techniques for complexity reduction, fuzzy linguistic modeling, large-scale application of fuzzy control, intelligent robotic control, and numerous other systems and practical applications. This book is an essential resource for engineers, mathematicians, and computer scientists working in fuzzy sets, soft computing, and of course, computational intelligence.

An introduction to the variational methods used to formulate and solve mathematical and physical problems, allowing the reader an insight into the systematic use of elementary (partial) convexity of differentiable functions in Euclidian space. By helping students directly characterize the solutions for many minimization problems, the text serves as a prelude to the field theory for sufficiency, laying as it does the groundwork for further explorations in mathematics, physics, mechanical and electrical engineering, as well as computer science.

My original introduction to this subject was through conservations, and ultimate ly joint work with C. A. Micchelli. I am grateful to him and to Profs. C. de Boor, E. W. Cheney, S. D. Fisher and A. A. Melkman who read various portions of the manuscript and whose suggestions were most helpful. Errors in accuracy and omissions are totally my responsibility. I would like to express my appreciation to the SERC of Great Britain and to the Department of Mathematics of the University of Lancaster for the year spent there during which large portions of the manuscript were written, and also to the European Research Office of the U.S. Army for its financial support of my research endeavors. Thanks are also due to Marion Marks who typed portions of the manuscript. Haifa, 1984 Allan Pinkus Table of Contents 1 Chapter I. Introduction . . . . . . . . Chapter II. Basic Properties of n-Widths . 9 1. Properties of d * * * * * * * * * * 9 n 15 2. Existence of Optimal Subspaces for d * n n 17 3. Properties of d * * * * * * 20 4. Properties of b * * * * * * n 5. Inequalities Between n-Widths 22 n 6. Duality Between d and d * * 27 n 7. n-Widths of Mappings of the Unit Ball 29 8. Some Relationships Between dn(T), dn(T) and bn(T) . 32 37 Notes and References . . . . . . . . . . . . . .

Mathematics is playing an ever more important role in the physical and biologi cal sciences, provoking a blurring of boundaries between scientific disciplines and a resurgence of interest in the modem as well as the classical techniques of applied mathematics. This renewal of interest, both in research and teaching, has led to the establishment of the series Texts in Applied Mathematics (TAM). The development of new courses is a natural consequence of a high level of excitement on the research frontier as newer techniques, such as numerical and symbolic computer systems, dynamical systems, and chaos, mix with and rein force the traditional methods of applied mathematics. Thus, the purpose of this textbook series is to meet the current and future needs of these advances and to encourage the teaching of new courses. TAM will publish textbooks suitable for use in advanced undergraduate and beginning graduate courses, and will complement the Applied Mathematics Sci ences (AMS) series, which will focus on advanced textbooks and research-level monographs. v Preface This textbook introduces the basic concepts and results of mathematical control and system theory. Based on courses that I have taught during the last 15 years, it presents its subject in a self-contained and elementary fashion. It is geared primarily to an audience consisting of mathematically mature advanced undergraduate or beginning graduate students. In addi tion, it can be used by engineering students interested in a rigorous, proof oriented systems course that goes beyond the classical frequency-domain material and more applied courses."

Ever since the discovery of the five platonic solids in ancient times, the study of symmetry and regularity has been one of the most fascinating aspects of mathematics. Quite often the arithmetical regularity properties of an object imply its uniqueness and the existence of many symmetries. This interplay between regularity and symmetry properties of graphs is the theme of this book. Starting from very elementary regularity properties, the concept of a distance-regular graph arises naturally as a common setting for regular graphs which are extremal in one sense or another. Several other important regular combinatorial structures are then shown to be equivalent to special families of distance-regular graphs. Other subjects of more general interest, such as regularity and extremal properties in graphs, association schemes, representations of graphs in euclidean space, groups and geometries of Lie type, groups acting on graphs, and codes are covered independently. Many new results and proofs and more than 750 references increase the encyclopaedic value of this book.

This monograph deals with various classes of deterministic and stochastic continuous time optimal control problems that are defined over unbounded time intervals. For these problems the performance criterion is described by an improper integral and it is possible that, when evaluated at a given admissible element, this criterion is unbounded. To cope with this divergence new optimality concepts, referred to here as overtaking optimality, weakly overtaking optimality, agreeable plans, etc. , have been proposed. The motivation for studying these problems arises primarily from the economic and biological sciences where models of this type arise naturally. Indeed, any bound placed on the time hori zon is artificial when one considers the evolution of the state of an economy or species. The responsibility for the introduction of this interesting class of problems rests with the economists who first studied them in the modeling of capital accumulation processes. Perhaps the earliest of these was F. Ramsey [152] who, in his seminal work on the theory of saving in 1928, considered a dynamic optimization model defined on an infinite time horizon. Briefly, this problem can be described as a Lagrange problem with unbounded time interval. The advent of modern control theory, particularly the formulation of the famous Maximum Principle of Pontryagin, has had a considerable impact on the treat ment of these models as well as optimization theory in general.

In the late forties, Mathematical Programming became a scientific discipline in its own right. Since then it has experienced a tremendous growth. Beginning with economic and military applications, it is now among the most important fields of applied mathematics with extensive use in engineering, natural sciences, economics, and biological sciences. The lively activity in this area is demonstrated by the fact that as early as 1949 the first "Symposium on Mathe- matical Programming" took place in Chicago. Since then mathematical programmers from all over the world have gath- ered at the intfrnational symposia of the Mathematical Programming Society roughly every three years to present their recent research, to exchange ideas with their colleagues and to learn about the latest developments in their own and related fields. In 1982, the XI. International Symposium on Mathematical Programming was held at the University of Bonn, W. Germany, from August 23 to 27. It was organized by the Institut fUr Okonometrie und Operations Re- search of the University of Bonn in collaboration with the Sonderforschungs- bereich 21 of the Deutsche Forschungsgemeinschaft. This volume constitutes part of the outgrowth of this symposium and docu- ments its scientific activities. Part I of the book contains information about the symposium, welcoming addresses, lists of committees and sponsors and a brief review about the Ful- kerson Prize and the Dantzig Prize which were awarded during the opening ceremony.

Conditional Monte Carlo: Gradient Estimation and Optimization Applications deals with various gradient estimation techniques of perturbation analysis based on the use of conditional expectation. The primary setting is discrete-event stochastic simulation. This book presents applications to queueing and inventory, and to other diverse areas such as financial derivatives, pricing and statistical quality control. To researchers already in the area, this book offers a unified perspective and adequately summarizes the state of the art. To researchers new to the area, this book offers a more systematic and accessible means of understanding the techniques without having to scour through the immense literature and learn a new set of notation with each paper. To practitioners, this book provides a number of diverse application areas that makes the intuition accessible without having to fully commit to understanding all the theoretical niceties. In sum, the objectives of this monograph are two-fold: to bring together many of the interesting developments in perturbation analysis based on conditioning under a more unified framework, and to illustrate the diversity of applications to which these techniques can be applied. Conditional Monte Carlo: Gradient Estimation and Optimization Applications is suitable as a secondary text for graduate level courses on stochastic simulations, and as a reference for researchers and practitioners in industry.