136
Uncertainty Modeling using Fuzzy Arithmetic and Sparse Grids Von der Fakultät Mathematik und Physik der Universität Stuttgart zur Erlangung der Würde eines Doktors der Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung Vorgelegt von W. Andreas Klimke aus Blaubeuren Hauptberichter: Prof. Dr. B. Wohlmuth Mitberichter: Prof. Dr. H.-J. Bungartz Prof. Dr. L. Gaul Tag der mündlichen Prüfung: 16. November 2005 Institut für Angewandte Analysis und Numerische Simulation Universität Stuttgart 2006

Uncertainty Modeling using Fuzzy Arithmetic and Sparse Grids · Uncertainty Modeling using Fuzzy Arithmetic and Sparse Grids Von der Fakultät Mathematik und Physik der Universität

  • Upload
    others

  • View
    40

  • Download
    0

Embed Size (px)

Citation preview

Uncertainty Modeling usingFuzzy Arithmetic and Sparse Grids

Von der Fakultät Mathematik und Physik der Universität Stuttgartzur Erlangung der Würde eines Doktors der

Naturwissenschaften (Dr. rer. nat.) genehmigte Abhandlung

Vorgelegt von

W. Andreas Klimke

aus Blaubeuren

Hauptberichter: Prof. Dr. B. Wohlmuth

Mitberichter: Prof. Dr. H.-J. BungartzProf. Dr. L. Gaul

Tag der mündlichen Prüfung: 16. November 2005

Institut für Angewandte Analysis und Numerische SimulationUniversität Stuttgart

2006

D93 (Diss. Universität Stuttgart)

Acknowledgments

Presented in this work are the results of my research activities at the chair “Numerische Mathe-matik für Höchstleistungsrechner” of the Institute für Angewandte Analysis und NumerischeSimulation, Universität Stuttgart.

I would like to thank Prof. Dr. rer. nat. Barbara Wohlmuth for her mentoring, support, andenduring encouragement of my research work. While I enjoyed quite a bit of freedom withregards to my scientific pursuits, I consider myself very lucky to having been able to drawfrom the excellent training I had received under her supervision, as well as her vast knowledgein the field of applied mathematics. I am especially indebted to PD Dr. habil. Michael Hanssfor igniting in me the spark of excitement for the topics of uncertainty modeling in general andfuzzy set theory in particular. Many invaluable discussions have followed since then. It is mypleasure to thank Dr. Ronaldo Nunes for many stimulating discussions on the application offuzzy methods to problems in vibration engineering. Special thanks I owe to Prof. Dr. Hans-Joachim Bungartz, for a stimulating discussion on sparse grids that very much impacted thisthesis. I am also very grateful to Prof. Dr. Lothar Gaul and Prof. Dr. Bungartz for participatingin the thesis commitee, and to Dr. Hanss for participating in the oral defense.

During my employment at the Institut für Angewandte Analysis und Numerische Simulation,I greatly enjoyed the inspiring and cooperative atmosphere. I would especially like to thank mycolleagues Bernd Flemisch, Stefan Hüeber, and most of all, Bishnu Lamichhane, for providingtheir profound advice on mathematical and other topics related to this thesis.

Furthermore, I record my distinct appreciation to DaimlerChrysler AG for providing somefinite element models that were used in the applications section of this thesis, as well as INTESGmbH for providing the required licenses of the finite element software PERMAS in this con-text.

Finally, I would like to express my deepest gratitude to my wife Grace, who has supportedme in all my professional endeavors. She gave me not only her constant moral support and en-couragement, but also took actively part in this work by carefully proofreading this document.

Stuttgart, December 2005 Andreas Klimke

iii

Contents

Notation vii

Abstract ix

Zusammenfassung xi

1 Introduction 1

2 Fuzzy Set Theory and Fuzzy Calculus 32.1 Fuzzy set theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.1 Fuzzy sets and membership functions . . . . . . . . . . . . . . . . . . 32.1.2 Support and alpha-cuts of fuzzy sets . . . . . . . . . . . . . . . . . . . 42.1.3 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.4 Fuzzy numbers and fuzzy intervals . . . . . . . . . . . . . . . . . . . . 52.1.5 Parametric representation of fuzzy numbers . . . . . . . . . . . . . . . 62.1.6 Measuring the error of a fuzzy number . . . . . . . . . . . . . . . . . . 8

2.2 Extension principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Common approaches to fuzzy calculus . . . . . . . . . . . . . . . . . . . . . . 14

2.3.1 Global optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.2 Vertex method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.3 Transformation method . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Computing expensive fuzzy-valued functions . . . . . . . . . . . . . . . . . . 21

3 Tensor Product and Sparse Grid Interpolation 233.1 Univariate interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.1 Piecewise linear splines . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.2 Lagrangian polynomial interpolation . . . . . . . . . . . . . . . . . . . 24

3.2 Multivariate tensor product interpolation . . . . . . . . . . . . . . . . . . . . . 303.2.1 The general tensor product interpolation formula . . . . . . . . . . . . 323.2.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3 Sparse grid interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.3.1 Smolyak’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.3.2 Piecewise multilinear basis functions . . . . . . . . . . . . . . . . . . 363.3.3 Polynomial basis functions . . . . . . . . . . . . . . . . . . . . . . . . 403.3.4 From univariate nodal to multivariate hierarchical . . . . . . . . . . . . 413.3.5 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.3.6 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

v

Contents

3.3.7 Performance results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.4 Dimension-adaptive tensor-product interpolation . . . . . . . . . . . . . . . . 59

3.4.1 Generalized sparse grid interpolation . . . . . . . . . . . . . . . . . . 593.4.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613.4.3 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.4.4 Performance results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4 Fuzzy Calculus using Sparse Grids 734.1 Discretization of the fuzzy numbers . . . . . . . . . . . . . . . . . . . . . . . 734.2 Summary of the procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.3 Computing the extension principle solution . . . . . . . . . . . . . . . . . . . 744.4 Applying incomplete global search methods . . . . . . . . . . . . . . . . . . . 754.5 Applying global search methods based on interval arithmetic . . . . . . . . . . 77

4.5.1 The minimal inclusion function . . . . . . . . . . . . . . . . . . . . . 784.5.2 The natural inclusion function . . . . . . . . . . . . . . . . . . . . . . 784.5.3 The centered inclusion function . . . . . . . . . . . . . . . . . . . . . 804.5.4 Computing the inclusion of the gradient vector . . . . . . . . . . . . . 824.5.5 A branch-and-bound method . . . . . . . . . . . . . . . . . . . . . . . 83

4.6 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.6.1 Performance of the optimization algorithms . . . . . . . . . . . . . . . 844.6.2 Overall performance results . . . . . . . . . . . . . . . . . . . . . . . 86

4.7 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5 Applications 915.1 Dynamic systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.1.1 Infectious disease modeling under uncertainty . . . . . . . . . . . . . . 915.1.2 Computation of a multibody mechanism under uncertainty . . . . . . . 95

5.2 Vibration engineering: Frequency response function envelopes . . . . . . . . . 965.2.1 Numerical realization . . . . . . . . . . . . . . . . . . . . . . . . . . . 985.2.2 Estimating FRF envelopes using the spectral element method . . . . . . 995.2.3 Response curve envelopes of large-scale finite element models . . . . . 106

6 Concluding Remarks 117

Bibliography 119

vi

Notation

Fuzzy sets

A Fuzzy set

µA Membership function of fuzzy set A

Aα α-cut of A

A0 compact support or 0-cut of A

p Fuzzy number or fuzzy interval

〈m,α,β 〉TFN Triangular fuzzy number with peak value m, left-hand spread α and right-hand spread β

〈m,σ ,r〉QGFN Quasi-Gaussian fuzzy number with peak value m, standard deviation σ andcut-off factor r

Ωα Interval box formed by the Cartesian product of several connected α-cuts.

Ω,Ω0 Support box

Interpolation and sparse grids

C, C0 Space of continuous functions

Cn Space of n times continuously partially differentiable functions

Cn(Ω) Cn on the domain ΩPn Space of polynomials of degree n

Πn( f ) Polynomial interpolant of degree n of f

Πhn( f ) Piecewise polynomial interpolant with maximum interval length h

ΠXn ( f ) Polynomial interpolant with set of support nodes X

p∗n( f ) Best approximation polynomial of degree n of f

Λ Lebesgue constant

‖·‖∞ Maximum norm

× Cartesian product operator

⊗ Tensor product operator, see Section 3.2.1

d Dimension or number of variables

/0 Empty set

# Cardinality (number of elements) of a set

vii

Notation

∪, ∩, \ Set union, intersection, and minus, respectively

n Sparse grid interpolation depth, n ∈ N0

A( f ) Sparse grid interpolant of f

Aq,d( f ) Regular sparse grid interpolant of dimension d and q = n+d

ASk( f ) Dimension-adaptive interpolant with set of multi-indices Sk

Hq,d Sparse grid of dimension d and depth n on [0,1]d, q = n+d

∆H Subset of sparse grid points

H(Ω) Sparse grid scaled to ΩHCC Clenshaw-Curtis sparse grid

HNB No-boundary-nodes sparse grid

HM Maximum-norm-based sparse grid

HLI Sparse grids for piecewise multilinear interpolation, LI = CC,M,NBHCGL Chebyshev-Gauss-Lobatto sparse grid

i Multi-index (i1, . . . , id) with |i| = i1 + · · ·+ idS, ∆S Set or subset of multi-indices, respectively

n(i) Number of grid points of grid corresponding to i

w Hierarchical surplus or interval width (depending on context)

Z Set of hierarchical surpluses

A Set of active indices in dimension-adaptive algorithm

O Set of passive indices in dimension-adaptive algorithm

ω Degree of dimensional adaptivity

N Number of sparse grid points

Interval analysis and optimization

x Point vector

[a,b] Interval scalar

I Interval vector (or box)

∆ Step-length control parameter

[ f ]∗ Minimal interval inclusion function of f

[ f ]n Natural inclusion function

[ f ]c Mixed centered inclusion function

viii

Abstract

In today’s thorough understanding of physical, economic, and other complex systems, de-veloping mathematical models and performing numerical simulations play a key role. Withincreasing capabilities of modern computers, the models are becoming more sophisticated andrealistic. This not only has raised our expectations of solving practical problems more andmore accurately, but has also resulted in the need to gather much more detailed data.

However, one observes that an often large part of the required data cannot be obtained pre-cisely, but rather exhibits some degree of uncertainty. Various sources of uncertainty are en-countered in this context. Physical systems, for instance, are based on model parameters thatare usually obtained via measurements, which cannot be exact by nature. It is thus recog-nized that quantifying, analyzing, and controlling uncertainty is essential to more reliable andmore realistic results in modeling and computer simulation. Unfortunately, methods to treatuncertainty require extensive computational resources. Monte Carlo methods, for example, re-quire a large number of samples to achieve good results. Obtaining not only probabilistic butpossibilistic results (i.e., the worst-case bounds of the results for a given set of uncertain param-eters) requires the solution of global optimization problems, where each uncertain parameterbecomes an independent variable of the problem. Solving a multivariate global optimization ismostly an np-hard problem in which the complexity often grows exponentially with the prob-lem dimension. Therefore, specifically problems with a large number of uncertain parameters,i.e. high-dimensional problems, pose an enormous challenge to current research.

In this thesis, the uncertain parameters are modeled using fuzzy set theory, which representsa well-studied approach to uncertainty management that places emphasis on gradations of pos-sibility rather than on randomness and probability, such as stochastic methods. Computing withfuzzy sets is performed with the so-called extension principle that can extend any real-valuedfunction to a function of fuzzy numbers.

As the main contribution of this work, it is shown how sparse grid interpolation can be usedin the fuzzy set-based uncertainty modeling process. The most important property of sparsegrid interpolation methods is the fact that they scale well to higher-dimensional problems. In-creasingly accurate, error-controlled interpolants are constructed adaptively from mere modelevaluations up to a desired estimated accuracy or up to a maximum number of function evalu-ations. These interpolants are then employed as surrogate functions in the computation of theextension principle, which requires multiple global optimization problems to be solved. Ap-plications in dynamic systems modeling and vibration engineering illustrate the wide potentialof the novel approach.

ix

Zusammenfassung

Zum heutigen gründlichen Verständnis physikalischer, ökonomischer, und anderer komplexerSysteme tragen die Entwicklung von mathematischen Modellen und deren numerische Simu-lation in entscheidender Weise bei. Mit wachsenden Fähigkeiten moderner Computer werdendiese Modelle immer ausgefeilter und realistischer. Dies hat dazu geführt, dass unsere Erwar-tungen, praktische Probleme immer genauer lösen zu können, gewachsen sind, aber auch dazu,dass die Eingangsdaten der Modelle immer besser erfasst werden müssen.

Mittlerweile stellt man jedoch fest, dass ein oft großer Anteil der benötigten Daten nichtpräzise ermittelt werden kann, sondern stattdessen mit einem gewissen Grad an Unsicherheitbehaftet ist. Verschiedene Ursachen können hierbei Unsicherheit hervorrufen. Beispielsweisebasieren physikalische Systeme auf Modellparametern, die man mit Hilfe von Messreihen be-stimmt, die von Natur aus nicht exakt sein können. Dies führt zu der Erkenntnis, dass es vonessenzieller Bedeutung ist, Unsicherheiten zu quantifizieren, zu analysieren und zu begrenzenum verlässlichere und realistischere Ergebnisse bei der Modellierung und Computersimulati-on zu erhalten. Unglücklicherweise stellen Methoden, die Unsicherheiten in die Berechnungeinbeziehen, beträchtliche Anforderungen an die Rechenleistung. Als Beispiel seien hier Mon-te Carlo Methoden genannt, die eine große Anzahl an Zufallsstichproben erfordern um guteErgebnisse zu liefern. Wenn man jedoch nicht nur probabilistische sondern possibilistische Er-gebnisse anstrebt (d.h. den ungünstigsten möglichen Fall für eine gegebene Menge unsichererEingangsgrößen), wird die Lösung eines globalen Optimierungsproblems notwendig, wobeijeder unsicherer Parameter als freie Variable in das Problem eingeht. Bei einem globalen, mul-tivariaten Optimierungsproblem handelt es sich meist um ein sogenanntes np-hartes Problem,dessen Komplexität oft exponentiell mit der Problemdimension anwächst. Daher stellen insbe-sondere Probleme mit einer großen Zahl unsicherer Eingangsparameter, d.h. hochdimensionaleProbleme, eine enorme Herausforderung an die heutige Wissenschaft dar.

In dieser Arbeit werden die unsicheren Parameter mit Hilfe der Theorie unscharfer Mengen(engl. fuzzy sets) modelliert, die einen gut untersuchten Ansatz für das Unsicherheitsmanage-ment darstellt. Die Methodik stellt Abstufungen der Möglichkeit in den Vordergrund, im Ge-gensatz zu stochastischen Ansätzen, bei denen Zufall und Wahrscheinlichkeit im Mittelpunktstehen. Das Rechnen mit unscharfen Mengen wird über das sogenannte Erweiterungsprinzipdurchgeführt, mit dessen Hilfe beliebige reellwertige Funktionen auf Funktionen unscharferZahlen verallgemeinert werden können.

Als zentraler Beitrag dieser Arbeit wird aufgezeigt, wie die Interpolation auf dünnen Git-tern (engl. sparse grid interpolation) im Rahmen der Unsicherheitsmodellierung verwendetwerden kann. Die wichtigste Eigenschaft dünner Gitter stellt deren gute Skalierbarkeit auf hö-herdimensionale Probleme dar. Zunehmend genaue Interpolierende können unter Abschätzungdes Fehlers adaptiv aus reinen Funktionsauswertungen konstruiert werden, bis hin zu einer vor-gegebenen Fehlertoleranz oder einer maximalen Zahl an Auswertungen. Diese Interpolanten

xi

Zusammenfassung

werden dann als Ersatzfunktionen bei der Berechnung des Erweiterungsprinzips eingesetzt,welches das Lösen mehrerer globaler Optimierungsprobleme erfordert. Anwendungen im Be-reich dynamischer Systeme und der Schwingungstechnik illustrieren das breite Anwendungs-potenzial des neuen Verfahrens.

xii

1 Introduction

In today’s thorough understanding of physical, economic, and other complex systems, devel-oping mathematical models and performing numerical simulations play a key role. With in-creasing computation and storage capabilities of modern computers, the models are becomingmore sophisticated and realistic. This has raised our expectations of solving practical problemsmore and more accurately, but also resulted in the need to gather much more detailed data.This trend has been recognized not recently, but at least 20 years ago (see, e.g., [23]). Fur-thermore, it has been observed that an often large part of the required data cannot be obtainedprecisely, but rather exhibits some degree of uncertainty. Various sources of uncertainty areencountered. Physical systems, for instance, are based on model parameters that are usuallyobtained via measurements, which cannot be exact by nature. Going one step further, Zadeheven challenges the usefulness of highly precise and complex systems: “as the complexity ofa system increases, our ability to make precise and yet significant statement about its behaviordiminishes until a threshold is reached beyond which precision and significance (or relevance)become almost mutually exclusive characteristics” [86].

Traditionally, probability theory is used to deal with uncertain information. In case of dy-namic systems, for instance, stochastic processes are used to model phenomena observed innature that are to some extend unpredictable. Resulting probabilities can be estimated from asufficiently large sample of realizations (outcomes) of some random variables and stochasticprocesses [69]. However, as Dubois and Prade point out, there are important characteristicsof uncertainty that cannot be handled appropriately by probability theory [23], mainly sinceits key concepts are based on principles of randomness, which is not necessarily the source ofuncertainty.

Consequently, other concepts have been proposed. Interval analysis, developed by Moore in1966 [61], provides the means to deal with imprecise data, and is extensively used in toleranceanalysis. Here, imprecision refers to a lack of knowledge about the value of a parameter thatis in turn expressed as a crisp tolerance interval. The main advantage of interval analysis isits capability to provide guaranteed bounds on the results for given interval-valued input data.This fact implies the important distinction of a result to be possible rather than probable.

Another approach to handling uncertainty and imprecision emerged from the work of LotfiA. Zadeh. In 1965, he proposed fuzzy set theory [85], which led to the development of fuzzylogic as well as possibility theory for dealing with forms of uncertainty which are inherentlynon-statistical in nature. An illustrative example is given by Zadeh in the foreword of [6]:“John’s income is between fifty and sixty thousand dollars. In this case, the interval [50K,60K]is the possibility distribution of John’s income, that is, the set of possible values. . . . There isno randomness in this example, the possibility distribution is a fuzzy set and possibility is anumber in the interval [0,1]”. From this example, it is evident that possibility theory can beinterpreted as a generalization of interval analysis. Instead of producing single intervals as

1

1 Introduction

outputs, probability theory based on fuzzy sets permits gradations of possibility.While interval analysis has found its place in application areas such as parameter estimation,

robust control, and robotics [44], being able to provide numerical methods for finding all solu-tions within guaranteed bounds, it has long been argued whether possibility theory and fuzzyset based methods are an appropriate basis for addressing uncertainty. Maglaras et al. mentionseveral different views on these issues, and present a detailed experimental comparison [59],concluding that it very much depends on the considered problem itself.

One important drawback of handling uncertainty with possibilistic approaches has been thelack of accurate and universal tools for computing with fuzzy sets. This is an important reasonwhy fuzzy set-based methods, despite their merits, have not been applied to many complexreal-world problems. Zadeh’s extension principle forms the theoretical basis of fuzzy calculus,extending real-valued functions to functions of fuzzy numbers. In practice, the implementationof fuzzy calculus turns out to be a problem of nonlinear programming, which is commonlydifficult to solve and also computationally expensive.

This work proposes a new approach to computing functions of fuzzy numbers centeredaround sparse grid interpolation. It is especially well-suited for expensive multivariate ob-jective models. Since the approach requires only real-valued function evaluations of the objec-tive model, it can be immediately applied to a large class of problems. The remainder of thedocument is organized as follows:

Chapter 2 reviews the relevant parts of fuzzy set theory, and common approaches to theimplementation of Zadeh’s extension principle. The advantages as well as the limitations ofthese methods are discussed.

Chapter 3 gives an introduction to sparse grid interpolation. We start with nodal and hie-rarchical interpolation in the univariate case. Then, multivariate interpolation based on tensorproducts and the necessary modifications to obtain the sparse grid algorithm are briefly re-viewed. Finally, a dimension-adaptive approach due to Hegland [39] and Gerstner and Griebel[26] is discussed and further improved. All along the chapter, numerical examples illustratethe presented algorithms.

In Chapter 4, the new approach to fuzzy calculus based on sparse grids is introduced. Theapproach can be split into two main parts: the approximation of the objective function viasparse grid interpolation, and a subsequent optimization of the interpolant for multiple searchboxes. Depending on the required accuracy, either piecewise multilinear or higher order poly-nomial basis functions are suggested for the interpolation part of the method. Suitable opti-mization algorithms are discussed. The performance of the different approaches are demon-strated by numerical examples.

Chapter 5 presents applications in dynamic systems and vibration engineering.Chapter 6 provides some concluding remarks.

2

2 Fuzzy Set Theory and Fuzzy Calculus

2.1 Fuzzy set theory

In the first section of this chapter, the basic notions of fuzzy set theory are introduced. Whilea lot of different concepts known from real analysis have been extended to fuzzy set theory,only the concepts relevant to the focus of this work are mentioned here. For a more detaileddiscussion of the basics of fuzzy set theory, see, for instance, [10, pp. 14–57], [22, pp. 9–35],[37, ch. 1], [60, ch. 2].

2.1.1 Fuzzy sets and membership functions

Definition 2.1 (conventional set). Let X be a set of classical objects called the space. Ac-cording to Cantor, a set A is defined as a collection of objects or elements x ∈ X with certainproperties. Each single element can either belong or not belong to the set A, A ⊆ X . Thus, setscarry an ordering or structuring character. Membership of an element x in A can be viewed asa characteristic function µA : X →0,1 with

µA(x) =

1 if and only if x ∈ A,

0 otherwise.(2.1)

Definition 2.2 (fuzzy set). Let X be a space whose generic elements are denoted by x, and letµA : X → M ⊆ [0,1] be a characteristic function that maps X to the membership space M. Then,a fuzzy set is uniquely defined by the following set of pairs

A =(x,µA(x)) | x ∈ X

. (2.2)

µA is often called membership function. If M = 0,1, A is called non-fuzzy or crisp. Ifsupx∈X µA(x) = 1, the fuzzy set A is called normal. In the following, it is assumed that allfuzzy sets are normalized.

Example 2.1. Fig. 2.1 shows some examples for membership functions. The according defi-nitions of the fuzzy sets are

(a) A =(x,µA(x)) | µA(x) = (1+(x−5)4)−1, x ∈ R

,

(b) B =(x,µB(x)) | x ∈ R

, with

µB(x) =

(x−2)/2 if 2 ≤ x < 4,

1 if 4 ≤ x < 5,

(8− x)/3 if 5 ≤ x < 8,

0 otherwise,

3

2 Fuzzy Set Theory and Fuzzy Calculus

(c) C =(2,0);(3,0.25);(4,0.75);(5,1);(6,0.5);(7,0)

,

(d) D =(5,1);(x,0) | x ∈R,x 6= 5

. Remark. Since D contains only a single value x0 with

µD(x) > 0, and µD(x0) = 1, x0 is called singleton. Furthermore, D is a crisp set, sinceM = 0,1.

50

1

4 50

1

2 3 4 5 6 70

1

50

1

PSfrag replacements

µ(x)

xxxx

(a) (b) (c) (d)

Figure 2.1: Examples for fuzzy sets

2.1.2 Support and alpha-cuts of fuzzy sets

Definition 2.3 (support). The support of a fuzzy set A is the crisp set of all x ∈ X such thatµA > 0, i.e.

supp(A) =

x | µA(x) > 0,x ∈ X. (2.3)

Definition 2.4 (α-cut). Let A be a fuzzy set with A =(x,µA(x)),x ∈ X

. Then, the crisp set

Aα withAα =

x | µA(x) ≥ α, x ∈ X , 0 < α ≤ 1

(2.4)

is called α-cut or α-level set of A.

Definition 2.5 (compact support). In addition to the support and the α-cuts, it is useful forcomputational reasons to also define the compact support of a fuzzy set A as the closed interval

A0 =[

inf(supp(A)),sup(supp(A))]. (2.5)

Obviously, this definition is only useful if the support supp(A) is bounded. We refer to A0 asthe 0-cut of A.

Example 2.2. For the fuzzy sets defined in Example 2.1, the support and some α-cuts aregiven below.

(a) supp(A) = R, since µA(x) > 0 for all x ∈ X ,X = R.A1 = 5; A0.5 = x | 4 ≤ x ≤ 6,x ∈ R, or in interval notation: A0.5 = [4,6].

4

2.1 Fuzzy set theory

(b) supp(B) = x | 2 < x < 8,x ∈ R = (2,8)B1 = [4,5]; B0.5 = [3,6.5]; B0 = [2,8].

(c) supp(C) = 3,4,5,6. C1 = 5; C0.5 = 4,5,6; C0 = [3,6].

(d) supp(D) = 5. D1 = D0.5 = 5; D0 = [5,5] = 5.

2.1.3 Convexity

Unlike in the conventional set theory, convexity of fuzzy sets refers to properties of the mem-bership function rather than to the support of a fuzzy set.

Definition 2.6. A fuzzy set A =(x,µA(x)),x ∈ X

is convex, if for all a,b,c ∈ X with a ≤ b ≤

c,µA(a) ≤ µA(b) or µA(c) ≤ µA(b). (2.6)

Alternatively, a fuzzy set is convex if all α-level sets are convex in the conventional set-theoretic sense, i.e. if all α-level sets are connected.

Example 2.3. All fuzzy sets of Example 2.1 are convex. The fuzzy set E depicted in Fig. 2.2is not convex, since µE(a) > µE(b) and µE(c) > µE(b).

Figure 2.2: Example of a non-convex fuzzyset

0

1

PSfrag replacements µE(a)

µE(b)

µE(c)

xa b c

2.1.4 Fuzzy numbers and fuzzy intervals

While most set-theoretic operations (e.g. union, intersection, etc., see references given above)can be performed on convex and non-convex fuzzy sets, it is important to introduce the conceptsof fuzzy numbers and fuzzy intervals as a sound basis for performing arithmetic computationswith fuzzy sets.

Definition 2.7 (fuzzy number). A convex, normalized fuzzy set p over the set of real numbersR is called fuzzy number, if there exists exactly one real number m with µ p = 1, and themembership function µ p(x) is at least piecewise continuous. The point m is called peak valueof p.

5

2 Fuzzy Set Theory and Fuzzy Calculus

Definition 2.8 (fuzzy interval). A convex, normalized fuzzy set p over the set of real numbersR is called fuzzy interval, if there exist two real numbers m1,m2 such that ∀ x ∈ [m1,m2],µ p(x) = 1, and the membership function µ p(x) is at least piecewise continuous.

Example 2.4. We consider again the fuzzy sets from Example 2.1. A is a fuzzy number, sincethe membership function is continuous and there is exactly one point m = 5 with µA = 1. B is afuzzy interval with [m1,m2] = [4,5]. The fuzzy sets C and D do not classify as fuzzy numbersor fuzzy intervals.

2.1.5 Parametric representation of fuzzy numbers

For the definition of fuzzy numbers and intervals of common shape, it is convenient to introducea simpler notation than the set-based notation of Definition 2.2. Dubois and Prade [22] describea good parametric representation of fuzzy numbers and intervals that can be obtained by usingtwo reference (or shape) functions, which we describe in the following.

Definition 2.9 (shape function). A function f : R+0 → [0,1] is called shape function if f has

the following properties:

(a) f is monotonic decreasing in [0,∞),

(b) f (0) = 1, and

(c) f (1) = 0 or limx→∞

f (x) = 0.

Definition 2.10 (LR fuzzy number). A fuzzy number p is called LR fuzzy number if two shapefunctions L (left) and R (right) with three parameters m ∈ R, α ∈ R

+, and β ∈ R+ exist such

that

∀ x : µ p(x) =

L(

m−xα)

if x < m1 if x = m

R(

x−mβ

)if x > m

. (2.7)

m is called the peak value or mean value, α and β are called the left-hand spread and theright-hand spread. A short notation of an LR fuzzy number p is then given by

p = 〈m,α,β 〉LR. (2.8)

Definition 2.11 (LR fuzzy interval). A fuzzy number p is called LR fuzzy interval if two shapefunctions L (left) and R (right) with four parameters m1,m1 ∈ R, α ∈ R

+, and β ∈ R+ exist

such that

∀ x : µ p(x) =

L(

m−xα)

if x < m11 if x ∈ [m1,m2]

R(

x−mβ

)if x > m2

. (2.9)

[m1,m2] is called the peak interval, m1,m2 are called the lower and upper modal value, respec-tively.

6

2.1 Fuzzy set theory

Triangular fuzzy numbers (TFN) If p is of triangular form, the shape functions are given to

L(u) = R(u) = max(0,1−u), (2.10)

and the resulting fuzzy number is called triangular fuzzy number, denoted by the triplet

p = 〈m,α,β 〉TFN. (2.11)

This triplet of type LR should not be confused with the definition of triangular fuzzy numbersaccording to Kaufmann and Gupta [46]. For α = β , the TFN is symmetric, otherwise semi-symmetric (since L(u) = R(u)).

Trapezoidal fuzzy intervals (TFI) If the shape functions of p are given by Eq. (2.10), and pis a fuzzy interval, p is called trapezoidal fuzzy interval denoted by the quadruplet

p = 〈m1,m2,α,β 〉TFI. (2.12)

Example 2.5. Examples for a symmetric TFN p = 〈4,2,2〉 and a semi-symmetric TFN q =〈4,1,3〉 are shown in Fig. 2.3, (a) and (b), respectively. An example for a trapezoidal fuzzyinterval is the fuzzy set B of Example 2.1, which can be denoted by b = 〈4,5,2,3〉TFI.

Figure 2.3: Examples for triangular fuzzynumbers; (a) symmetric, (b)semi-symmetric

2 4 60

1

3 4 70

1

PSfrag replacements

µ(x)

xx

(a) (b)

Gaussian fuzzy numbers (GFN) Since uncertain parameters often carry an empirically de-termined uncertainty range, Gaussian shape functions are often considered a practical assump-tion. The Gaussian (or normal) density function [9, pp. 131–142],[29] of probability theoryis

f (x) = C exp

(−1

2(m− x)2

σ 2

)(2.13)

with the constant scaling factor C = 1/(σ√

2π) to satisfy the important property of a probabil-ity density function

∞∫

−∞

f (x)dx = 1. (2.14)

7

2 Fuzzy Set Theory and Fuzzy Calculus

The membership function of a GFN, however, can usually not satisfy this equality to unity,since we set C = 1 instead to meet the definition requirements of a fuzzy number, which de-mands that µ p(m) = 1. In LR notation, the shape functions therefore become

L(u) = R(u) = exp

(−1

2u2)

. (2.15)

The left- and right-hand spread α and β of the so-defined membership function are equal tothe distance σ of the points of inflection to the peak value m. The GFN p can be denoted

p = 〈m,σ ,σ〉GFN = 〈m,σ〉GFN. (2.16)

Remark. In probability theory, σ represents the standard deviation of a random variable withthe probability density function f (x). Within the context of GFNs, σ is often still referred to asthe standard deviation although the term no longer applies in a strict sense, since the definitionof the variance and the standard deviation depend on the property (2.14).

Quasi-Gaussian fuzzy numbers (QGFN) [35] Gaussian fuzzy numbers do not have a com-pact (bounded) support. This is disadvantageous for numerical treatment because a decompo-sition of the GFN in intervals results in an unbounded interval for membership level µ p(x) = 0.To avoid this difficulty, one can bound the support by letting

L(u) = R(u) =

exp(−1

2 u2)

if |m− x| ≤ rσ0 if |m− x| > rσ ,

(2.17)

with r ∈ R+. To uniquely define QGFN’s, we use the parameter triplet

p = 〈m,σ ,r〉QGFN. (2.18)

Remark. Unlike Gaussian fuzzy numbers, the membership functions of a QGFN is not con-tinuous but only piecewise continuous.

Example 2.6. A Gaussian fuzzy number p = 〈4,1〉GFN and a quasi-Gaussian fuzzy numberq = 〈4,1,3〉QGFN are shown in Fig. 2.4, (a) and (b).

2.1.6 Measuring the error of a fuzzy number

Most methods that perform computations with fuzzy numbers and intervals produce only ap-proximations of the exact fuzzy-valued solution. Therefore, the question arises on how tomeasure the error of the result.

In publications by Giachetti and Young [27, 28], error measures were given by comparingthe approximation and the actual result separately for the left and the right segment of thefuzzy numbers for a given α-level α ∈ [0,1]. If we denote p as the actual result and p∗ as the

approximation with [a(α),b(α)] and [a(α)∗ ,b(α)

∗ ], respectively, as the intervals at a given α-level,we get the absolute error ε to

ε(α)left = |a(α)−a(α)

∗ | and ε(α)right = |b(α)−b(α)

∗ |. (2.19)

8

2.1 Fuzzy set theory

Figure 2.4: (a) Gaussian fuzzy number, (b)quasi-Gaussian fuzzy number

3 4 50

1

1 4 5 70

1

PSfrag replacements

µ(x)

xx

σσ

(a) (b)

This measure can also be interpreted as the distance to the left ∆(α)left = ε(α)

left and distance to the

right ∆(α)right = ε(α)

right of two intervals of confidence [46]. Adding both measures gives the distance

∆(α) = ∆(α)left + ∆(α)

right. By integrating over all membership levels α ∈ [0,1], one can obtain thedistance between two fuzzy numbers. In our case, we interpret the distance (not normalized asin [46]) as the absolute error

ε =

1∫

α=0

∆(α) dα (2.20)

=

1∫

α=0

(|a(α)−a(α)

∗ |+ |b(α)−b(α)∗ |)

dα. (2.21)

A more meaningful measure is the relative error, since the magnitude of the error has to berelated to the magnitude and spread of the fuzzy number. We divide by the area of the fuzzynumber to obtain the relative error e

e = ε/area(p) (2.22)

with

area(p) =

1∫

α=0

(b(α)−a(α)) dα. (2.23)

p must not be crisp, since the area of a crisp number is zero.The error e has the following properties:

(a) e ≥ 0

(b) (p∗ = p) → e = 0

(c) If p∗ is a crisp number with the singleton p, and the peak value of p is equal to p, e = 1.

For fuzzy numbers in discrete representation, we can obtain a continuous membership func-tion through piecewise linear interpolation. To compute the error measures, we can use thetrapezoidal integration rule.

9

2 Fuzzy Set Theory and Fuzzy Calculus

2.2 Extension principle

Zadeh’s extension principle [87] forms the theoretical basis of almost all methods for com-puting with fuzzy sets. It extends functions of real numbers to fuzzy-valued functions in aconsistent way. Although other ways of extending real calculus to fuzzy calculus have beenproposed (see [22, pp. 37–38] for examples), Zadeh’s extension principle has become widelyaccepted. A very thorough review of the extension principle including many illustrating exam-ples can be found in [60].

Definition 2.12 (extension principle). Zadeh’s extension principle extends functions of realnumbers to fuzzy-valued functions. Let A1, . . . , Ad be d fuzzy sets with the membership func-tions µ1, . . . ,µd defined on the spaces X1, . . . ,Xd , respectively. Let f : X1×·· ·×Xd →Y be theobjective function that maps the space X1 ×·· ·×Xd to the space Y , i.e. y = f (x1, . . . ,xd) andy ∈ Y . Then, the fuzzy image B can be obtained by the formulae

B = (y,µB(y)) | y = f (x1, . . . ,xd), (x1, . . . ,xd) ∈ X1×·· ·×Xd,

with

π(x1, . . . ,xd) = minµ1(x1), . . . ,µd(xd), (2.24)

µB(y) =

supy= f (x1,...,xd)

π(x1, . . . ,xd), if ∃ y = f (x1, . . . ,xd)

0 otherwise.

Example 2.7. To illustrate the extension principle, we consider a simple function of two vari-ables y = f (x1,x2) = 1

10 x1x2, f : R2 → R. Let p1 = 〈2,3,1,2〉TFI and p2 = 〈4,1,3〉QGFN befuzzy intervals. To compute the fuzzy-valued result q of the fuzzy extension of f , we couldproceed as illustrated in Fig. 2.5. We start with computing π(x1,x2) = min(µ1(x1),µ2(x2)) fora sufficiently fine grid with x1,x2 ∈ [0,8]. This leads to the filled contour plot in the center ofFig. 2.5. Now, we compute the range of the objective function f for x1,x2 ∈ [0,8] to [0,6.4](here, this is trivial since f is monotonic increasing). Finally, we proceed by selecting a discretevalue yh ∈ [0,6.4], and by computing the supremum

sup(π(x1,x2) | f (x1,x2) = yh).

This can by visualized by adding the contour lines where f = yh into the contour plot ofFig. 2.5. In the plot, we show the contour lines with yh ∈ 1

2 ,1, 32 ,2, 5

2 ,3, 72 ,4,5,6. We find the

value of the membership function of the result µq(yh) where π(x1,x2), restricted to the contourline yh = f (x1,x2), attains its maximum (e.g. marked by a circle in the plot for yh = 2.5).

Practical considerations From a practical point of view, computing fuzzy functions withthe formulation of the extension principle is difficult due to several reasons:

• Obtaining the range of the function for the region of interest, as we have done in theabove example, is in general very difficult. One must solve global optimization problemsto find the lower and the upper bound of the range.

10

2.2 Extension principle

• Computing the supremum of π under the restriction y = f (x1, . . . ,xd) poses another prob-lem, since it represents a global optimization problem with a nonlinear, nonconvex con-straint on the free variables x1, . . . ,xd .

• Finally, it is not trivial to select a proper distribution of the discrete points yh in caseof nonlinear objective functions. In the above example, for instance, the equidistantdistribution of points yh ∈ 1

2 ,1, 32 ,2, 5

2 ,3, 72 ,4 produced five points on the upper branch

of the fuzzy-valued result, but only one point was sampled on the left branch.

Some of these difficulties can be efficiently addressed by an alternative formulation of theextension principle, which is equivalent under some weak assumptions on the objective func-tion as well as the fuzzy-valued inputs.

Theorem 2.1. If the fuzzy sets A1, . . . , Ad of the extension principle are fuzzy intervals withcompact support, and the objective function f : X1 × ·· · × Xd → Y is continuous, then thefollowing formulation is equivalent to Eqs. (2.24).

B = (y,µB(y)) | y ∈ Y, with

µB(y) =

supα | y ∈ Bα if y ∈ B0,

0 otherwise,(2.25)

Bα =[

minx∈Ωα

f (x) , maxx∈Ωα

f (x)], 0 ≤ α ≤ 1.

In Eq. (2.25), Ωα = (A1)α × ·· ·× (Ad)α , 0 ≤ α ≤ 1 denote the interval boxes formed by theα-cuts (A1)α , . . .(Ad)α .

Proof. See [13].

Example 2.8. Consider again the problem from Example 2.7. We illustrate the alternativeformulation of the extension principle by means of Fig. 2.6. First, we discretize the fuzzyinput parameters pi, i = 1,2, into some α-cuts (pi)αh to form the boxes Ωαh . Here, we useαh ∈ 0,0.5,1. Thus, we obtain the three boxes Ω0, Ω0.5, and Ω1, which are shown in theplot. Since the α-cut (p2)1 is a singleton, Ω1 is degenerated to a line. Then, we compute theupper and the lower bound [aαh,bαh] of the α-cuts qαh of the fuzzy result q by solving theglobal optimization problems

min(x1,x2)∈Ωαh

f (x1,x2) and max(x1,x2)∈Ωαh

f (x1,x2). (2.26)

Since f is monotonic increasing with respect to x1 and x2 for the objective range, optimizing fis trivial. We can visualize this by adding a contour plot of f (x1,x2) to Fig. 2.6. Obviously, theminimum and the maximum of f for the interval boxes are attained at the lower-left and theupper-right corners of the boxes. From the values qαh , we can directly obtain an approximationof the membership function of the result µq, which is also shown in the figure.

11

2 Fuzzy Set Theory and Fuzzy Calculus

0 1 2 3 5 80

0.5

1

00.510

1

4

7

8

0 0.5 1

1

2

3

4

5

6

0 0.5 10

1

2

3

4

5

6

PSfrag replacements

p1

µ 1(x

1)

x1

x1p2

µ2(x2)

x 2x 2

π(x1,x2)

y = f (x1,x2) q

y

µq(y)

Figure 2.5: Illustration of the extension principle

0 1 2 3 5 80

0.5

1

00.510

1

4

7

8

0

1

2

3

4

5

6minmax

0 0.5 10

1

2

3

4

5

6

PSfrag replacements

p1

µ 1(x

1)

x1

x1p2

µ2(x2)

x 2x 2

q

y

µq(y)

y = f (x1,x2)

Figure 2.6: Illustration of the alternative formulation of the extension principle

12

2.2 Extension principle

Remark. The alternative formulation of Eq. (2.25) is still very general. Non-convex fuzzysets can be treated by splitting the fuzzy sets into its convex parts, and applying Eq. (2.25)repeatedly. Only in case of discontinuous objective functions, the results differ, since the fuzzyresult can become non-convex, i.e. the resulting α-level sets are no longer connected andthus not representable by intervals. However, the α-cuts of the correct fuzzy result are propersubsets of the Bα computed with the alternative formulation Eq. (2.25) (see the followingexample).

Example 2.9. In this example, we consider the fuzzy extension q = f (p) of a discontinuousunivariate function f : R → R,

f (x) =

x if x ≤ 1

x+1 if x > 1,

with p = 〈2,2,2〉TFN. The fuzzy result q according to the extension principle as well as theproper inclusion [q] according to the alternative formulation are shown in Fig. 2.7.

−1 0 1 2 3 4 50

0.5

1

−1 0 1 2 3 4 5−1

0

1

2

3

4

5

6minmax

0 0.5 1−1

0

1

2

3

4

5

6

0 0.5 1−1

0

1

2

3

4

5

6

PSfrag replacements

p

µ p(x

)

x

x

q

[q]

µq(y)µq(y)

y = f (x) q

yyy

µq(y)

Figure 2.7: Difference between extension principle formulations, f discontinuous

Unfortunately, even with the alternative formulation, computing fuzzy functions is still ahighly complex task, since multiple global optimization problems must be solved. Only in caseof monotonicity, the optimization problems can be solved efficiently. However, this obviouslyrequires that the objective function is known to be monotonic within the objective range, which

13

2 Fuzzy Set Theory and Fuzzy Calculus

is not known a priori in most cases. Several methods have been proposed to implement theextension principle, most of them based on the alternative formulation. A review of themfollows in the next section.

2.3 Common approaches to fuzzy calculus

We start with a brief review of existing methods implementing fuzzy calculus. We can clas-sify these methods into two categories, which we will refer to as classical fuzzy arithmeticand constrained fuzzy arithmetic. The classical category includes fuzzy arithmetic based onLR-fuzzy numbers according to Dubois and Prade [22], fuzzy arithmetic based on intervalarithmetic according to Kaufmann and Gupta [46], or similar variations (e.g. [28]). Theyprovide a way to compute fuzzy-valued expressions in a manageable way in terms of com-putational complexity. These methods, however, have one important common characteristic,which turns out to be a serious drawback: Each variable is considered independently in eachoccurrence, even if the same variable occurs multiple times in a given expression. This canlead to a large overestimation of the result, which has been rigorously demonstrated (see, forinstance, [20, 35, 56, 83, 84]). Methods of the constrained category avoid the overestimationeffect of the classical methods by directly computing the extension principle solution. Forinstance, one can apply global search methods by employing branch-and-bound algorithmsbased on interval arithmetic [34, 44, 61]. Dong and Shah [20] suggested a non-overestimatingapproach, the so-called vertex method. In its initial version, the algorithm was only applica-ble to monotonic functions. An improved algorithm was presented by Wood et al. [83]. Inaddition to a reduction of the complexity of the vertex method in certain cases, it includedan enhancement to correctly compute non-monotonic functions. Both algorithms require anadditional routine to locate internal extrema, which can be done either analytically or numeri-cally with an algorithm suited for global optimization of non-linear functions. More recently,the transformation method was proposed by Hanss [35, 36] as a practical approach to evaluatefuzzy-parameterized models without requiring an external optimization routine. Additionally,Hanss’ method provides a sensitivity analysis framework [35, 38]. Further implementations ofconstrained fuzzy arithmetic were presented in [62, 84].

In the following, we give a brief review of the most important methods of the constrainedcategory that avoid the overestimation effect.

2.3.1 Global optimization

A very important approach to implementing the extension principle is to directly solve thealternative formulation Eq. (2.25) for a sufficiently large number of α-cuts by global optimiza-tion.

Summary Global optimization methods can be classified according to the degree of rigorthat is applied during the solution process [64]:

• An incomplete method uses intelligent heuristics for searching, but cannot guarantee con-vergence to the global optimum. The simplest incomplete search method is the multiple

14

2.3 Common approaches to fuzzy calculus

random start method, which consists of performing local optimizations from randomstart points, hoping that one of them lies in the basin of attraction of the global optimum.In general, incomplete search methods can be further categorized into deterministic andstochastic methods. Other examples for incomplete global search methods are [64] localdescend techniques (these include multiple random start, tunneling methods), responsesurface techniques (these include Bayesian stochastic methods), nonmonotonic searchtechniques (these include simulated annealing), and ensemble methods (these includegenetic algorithms).

• An asymptotically complete method reaches a global optimum either with certainty orwith probability one, but it is not able to provide a stopping criterium (i.e. it has nomeans to know when a global optimum has been found).

Asymptotically complete methods are usually applied to problems where only local in-formation is available (i.e. only function, gradient, or Hessian evaluations at singlepoints). The density theorem [82] provides the necessary condition for a method basedon local information to be convergent:

Theorem 2.2 (Density theorem). Any method based on local information only that con-verges for every continuous function f to a global minimizer in a feasible domain Ωmust produce a sequence of points x1,x2, . . . that is dense in Ω.

According to [64], three good asymptotically complete methods exist: the DIRECT al-gorithm [45], multilevel coordinate search [42], and LGO [68]. The latter three methodsemploy branching techniques to achieve efficiency. Branching means that the searchdomain is split recursively into sub-domains (usually boxes). At least one function eval-uation is performed for each of the sub-domains. Boxes that are likely to improve thecurrently best found point are split earlier than other boxes. However, appropriate split-ting rules ensure that every box is split eventually such that the density theorem is satis-fied. The general transformation method (see Section 2.3.3.1) could be classified as anasymptotically complete method – it represents a variant of a full grid search producinga dense sequence of points, but no stopping criteria are provided.

• A complete method is guaranteed to find a global optimum within some tolerances withina finite amount of work, assuming exact computations. Complete methods are usuallybased on branch and bound techniques. In addition to the branching principle, i.e. split-ting the search domain, the bounding rule allows to reduce sub-boxes in size or eliminatethem without changing the set of feasible points. This can only be done reliably by us-ing some kind of global information. In this context, global information means that theobjective function is available in a form that allows one to obtain guaranteed bounds onthe function values, the gradients, or the Hessian for not only local points but semilocalregions, e.g. entire boxes. Interval analysis [34, 44, 61] extends classical analysis in itsability to provide existence and optimality conditions for pre-specified semilocal regions[64]. It is therefore an essential part of complete global search methods, such as BARON[74, 75] and αBB [2, 3].

15

2 Fuzzy Set Theory and Fuzzy Calculus

• A rigorous method reaches a global minimum with certainty and within given error tol-erances even in the presence of rounding errors (expect in near-degenerate cases wherethe tolerances may be exceeded). Rigorous interval analysis can guarantee correct resultsby outward rounding. Examples are the branch and bound solvers GlobSol [47, 48] andNumerica [40].

2.3.2 Vertex method

Summary The vertex method due to Dong and Shah [20] is a classical method that is stillwidely used in practice, although often in slightly modified form (e.g. the level interval algo-rithm [83], the reduced transformation method (see Section 2.3.3.2), or the short transformationmethod [19]). It is based on the alternative formulation of the extension principle, Eq. (2.25).It represents a generalization of the fuzzy weighted averages algorithm (FWA), which was pro-posed by Dong and Wong [21] to compute the weighted average of fuzzy numbers. The methodrequires real-valued function evaluations only. The first part of the method consists of discretiz-ing the fuzzy-valued inputs into α-cuts. Permutations of the lower and the upper bounds of theα-level sets are formed to obtain the corner points (“vertices”) of the d-dimensional boxesΩα in Eq. 2.25. If the objective function is monotonic with respect to all input parameters inthe region Ω0, these points suffice to correctly compute the resulting α-cuts. Otherwise, it issuggested to conduct an extreme point analysis, and include the extreme points in the set ofconsidered vertices.

Applicability The vertex method is directly applicable to continuous functions that are mono-tonic with respect to all variables for the considered base box. Convex fuzzy sets with boundedsupport may be used as inputs. The suggested extreme point analysis, however, is not suffi-cient to guarantee correct results in case of non-monotonic functions, as will be illustrated inExample 2.10.

Implementation In case of functions that are continuous in the interval box formed by thecompact supports of the fuzzy input parameters pi, i = 1, . . . ,d, and also no extreme pointsexist in this region (including the boundaries), then the following steps are conducted:

(a) Discretize the fuzzy input parameters pi into (m + 1) α-cuts (pi)α j , 0 ≤ α j ≤ 1, j =0, . . . ,m. Form d-dimensional interval boxes Ωα j = (p1)α j ×·· ·× (pd)α j .

(b) For each α j, the corner points of the interval boxes Ωα j are denoted as the vertices ck,k = 1, . . . ,2d . Evaluate the objective function f at these points and obtain 2d valueszk = f (ck).

(c) For each α j, compute the resulting α-cut by

qα j =[

mink

zk,maxk

zk]. (2.27)

16

2.3 Common approaches to fuzzy calculus

If there exist extreme points within the region Ω0, then add the extreme points into the sets ofvertices. Suppose there are n extreme points in Ωα j , then determine these extreme points El ,l = 1, . . . ,n, and replace Eq. 2.27 by

qα j =[

mink,l

zk, f (El),maxk,l

zk, f (El)]. (2.28)

If the objective function is not monotonic, the vertex method may produce incorrect resultsas already observed by Wood et al. [83]. It is not sufficient to consider additionally onlyextreme points in the region Ω0, since the global minima and maxima that must be determinedaccording to Eq. (2.25) may also lie at other points on the boundaries of each Ωα j . This isillustrated by the following example.

Example 2.10. Consider the Example 5 of [20], where f : R2 → R with f (x1,x2) = x2

1 +x2

2 − 4x1 + 4 is extended. Let the fuzzy input parameters be given by p1 = 〈3,2,1〉TFN andp2 = 〈0,1,1〉TFN. There is one extreme point E1 = (2,0) with f (E1) = 0 in Ω0 = [1,4]× [−1,1],since

∂ f∂x1

= 2x1 −4 = 0, x1 = 2, and

∂ f∂x2

= 2x2 = 0, x2 = 0.

There are n = 2d = 4 vertices for each α-cut.Considering the α-cut α = 0, the vertices are c1 = (1,−1), c2 = (1,1), c3 = (4,−1), c4 =

(4,1), and by evaluating f (ci), z = (2,2,5,5). E1 ∈ Ω0, thus, the extreme points should beadded to the set of vertices. By Eq. (2.28), we obtain the α-level set

q0 = [min2,2,5,5,0,max2,2,5,5,0] = [0,5],

of the fuzzy result q, which is correct.However, considering the α-cut α = 0.75, for instance, gives an incorrect result. With

Ω0.75 = [2.5,3.25]× [−0.25,0.25], the four vertices are c1 = (2.5,−0.25), c2 = (2.5,0.25),c3 = (3.25,−0.25), c4 = (3.25,0.25), and z = (0.3125,0.3125,1.625,1.625). E1 /∈ Ω0.75,therefore by Eq. (2.27),

q0.75 = [min0.3125,1.625,max0.3125,1.625] = [0.3125,1.625],

which is incorrect (correct would be the interval [0.25,1.625]). The global minimizer of ffor the region Ω0.75 lies at the point P = (2.5,0) with f (P) = 0.25, which is not consideredby the vertex method. Similarly, in this example, wrong results are obtained for all qα with0.5 < α < 1.

Complexity In case of functions that are monotonic with respect to all input parameterswithin the base interval box Ω0, the computational complexity is governed by the numberof function evaluations N, which grows linearly with the number of considered α-cuts m andexponentially with the dimension d, i.e. N = m2d . In case of non-monotonic functions, the

17

2 Fuzzy Set Theory and Fuzzy Calculus

complexity can strongly depend on the extreme point analysis, since locating possibly multi-ple local extreme points with an automatic algorithm is neither performed by standard localoptimization routines (which commonly locate one local extremum), nor by global optimiza-tion routines (which locate only global extrema). Apart from that, we suggest not to apply thevertex method in this case due to the described erroneous results that can occur.

2.3.3 Transformation method

Summary The transformation method due to Hanss [35] is an implementation of the exten-sion principle that first discretizes the fuzzy numbers into α-cuts, and then again discretizesthe α-cut intervals into sets of points. By doing so, the evaluation of the objective function canbe performed using real-valued function evaluations only, which makes the method widely ap-plicable. Depending on the characteristics of the objective function, three different versions ofthe transformation method have been proposed: general, reduced, or extended. In the follow-ing, we describe the reduced and the general form; the extended version [36] is not explicitlydiscussed here, since it only slightly improves the complexity of the general form. Since thehigh number of required function evaluations are the method’s main drawback, several im-provements have been suggested [19, 49, 50].

2.3.3.1 General transformation method

Applicability The general transformation method is applicable to a large class of functions,including only piecewise continuous functions (in this case, the convex inclusion of the fuzzyresult is approximated). The function may be non-monotonic. However, the number of fuzzyinput parameters should be small, about d ≤ 5. Only fuzzy numbers are suitable as inputs.

Implementation We are briefly recalling the implementation of the transformation methodas discussed in [35]. We will adhere to the same notation.

With the general transformation method, each fuzzy parameter pi, i = 1, . . . ,d is first being

decomposed into α-cuts, leading to a set Pi of (m + 1) intervals X ( j)i , j = 0,1, . . . ,m, of the

form

Pi =

X (0)i ,X (1)

i , . . . ,X (m)i

(2.29)

with

X ( j)i =

[a( j)

i ,b( j)i

], a( j)

i ≤ b( j)i , i = 1,2, . . . ,n , j = 0,1, . . . ,m . (2.30)

The µ-axis is subdivided into m segments, equally spaced by ∆α = 1/m. The (m + 1) α-cutsα j are then given by

µ j =j

m , j = 0,1, . . . ,m . (2.31)

For an illustration of the decomposition, see Fig. 2.8.

18

2.3 Common approaches to fuzzy calculus

Figure 2.8: Decomposition of the ith uncer-tain parameter into intervals

PSfrag replacements

0

1

xi

µpi(xi)

∆αα j

α j+1

a( j)i b( j)

i

pi

xi

The intervals of each level of membership µ j, j = 0,1, . . . ,m, can now be transformed into

arrays X ( j)i of the following form:

X ( j)i =

((m+1− j)i−1 (m+1− j) tuples︷ ︸︸ ︷

γ( j)1,i ,γ

( j)2,i . . . ,γ( j)

(m+1− j),i, . . . ,γ( j)1,i ,γ

( j)2,i . . . ,γ( j)

(m+1− j),i

)(2.32)

withγ( j)

l,i =(c( j)

l,i , . . . ,c( j)l,i

)︸ ︷︷ ︸

(m+1− j)d−i elements

(2.33)

and

c( j)l,i =

a( j)i for l = 1 and j = 0,1, . . . ,m ,

12

(c( j+1)

l−1,i + c( j+1)l,i

)for l = 2,3, . . . ,m− j and j = 0,1, . . . ,m−2 ,

b( j)i for l = m− j +1 and j = 0,1, . . . ,m ,

(2.34)

Note that a( j)i and b( j)

i are the lower and upper bounds of the interval X ( j)i at the membership

level µ j for the ith uncertain model parameter.Assuming that the objective model is given by a function f : Rd → R with

q = f (p1, p2, . . . , pd) , (2.35)

its estimation is then carried out by evaluating the expression separately at each of the entriesof the arrays using the conventional arithmetic for crisp numbers. Thus, if the output q ofthe system can be expressed in its decomposed and transformed forms by the arrays Z( j),j = 0,1, . . . ,m, the kth element k z( j) of the array Z( j) is given by

kz( j) = f(

kx( j)1 , kx( j)

2 , . . . , kx( j)d

), (2.36)

where kx( j)i denotes the kth element of the array X ( j)

i . Finally, the fuzzy-valued result q of theproblem can be achieved in its decomposed form

Z( j) =[a( j),b( j)] , j = 0,1, . . .,m , (2.37)

19

2 Fuzzy Set Theory and Fuzzy Calculus

by re-transforming the arrays Z( j) according to the recursive formulae

a( j) = mink

(a( j+1), k z( j)

)

b( j) = maxk

(b( j+1), kz( j)

) , j = 0,1, . . . ,m−1 , (2.38)

anda(m) = min

k

(k z(m)

)= max

k

(k z(m)

)= b(m) . (2.39)

Complexity The cost of the general transformation method is governed by the number offunction evaluations N. The transformation and retransformation of the arrays can be per-formed in O(N). Since for each membership level α j, the transformed arrays X ( j)

i have(m+1− j)d entries, N is given by

N =m

∑j=0

(m+1− j)d =m+1

∑k=1

kd. (2.40)

Thus, the number of required function evaluations grows exponentially with the dimension d.This makes the general transformation method inapplicable to higher dimensional problems.A five-dimensional problem d = 5, with the discretization parameter m = 10, for example,already requires 381876 function evaluations.

2.3.3.2 Reduced transformation method

Applicability The reduced transformation method is only applicable to functions that aremonotonic with respect to all input parameters for the considered support box. The objectivefunction may be only piecewise continuous and non-differentiable (in this case, the convexinclusion of the fuzzy result is approximated). The reduced version can be used in conjunctionwith both fuzzy numbers and fuzzy intervals.

Implementation Compared to the general transformation method, the discretization of the α-cuts only considers the left and the right bound of the interval, since for monotonic functions,the extrema can only lie at permutations formed by the interval end points. This simplifies theformulae (2.32)–(2.34) to

X ( j)i =

(2i−1 pairs︷ ︸︸ ︷

γ( j)1,i ,γ

( j)2,i ,γ

( j)1,i ,γ

( j)2,i , . . . ,γ

( j)1,i ,γ

( j)2,i

)(2.41)

withγ( j)

1,i =(

a ji , . . . ,a

( j)i︸ ︷︷ ︸

2d−i elements

), γ( j)

2,i =(

b ji , . . . ,b

( j)i︸ ︷︷ ︸

2d−i elements

). (2.42)

The evaluation of the objective function and the re-transformation is performed in the sameway as with the general transformation method.

20

2.4 Computing expensive fuzzy-valued functions

Complexity The cost of the reduced method is governed by the number of function evalu-ations N. The transformation and re-transformation of the arrays can be performed in O(N).

Since for each membership level α j, the transformed arrays X ( j)i have 2d entries, N is given by

N =m

∑j=0

2d = (m+1)2d. (2.43)

2.4 Computing expensive fuzzy-valued functions

In real-world applications, the objective models and functions that are to be extended to fuzzy-valued inputs are expensive multivariate functions, which usually exhibit at least some of thefollowing characteristics:

(a) A single real-valued function evaluation requires a significant amount of computing timein the order of seconds, minutes or even hours.

(b) The model evaluation involves a numerical procedure to obtain the solution, e.g. solvingan ordinary or partial differential equation.

(c) The function is implemented as a separate, black box routine permitting real-valued func-tion evaluations only.

(d) The objective model has a high number of input and/or output parameters.

Due to these characteristics, expensive functions pose a serious problem to the common ap-proaches of computing fuzzy-valued functions. To compute the extension principle solution,several global optimization problems must be solved. For instance, to compute a model withonly a single output argument discretized into just 10 α-cuts, 20 global optimization problemsmust be solved. Although the objective function remains the same, different box constraintshave to be applied, which can only be exploited by standard global search methods up to a verylimited degree. Furthermore, most practical applications have many ouput variables, givingrise to many more optimization problems that must be solved. Although multiple output pa-rameters do not pose a problem to permutational methods, such as the transformation method,the complexity grows exponentially with the number of input parameters if the method is toguarantee convergence to the correct solution. In the chapters to follow, it will be demon-strated that sparse grid interpolation techniques are a suitable tool to efficiently address theseproblems.

21

3 Tensor Product and Sparse GridInterpolation

3.1 Univariate interpolation

We start with a brief review of univariate interpolation. Only two cases are considered here,namely piecewise linear spline interpolation and Lagrangian polynomial interpolation, sinceour sparse grid algorithms discussed later on are based on these univariate interpolation formu-las. However, these are not the only choices available – various other interpolation techniqueshave also been applied successfully to sparse grids [16, 76, 79, 80].

3.1.1 Piecewise linear splines

Let f : [a,b] → R be the function to be interpolated by a piecewise linear function Πh1( f )

using a finite number of support nodes x0 = a < x1 < · · · < xn = b, and let Πh1( f ) be obtained

by connecting the two points (x j, f (x j)) and (x j+1, f (x j+1)) by a straight line. h denotes themaximum length of the intervals [x j,x j+1]. Then, the piecewise linear spline is given by [71,ch. 3]

Πh1( f )(x) = f (x j)+

f (x j+1)− f (x j)

x j+1 − x j(x− x j) for x ∈ [x j,x j+1]. (3.1)

The following error bound holds if f ∈C2([x j,x j+1]) ∀ x0, . . . ,xn−1:

‖ f −Πh1( f )‖∞ ≤ h2

8max

ξ∈[a,b]| f ′′(ξ )|. (3.2)

We can easily rewrite Eq. 3.1 in Lagrangian form

Πh1( f )(x) =

n

∑j=0

f (x j)a j(x) (3.3)

by defining the basis functions a j to

a j(x) =

x−x j−1x j−x j−1

, if x ∈ [x j−1,x j], j = 1, . . . ,n,x j+1−xx j+1−x j

, if x ∈ [x j,x j+1], j = 0, . . . ,n−1,

0, otherwise.

(3.4)

23

3 Tensor Product and Sparse Grid Interpolation

In case of piecewise linear splines with equidistant nodes, the basis functions simplify to

a j(x) =

1− n|x−x j|

b−a , if |x− x j| < (b−a)/n,

0, otherwise.(3.5)

An important implementational feature of piecewise linear interpolation with equidistant nodes(see Algorithm 1) is the fact that the actual points x j, j = 0, . . . ,n need not be stored explicitly.Furthermore, the computation of an interpolated value can be performed in O(1) if the functionvalues f (x j) are stored in a contiguous array.

Algorithm 1 Piecewise linear spline interpolation

In: n ∈ N: Number of segments.[a,b]: Objective interval.x ∈ [a,b): Point to interpolate.Y = y0 = f (x0), . . . ,yn = f (xn): Set of function values at the equidistant nodes

x0 = a < x1 < .. . < xn = b.Out: p = Πh

1( f )(x): Interpolated value.

Let h = (b−a)/n.Let i =

((x−a)/h).

Let xi = a+ i ·h.Let p = yi +(yi+1 − yi) · (x− xi) ·h−1.

3.1.2 Lagrangian polynomial interpolation

In case of smooth objective functions, polynomial interpolation offers a higher-order errordecay with increasing number of nodes than piecewise linear splines. Let f : [a,b] → R bethe function to interpolate by a polynomial Πn( f ) using a finite number of support nodesa ≤ x0 < x1 < · · · < xn ≤ b. Then, there exists a unique polynomial Πn( f ) ∈ Pn such thatΠn( f )(x j) = f (x j) for j = 0, . . . ,n. In Lagrangian form, we have (e.g. [70, ch. 8])

Πn( f )(x) =n

∑j=0

f (x j)l j(x), (3.6)

with the basis polynomials (called characteristic polynomials)

l j(x) =n

∏k=0k 6= j

x− xk

x j − xk, j = 0, . . . ,n. (3.7)

Unlike with piecewise interpolation, however, uniform convergence (i.e. ‖ f −Πn( f )‖∞ → 0for n → ∞) is not guaranteed for an arbitrary distribution of nodes. For f ∈ Cn+1([a,b]), the

24

3.1 Univariate interpolation

interpolation error at the point x ∈ [a,b] is given by [70, ch. 8]

f (x)−Πn( f )(x) =f (n+1)(ξ )

(n+1)!

n

∏j=0

(x− x j), (3.8)

where ξ ∈ [a,b] depends on x. In the particular case of equidistant nodes, one obtains [71, ch.3]

‖ f −Πn( f )‖∞ ≤ hn+1

4(n+1)max

ξ∈[a,b]| f (n+1)(ξ )|. (3.9)

Despite the infinitesimal order of hn+1/(4(n + 1)), the error may not go to zero for n → ∞,since the latter term can be outweighed by the magnitude of maxξ∈[a,b] | f (n+1)(ξ )|, see [71, ch.3].

However, node distributions exist where uniform convergence can be proven if f ∈ C1. Tomeasure the approximation quality of the interpolating polynomial for a given node distribu-tion, it is useful to compare it with the interpolating polynomial where the support nodes havebeen selected in an optimal way, i.e. the maximum interpolation error is minimized. To thisend, a couple of definitions are required. In the following, we restrict the considered intervalto [−1,1] for simplicity w.l.o.g.

Definition 3.1 (best approximation polynomial). Let f ∈ C0([−1,1]), and let Πn( f ) ∈ Pn beinterpolating polynomials according to Eqs. (3.6) and (3.7). Then, the interpolating polynomialp∗n( f ) ∈ Pn with

‖ f − p∗n( f )‖∞ ≤ ‖ f −Πn( f )‖∞ ∀ Πn( f )

is called the best approximation polynomial of degree n [70, p. 433].

The distance of an interpolating polynomial Πn( f ) to the best approximation polynomial ismeasured by the Lebesgue constant, which is defined as follows.

Theorem 3.1. Let f ∈ C0([−1,1]). Let X = x j = x jn | j = 0, . . . ,n; n = 1,2,3, . . . be atriangular array of nodes such that each n-th row of X defines a unique interpolating polynomialΠn( f ) ∈ Pn with the support nodes x0, . . . ,xn | − 1 ≤ x0 < x1 < · · · < xn ≤ 1. Then (proofsee [70, p. 434–435], or [73, p. 12–13]),

‖ f −Πn( f )‖∞ ≤ ‖ f − p∗n( f )‖∞(1+Λn(X)), where

Λn(X) =

∥∥∥∥∥n

∑j=0

|l j|∥∥∥∥∥

, (3.10)

and l j denote the characteristic polynomials according to Eq. (3.7).

Definition 3.2 (Lebesgue constant). Λn(X) in the above theorem is called the Lebesgue con-stant.

Note that the Lebesgue constant Λn(X) does not depend on f , but only on the distribution ofthe support nodes X . Therefore, it is possible to construct a priori sets of support nodes X with

25

3 Tensor Product and Sparse Grid Interpolation

a small Lebesgue constant. The set of support nodes X ∗ corresponding to the smallest possibleLebesgue constant Λ(X ∗) can be computed for given n by minimizing Eq. (3.10). Λ(X∗) isbounded by the inequality [11]

12

+2π

log(n+1) < Λn(X∗) <

34

+2π

log(n+1) (3.11)

for all n ≥ 1. Although the optimal nodes are not known in explicit form, several sets of nodesare readily available that suffice for practical purposes. An overview of good choices is given in[11]. Among possible node distributions, interpolation at the Chebyshev extrema (also knownas the Chebyshev Gauss-Lobatto nodes) has the additional advantage that recurring sequencesof nodes are produced for increasing n. We denote the according polynomial by ΠCGL

n ( f ). Thearray of nodes is given by

T = x j = x jn | x j = −cos( jπ/n); j = 0, . . . ,n; n = 1,2, . . .. (3.12)

In particular, with (X)n denoting the n-th row of X , (X)2k−1 ⊂ (X)2k for k = 1,2, . . .. This willbe of use later on. The Lebesgue constant Λ(T ) is bounded from above by

Λn(T ) ≤ 1+2π

log(n+1), n ≥ 1. (3.13)

Thus, the distance Λ(T )−Λ(X ∗) is at most 1/2. Actual values comparing Λn(X∗) and Λn(T )are given in Table 3.1 [11, 67].

Table 3.1: Values of the Lebesgue constants for X ∗ and T .

n Λn(X∗) Λn(T )3 1.423 1.6674 1.559 1.7995 1.672 1.9896 1.768 2.0838 1.925 2.275

10 2.052 2.42120 2.461 2.86850 3.025 3.453

100 3.459 3.894200 3.897 4.336

Depending on the smoothness of f , different convergence rates are obtained by polynomialinterpolation at the Chebyshev Gauss-Lobatto nodes. In this context, some basic definitionsand results from approximation theory are required, which are given in the following (also see[43, ch. 5], [67, 72]).

Definition 3.3 (modulus of continuity). Let f (x) be defined on [a,b]. The modulus of continuityof f (x) on [a,b], ω(δ ), is defined for δ > 0 by

ω(δ ) = supx1,x2∈[a,b],|x1−x2|≤δ

| f (x1)− f (x2)|. (3.14)

26

3.1 Univariate interpolation

From the definition of the modulus of continuity follows directly that f (x) is uniformly con-tinuous on [a,b] if and only if limδ→0 = 0, since any function that is continuous in a closedinterval [a,b] is also uniformly continuous [43, p. 183]. Also related to the modulus of conti-nuity is the Lipschitz condition.

Definition 3.4 (Lipschitz condition). If a function satisfies

| f (x1)− f (x2)| ≤ K|x1 − x2|α (3.15)

for x1,x2 ∈ [a,b], and α > 0, then f (x) is said to satisfy a Lipschitz condition of order α withconstant K on [a,b]. The set of such functions is denoted by lipK α .

Theorem 3.2 (Jackson’s theorem). If f ∈C0([−1,1]), then

‖ f − p∗n( f )‖∞ ≤ 6ω(1/n). (3.16)

From Jackson’s theorem, the following corollaries can be obtained [72].

Corollary 3.1. If f ∈ lipK α on [−1,1], then

‖ f − p∗n( f )‖∞ ≤ 6Kn−α . (3.17)

Corollary 3.2. If f ∈Ck([−1,1]) and n > k, then

‖ f − p∗n( f )‖∞ ≤ 6kek(1+ k)−1 ·n−k · ‖ f (k)− p∗n−k( f (k))‖∞ (3.18)

≤ 6k+1ek(1+ k)−1 ·n−k ·ωk(1/(n− k)), (3.19)

where ωk is the modulus of continuity of f (k).

Using Jackson’s theorem and the corollaries from above, the Lebesgue constant Λn(T ) ofthe Chebyshev Gauss-Lobatto nodes T from Eq. (3.13), and the following weak bound on themodulus of continuity,

ωk(δ ) ≤ supx1,x2∈[−1,1]

‖ f (k)(x1)‖+‖ f (k)(x2)‖ = 2 · ‖ f (k)‖∞,

we immediately arrive at the following error bounds of the polynomial interpolant ΠCGLn ( f ):

Corollary 3.3. If f ∈ lipK α on [−1,1], then

‖ f −ΠCGLn ( f )‖∞ ≤ 6K ·n−α · (2+

log(n+1))≤C1 ·n−α · log(n). (3.20)

Corollary 3.4. If f ∈Ck([−1,1]) and n > k, then

‖ f −ΠCGLn ( f )‖∞ ≤ 6kek(1+ k)−1 ·n−k · ‖ f (k)−ΠCGL

n−k ( f (k))‖∞ (3.21)

≤ 6k+1ek(1+ k)−1 ·n−k ·ωk(1/(n− k)) · (2+2π

log(n+1)) (3.22)

≤C2 · ‖ f (k)‖∞ ·n−k · log(n). (3.23)

27

3 Tensor Product and Sparse Grid Interpolation

Higher convergence rates are obtained if the function f is smooth, i.e. f ∈ C∞ and f canbe analytically continued to a function f (z) that is analytic in a neighborhood of [−1,1] in thecomplex plane [8]. Then,

‖ f −ΠCGLn ( f )‖∞ ≤C3K−n, (3.24)

where C3 > 0 and K = a+b > 1 are constants. Therein, 2a and 2b are the major and minor axislengths of the ellipse with foci ±1 (separated by a distance of 2c = 2) specifying the region inthe complex plane that the function is analytic on. Eq. (3.24) yields a geometric convergencerate. Obviously, even better (super-geometric) convergence rates are achieved if f (z) is entire,i.e. if f is analytic in C.

Example 3.1. Let f1 : [−1,1]→R, f1(x)= |x|3. f is twice continuously differentiable ( f ∈C2).Furthermore, the second derivative f ′′1 (x) = 6|x| satisfies the Lipschitz condition of order 1 withconstant 6 ( f ′′1 ∈ lip6 1). Therefore, according to Eqs. (3.20) and (3.21),

‖ f1 −ΠCGLn ( f1)‖∞ ≤C ·n−3 log(n),

with a positive constant C and n > 2. Fig. 3.1 (a) shows the error en( f1) = maxi=1,...,100| f1(xi)−ΠCGL

n ( f1)| for 100 randomly sampled interpolation points xi in [−1,1] vs. the asymptotic con-vergence rate (neglecting the logarithmic factor).

Example 3.2. Let f2 : [−1,1] → R, f2(x) = 1/(25x2 +1) (Runge’s counter-example, e.g. [70,p. 331]). f2 can be analytically continued. The zeros of the denominator at ±i/5 (the poles off2 in C) govern the extent of the analytic region. By fitting an ellipse with maximum extent,the base K of the error bound according to Eq. (3.24) can be obtained. With any ellipse, therelation a2 = b2 + c2 holds between the major and minor axis lengths 2a, 2b and the distanceof the foci 2c. Thus, K = 1/5 +

√26/25 with b = 1/5 and c = 1. The error, computed as in

Ex. 3.1, is shown in Fig. 3.1 (b).

100

101

102

10−6

10−5

10−4

10−3

10−2

10−1

100

50 100 150 200

10−15

10−10

10−5

100

PSfrag replacements

e ne n

nn

ΠCGLnΠCGL

nO(n−3) O(K−n)

(a) (b)

Figure 3.1: Interpolation error of Exs. 3.1 and 3.2; (a): en( f1), (b): en( f2).

28

3.1 Univariate interpolation

Remark. While Lagrangian polynomial interpolation cannot provide sequences of polyno-mials Πn( f ) that converge uniformly to f for any f ∈ C0, this is indeed possible in generalaccording to the Weierstrass approximation theorem [73, p. 31], for instance by Hermite inter-polation.

3.1.2.1 Efficient and stable polynomial interpolation at the Chebyshev extrema via thebarycentric formula

In the following, we discuss the barycentric formula, which represents an attractive alternativeformulation of the Lagrangian form that results in an efficient and numerically stable algo-rithm. In the barycentric form, interpolation at the Chebyshev extrema reveals another remark-able property. To the most part, our notation follows a recent survey article on barycentricinterpolation [8]; earlier references include [81, p. 190].

Definition 3.5 (barycentric formula of the first form). Rewriting the characteristic polynomialsfrom Eq. (3.7) as

l j(x) =1

∏nk=0k 6= j

(x j − xk)

︸ ︷︷ ︸w j

· 1x− x j

n

∏k=0

(x− xk)

︸ ︷︷ ︸l(x)

= l(x)w j

x− x j, j = 0, . . . ,n, (3.25)

we obtain the formula of the first form

Πn( f )(x) = l(x)n

∑j=0

w j

x− x jf (x j), (3.26)

where w j denote the barycentric weights. Obviously, Πn(x) is not defined for x ∈ x0, . . . ,xn.But these points do not require interpolation anyway, since Πn(x) = f (x) ∀ x ∈ x0, . . . ,xn.

Note that both w j and the factor l(x) do not depend on f . Therefore, Πn can be evalu-ated at a cost of O(n), similar to the well-known Newton interpolation formula provided thatthe barycentric weights are known. For any given point distribution, these weights can beeasily computed using O(n2) operations; [8] gives explicit formulas for the equidistant andChebyshev point distributions. From a numerical standpoint, however, the above formula isproblematic, since underflow or overflow can occur during its computation. Consider, for in-stance, the computation of l(x), x ∈ [−1,1], x j according to Eq. (3.12). Clearly, l(x) → 0 forn → ∞, since with growing n, increasingly many support nodes will lie in close proximity to x.Thus, underflow will occur inevitably for large n with finite precision arithmetic. To addressthe problem of numerical instability, the barycentric formula of the second form is introduced.

The constant function f (x) = 1 can be represented exactly by a Lagrangian polynomialΠn(x), with all f (x j) equal to one. Inserted into Eq. (3.26), we get

1 = l(x)n

∑j=0

w j

x− x j. (3.27)

29

3 Tensor Product and Sparse Grid Interpolation

Definition 3.6 (barycentric formula of the second form). Solving Eq. (3.27) for l(x) and in-serting the result into Eq. (3.26), we obtain the barycentric formula of the second form

Πn( f )(x) =

n

∑j=0

w j

x− x jf (x j)

n

∑j=0

w j

x− x j

. (3.28)

In comparison to the formula of the first form, the barycentric weights w j appear both in thenumerator and the denominator. Therefore, any common factors C can be canceled out suchthat w j = w j/C, j = 0, . . . ,n. In case of the Chebyshev Gauss-Lobatto nodes from Eq. (3.12),one obtains

w0 =12

; w j = (−1) j, j = 1, . . . ,n−1; wn =12(−1)n. (3.29)

Barycentric interpolation at the Chebyshev extrema and other suitable point distributions ex-hibit excellent stability, even in the case of x being very close to a support node x j [8]. Athorough numerical stability analysis is presented in [41], demonstrating that the barycentricformula of the second form is forward stable for any set of points with a small Lebesgue con-stant.

Algorithm 2 provides the barycentric formula for the Chebyshev Gauss-Lobatto nodes overan arbitrary interval [a,b] in algorithmic form. Fig. 3.2 illustrates the performance of a MAT-LAB implementation compared to several other standard interpolation algorithms in terms ofaccuracy and computing time. These other algorithms are the Lagrangian, Aitken, modifiedAitken, Neville, modified Neville, Krogh One, and Krogh Two algorithms (the latter two areimplementations of the Newton divided difference form) taken from the comparison paper byMacleod [58]. Again, the two test functions of Exs. 3.1 and 3.2 are considered. Figs. 3.2 (a), (b)show the error en( f ) = maxi=1,...,100| f (xi)−ΠCGL

n ( f )| for 100 randomly sampled interpo-lation points xi in [−1,1]. In Fig. 3.2 (c), the computing time is shown for a single evaluationof ΠCGL

n (on an i686 Athlon 1.6 GHz PC), undermining the expected excellent performanceof barycentric interpolation. The Newton variants Krogh One/Two and barycentric interpola-tion are the only methods that achieve a complexity of O(n) for the evaluation of Πn( f ). Butthe Newton methods require the computation of some coefficients depending on f that takeO(n2) operations. Furthermore, the Newton algorithms become numerically unstable alreadyfor small values of n < 50. All other methods are of order O(n2), but still perform worse interms of stability than the barycentric form.

3.2 Multivariate tensor product interpolation

An important preliminary stage to sparse grid interpolation is multivariate tensor-product in-terpolation. Actually, sparse grid interpolants are built up from multiple tensor product inter-polants. In the following, we briefly review tensor product interpolation.

30

3.2 Multivariate tensor product interpolation

Algorithm 2 Barycentric polynomial interpolation at the Chebyshev Gauss-Lobatto nodes.

In: n ∈ N: Degree of interpolating polynomial.[a,b]: Objective interval.x ∈ [a,b]: Point to interpolate.T = x j | x j = a+(−cos(π j/n)+1) · (b−a)/2; j = 0, . . . ,n: Support nodes.Y = y j | y j = f (x j), . . . ,yn = f (xn): Set of function values at the support nodes.

Out: p = ΠT ′n ( f )(x): Interpolated value.

If ∃ x j ∈ T such that x j = x ThenLet p = y j. Return.

EndLet d = 0.5/(x− x0). Let s1 = d · y0. Let s2 = d. Let w = −1.For j = 1 To n−1

Let d = w/(x− x j). Let s1 = s1 +d · y j. Let s2 = s2 +d. Let w = −w.EndLet d = 0.5 ·w/(x− xn). Let s1 = s1 +d · yn. Let s2 = s2 +d.Let p = s1/s2.

101

102

103

104

10−12

10−10

10−8

10−6

10−4

10−2

100

101

102

103

104

10−15

10−10

10−5

100

101

102

103

104

10−6

10−4

10−2

100

102

BarycentricLagrangeAitkenmod. AitkenNevillemod. NevilleKrogh OneKrogh Two

BarycentricLagrangeAitkenmod. AitkenNevillemod. NevilleKrogh OneKrogh Two

BarycentricLagrangeAitkenmod. AitkenNevillemod. NevilleKrogh OneKrogh Two

O(n2)O(n)

PSfrag replacements

t[s

ec.]

e ne n

nnn

(a) (b) (c)

Figure 3.2: Comparison of interpolation methods using the Chebyshev Gauss-Lobatto nodes;interpolation error (a): en( f1), (b): en( f2), and (c): computing time.

31

3 Tensor Product and Sparse Grid Interpolation

3.2.1 The general tensor product interpolation formula

In the one-dimensional case, let

U i( f ) = ∑xi∈X i

axi · f (xi), (3.30)

be an interpolation formula with the set of support nodes X i = xi | xi ∈ [0,1], #X i = mi, andthe basis functions axi ∈ C([0,1]), axi(xi) = 1, axi(yi) = 0 ∀ yi ∈ X i,xi 6= yi, i ∈ N. Then, oneobtains an interpolation formula for the multivariate case, by the tensor product formula

(U i1 ⊗·· ·⊗U id)( f ) = ∑xi1∈X i1

· · · ∑xid∈X id

(axi1 ⊗·· ·⊗axid ) · f (xi1, . . . ,xid). (3.31)

Obviously, both piecewise linear Eq. (3.3) as well as Lagrangian polynomial interpolation Eq.(3.6) fit Eq. (3.30), and are therefore suitable building blocks of the tensor product interpolant.In case of scalar functions f1, . . . , fd , the tensor product operation f = f1 ⊗ ·· ·⊗ fd is just afunction of d variables: f (x1, . . . ,xd) = ∏d

k=1 fk(xk).

3.2.2 Algorithms

Piecewise multilinear interpolation Piecewise multilinear interpolation can be implementedin a straightforward way in case of equidistant nodes. The computational complexity of com-puting an interpolated value is O(2d). We skip the implementation, and directly proceed withthe more interesting case of multivariate Lagrangian interpolation.

Multivariate Lagrangian interpolation based on the barycentric formula Here, we intro-duce an extension of the efficient one-dimensional interpolation formula of the second bary-centric form to the multivariate case. Firstly, the barycentric form is adapted to the bivariatecase with an obvious extension to the general multivariate case. We then describe an efficientalgorithm that successfully handles the problem of barycentric interpolation where one or manyof the abscissae of the point to interpolate are equal to the abscissae of the support nodes.

We start with the bivariate case, i.e. f : [a,b]× [c,d] → R. The support nodes are given bythe rectangular array X ×Y , which is the Cartesian product of the sets of points

X = x0, . . . ,xnx | a ≤ x0 < x1 < · · · < xnx ≤ b,Y = y0, . . . ,yny | c ≤ y0 < y1 < · · · < yny ≤ d,

The tensor product of the Lagrangian interpolation formula Eq. (3.6) can be written as

Πnx,ny( f ) = (Πnx ⊗Πny)( f ) =ny

∑k=0

nx

∑j=0

(lx, j ⊗ ly,k) · f (x j,yk). (3.32)

The bivariate interpolation formula has mx ·my = (nx + 1) · (ny + 1) nodes, and is of degreenx in x and of degree ny in y. lx, j and ly,k denote the characteristic polynomials in x and y

32

3.2 Multivariate tensor product interpolation

according to Eq. (3.7). Inserting the characteristic polynomials into Eq. (3.32), and lettinglx(x) = ∏nx

i=0(x− xi) and ly(y) = ∏nyi=0(y− yi), we get

Πnx,ny( f )(x,y) =ny

∑k=0

nx

∑j=0

[( nx

∏i=0i6= j

x− xi

x j − xi·

ny

∏i=0i6=k

y− yi

yk − yi

)· f (x j,yk)

]

= lx(x) · ly(y) ·ny

∑k=0

nx

∑j=0

[ 1x− x j

· 1y− yk

·nx

∏i=0i6= j

1x j − xi

︸ ︷︷ ︸w j

·ny

∏i=0i6=k

1yk − yi

︸ ︷︷ ︸vk

· f (x j,yk)]

= lx(x) · ly(y) ·ny

∑k=0

[ vk

y− yk·

nx

∑j=0

[ w j

x− x j· f (x j,yk)

]],

with the barycentric weights w j and vk. Analogously to Eq. (3.28), interpolating the constantfunction f (x,y) = 1, we get

Πnx,ny( f )(x,y) =

ny

∑k=0

[ vk

y− yk·

nx

∑j=0

[ w j

x− x j· f (x j,yk)

]]

ny

∑k=0

[ vk

y− yk

nx

∑j=0

[ w j

x− x j

] , (3.33)

where any common factors Cw,Cv can be canceled out such that w j = w j/Cw and v j = v j/Cv.We now generalize the above formula to the d-variate case. Let f : [a1,b1]×·· ·× [ad,bd] →

R denote the objective function. Let n = (n1, . . . ,nk) denote the degree of the interpolatingpolynomial in the variables x1, . . . ,xd . Let Xk, k = 1, . . . ,d denote the d sets of mk = nk + 1support nodes in each coordinate direction with

Xk = xk0, . . . ,x

knk| ak ≤ xk

0 < xk1 < · · · < xk

nk≤ bk. (3.34)

Then, the d-variate barycentric formula of the second form is obtained to

Πn( f )(x1, . . . ,xd) =

nd

∑jd=0

[bd

jd(xd) · · · · ·

n2

∑j2=0

[b2

j2(x2) ·

n1

∑j1=0

[b1

j1(x1) · f (x1

j1, . . . ,xdjd )]]

· · ·]

nd

∑jd=0

[bd

jd(xd)]· · · · ·

n2

∑j2=0

[b2

j2(x2)]·

n1

∑j1=0

[b1

j1(x1)] ,

(3.35)

bkjk(x

k) =wk

jk

xk − xkjk

, k = 1, . . . ,d. (3.36)

In principle, the implementation is straightforward, however, similar to the one-dimensionalcase, we must not interpolate for any coordinate direction k where the abscissa xk, k = 1, . . . ,d

33

3 Tensor Product and Sparse Grid Interpolation

Algorithm 3 Multivariate barycentric interpolation at the Chebyshev Gauss-Lobatto nodes.

In: n = (n1, . . . ,nd) ∈ Nd0: Degree of interpolating polynomial in x1, . . . ,xd .

Ω = [a1,b1]×·· ·× [ad,bd]: Objective interval box.x = (x1, . . . ,xd) ∈ Ω: Point to interpolate.T k = xk

j | xkj = ak +(−cos(π j/nk)+1) · (bk −ak)/2; j = 0, . . . ,nk, k = 1, . . . ,d :

Support nodes. If nk = 0, use T k = xk0 = (ak +bk)/2.

Y = yj | yj = f (x1j1, . . . ,x

djd), j = ( j1, . . . , jd), jk = 0, . . . ,nk, k = 1, . . . ,d:

Function values at the support nodes.Out: p = ΠCGL

n ( f )(x): Interpolated value.

Let D = /0. Initialize set of active interpolation dimensions. Let j = (0, . . . ,0). Initialize multi-index j = ( j1, . . . , jd). For k = 1 To d Do

If nk = 0 Then Let jk = 0.Else If ∃ xk

j ∈ X k, j = 0, . . . ,nk, such that xk = xkj Then Let jk = j.

Else Let D = D∪ k.EndIf D = /0 Then Let p = yj. Return.Let dact = #D. Let s = 1.For Each k ∈ D Do Precompute the bk

jkand the denominator sum s.

Let bk0 = 0.5/(xk − xk

0). Let t = bk0. Let w = −1.

For j = 1 To nk −1 DoLet bk

j = w/(xk − xkj). Let t = t +bk

j. Let w = −w.EndLet bk

nk= 0.5 ·w/(x− xk

nk). Let t = t +bk

nk. Let s = s · t.

EndIf dact > 1 Then Let done = false Else Let done = true.Let c1 = 0.Do Perform dact-variate interpolation.

Let k = (D)1.For jk = 0 To nk Do

Let c1 = c1 +bkjk· yj.

EndFor l = 2 To dact Do

Let k = (D)l. Let cl = cl +bkjk· cl−1. Let cl−1 = 0.

If jk < nk Then Let jk = jk +1. Break.Else If l < dact Then Let jk = 0.Else done = true.

EndWhile done = false.Let p = cdact/s.

34

3.3 Sparse grid interpolation

coincides with any support node xkj ∈ X k. Algorithm 3 outlines an implementation of multi-

variate polynomial interpolation at the Chebyshev Gauss-Lobatto nodes.Algorithm 3 does not address how the set of function values Y is stored. We recommend

a flattened, contiguous one-dimensional array Y , which can be implemented easily in anyprogramming language. Using just a one-dimensional array allows one to implement Al-gorithm 3 such that it works for any number of dimensions d. To map the d-dimensionalmulti-index j to its one-dimensional counterpart j, one can formally use the transformationj = ∑d

k=1

[jk ·∏k−1

l=1 nl], with the empty product ∏ /0 := 1. In order to avoid the computation of

j in each iteration of the loop, one can obtain the address index j of y j ∈ Y from its value in theprevious step by adding an appropriate relative step size that depends on the currently treateddimension.

The complexity of Algorithm 3 is governed by the do–while loop. One gets O(N), whereN = m1 · · · · ·md is the total number of grid points. To achieve O(N) independently of d,one must be careful to correctly implement the addressing of the values yj as mentioned inthe previous paragraph. If the polynomial degrees nk are not of equal magnitude, one canfurther improve the performance of the algorithm by reordering the dimensions such that thesums in the numerator of Eq. (3.35) with larger n appear more towards the inside of the nestedexpression.

3.3 Sparse grid interpolation

The interpolation problem considered with sparse grid interpolation is an optimal recoveryproblem (i.e. the selection of points such that a smooth function can be approximated with asuitable interpolation formula). Depending on the characteristics of the function to interpolate(degree of smoothness, periodicity), various interpolation techniques based on sparse grids ex-ist (e.g. [7, 76, 79, 80]). All of them employ Smolyak’s construction [78], which forms thebasis of all sparse grid methods. With Smolyak’s famous method, well-known univariate in-terpolation formulas are extended to the multivariate case by using tensor products in a specialway. As a result, one obtains a powerful interpolation method that requires significantly fewersupport nodes than conventional interpolation on a full grid. The points comprising the multidi-mensional sparse grid are hereby selected in a predefined fashion. The difference in the numberof required points can be several orders of magnitude with increasing problem dimension. Themost important property of the method constitutes the fact that the asymptotic error decay offull grid interpolation with increasing grid resolution is preserved up to a logarithmic factor.An additional benefit of the method is its hierarchical structure, which can be used to obtainan estimate of the current approximation error. Thus, one can easily develop an interpolationalgorithm that aborts automatically when a desired accuracy is reached.

In the following, we discuss hierarchical sparse grid interpolation algorithms based on bothpiecewise multilinear and polynomial basis functions. We compare three different sparse gridtypes for the piecewise linear case with respect to their grid structure and matching piecewisemultilinear basis functions. Thereafter, the higher-order polynomial case is discussed. Weperform numerical tests with respect to the error decay for a set of test functions. Finally,we take a look at suitable algorithms, complexity considerations, and the performance of our

35

3 Tensor Product and Sparse Grid Interpolation

reference implementation in MATLAB.Interpolation is not the only application area of sparse grids. [16] provides an overview of

the foundations as well as current developments in this active research field.

3.3.1 Smolyak’s algorithm

This brief description of Smolyak’s construction for multivariate interpolation adheres to thenotation given in [7]. We would like to approximate smooth functions f : [0,1]d → R usinga finite number of support nodes. However, the tensor product formula Eq. (3.31) requires avery high number of mi1 · · ·mid support nodes, which are sampled on the full grid. To reducethe number of support nodes while maintaining the approximation quality of the interpolationformula up to a logarithmic factor, Smolyak’s construction is used. With U 0 = 0, ∆i = U i −U i−1, |i| = i1 + · · ·+ id for i ∈ Nd , and q ≥ d,q ∈ N, the Smolyak algorithm is given by

Aq,d( f ) = ∑|i|≤q

(∆i1 ⊗·· ·⊗∆id )( f ) = Aq−1,d( f )+ ∑|i|=q

(∆i1 ⊗·· ·⊗∆id )( f )

︸ ︷︷ ︸∆Aq,d( f )

, (3.37)

with Ad−1,d = 0. From Eq. (3.37), we observe that we can increase the accuracy of the in-terpolation based on Smolyak’s construction without having to discard previous results. Mostimportantly, to compute Aq,d( f ), only the function values at the sparse grid

Hq,d =⋃

q−d+1≤|i|≤q

(X i1 ×·· ·×X id) (3.38)

are needed. One should select the sets X i in a nested fashion such that X i ⊂X i+1 to obtain manyrecurring points with increasing q. With X 0 = /0, X i

∆ = X i \X i−1, one can rewrite Eq. (3.38) to

Hq,d =⋃

|i|≤q

(X i1∆ ×·· ·×X id

∆ ) = Hq−1,d ∪∆Hq,d, with (3.39)

∆Hq,d =⋃

|i|=q

(X i1∆ ×·· ·×X id

∆ ), (3.40)

Hd−1,d = /0, which is more convenient for a successive refinement of the grid with increasingparameter q. For later use, we denote the cardinality of a subset (X i1

∆ × ·· · × X id∆ ) by n(i).

For comparison, we also introduce Hfull,q,d as the full grid with smallest number of points stillcontaining the sparse grid Hq,d with

Hfull,q,d = Xq−d+1 ×·· ·×Xq−d+1. (3.41)

3.3.2 Piecewise multilinear basis functions

Selection of a suitable sparse grid For multilinear interpolation, it is natural to select sparsegrids with sets X i, i∈N of equidistant nodes. We have examined three possibilities to constructthe sparse grid, namely

36

3.3 Sparse grid interpolation

(a) The “classical” maximum- or L2-norm-based sparse grid HM, including the boundary,as thoroughly discussed in [1, 14]. The points xi

j comprising the set of support nodesX i = xi

1, . . . ,ximi are defined as

mi = 2i +1, (3.42)

xij =

j−1mi −1

for j = 1, . . . ,mi, and i ≥ 1.

(b) The maximum-norm-based sparse grid, but excluding the points on the boundary, de-noted by HNB. Now, the xi

j are defined as

mi = 2i−1, (3.43)

xij = j/(mi +1) for j = 1, . . . ,mi, and

(c) The Clenshaw-Curtis-type sparse grid HCC with equidistant nodes, as described in [65,76]. Although the original paper [17] uses Chebyshev-distributed nodes, we adhere tothis grid name due to its association in the literature with the grid structure (resultingfrom the sequence mi = 2i−1 +1). Here, the xi

j are defined as

mi =

1 if i = 1,

2i−1 +1 if i > 1.(3.44)

xij =

j−1mi −1

for j = 1, . . . ,mi if mi > 1,

0.5 for j = 1 if mi = 1.

All three resulting sets of points fulfill the important property X i ⊂ X i+1, and therefore alsoHq,d ⊂ Hq+1,d . Figure 3.3 illustrates the grids HM

6,2, HNB6,2 and HCC

6,2 for d = 2. Figure 3.4

illustrates the grids HM7,3, HNB

7,3 and HCC7,3 for d = 3. The number of grid points grows much faster

with increasing q,d for HM. The number of points of the Clenshaw-Curtis grid HCC increasesthe slowest. To further illustrate the growth of the number of nodes with q,d depending onthe chosen grid type, we have included Table 3.2. Note that the grid HM is not suited forhigher-dimensional problems, since at least 3d support nodes are needed.

Our numerical tests in Section 3.3.6 show that the Clenshaw-Curtis-type grid outperformsthe other grid types in most cases by some factor (the asymptotic error decay remains thesame). However, depending on the objective function characteristics, another grid type mayalso perform better occasionally.

The univariate nodal basis functions To compute Aq,d( f ), we need to specify the basisfunctions a of the interpolation formulas U i( f ). We provide the piecewise linear basis functionsfor each of the three grid types below.

37

3 Tensor Product and Sparse Grid Interpolation

0 0.5 10

0.2

0.4

0.6

0.8

1

Points: 257 Level: 4, d: 20 0.5 1

0

0.2

0.4

0.6

0.8

1

Points: 129 Level: 4, d: 20 0.5 1

0

0.2

0.4

0.6

0.8

1

Points: 65 Level: 4, d: 2

PSfrag replacements

(a) (b) (c)

Figure 3.3: Sparse grids in 2D; (a): HM6,2, (b): HNB

6,2 , (c): HCC6,2 .

00.5

1

0

0.5

10

0.5

1

Points: 1505, Level: 40

0.51

0

0.5

10

0.5

1

Points: 351, Level: 40

0.51

0

0.5

10

0.5

1

Points: 177, Level: 4

PSfrag replacements

(a) (b) (c)

Figure 3.4: Sparse grids in 3D; (a): HM7,3, (b): HNB

7,3 , (c): HCC7,3 .

Table 3.2: Comparison: Number of grid points for level n = q−d.

d = 2 d = 4 d = 8n M NB CC M NB CC M NB CC0 9 1 1 81 1 1 6561 1 11 21 5 5 297 9 9 41553 17 172 49 17 13 945 49 41 1.9e5 161 1453 113 49 29 2769 209 137 7.7e5 1121 8494 257 129 65 7681 769 401 2.8e6 6401 39375 577 321 145 20481 2561 1105 9.3e6 31745 157136 1281 769 321 52993 7937 2929 3.0e7 141569 567377 2817 1793 705 1.3e5 23297 7537 9.1e7 5.8e5 1.9e5

38

3.3 Sparse grid interpolation

(a) For the maximum-norm-based grid, we define

axij(x) =

1− (mi−1)|x− xi

j|, if |x− xij| < 1/(mi−1),

0, otherwise,

for j = 1, . . . ,mi.

(b) For the maximum-norm-based grid without boundary nodes, we define

ax11(x) = 1 for i = 1, and

if j =

1, axi1(x) =

2− (mi +1)x, if x < 2

mi+1

0, otherwise,

mi, aximi

(x) =

(mi +1)x−mi +1, if x > mi−1

mi+1

0, otherwise,

otherwise, axij(x) =

1− (mi +1)|x− xi

j|, if |x− xij| < 1

mi+1 ,

0, otherwise,

for i > 1 and j = 1, . . . ,mi.

(c) For the Clenshaw-Curtis grid, we get

ax11(x) = 1 for i = 1, and

axij(x) =

1− (mi−1) · |x− xi

j|, if |x− xij| < 1/(mi−1),

0, otherwise,

for i > 1 and j = 1, . . . ,mi.

Accuracy of piecewise multilinear interpolation We now take a brief look at the approxi-mation quality. An a priori error estimate can be obtained for a d-variate function f if continu-ous mixed derivatives

Dβ f =∂ |β | f

∂xβ11 · · ·xβd

d

, (3.45)

with β ∈ Nd0 , |β | =

d∑

i=1βi, and β1, . . . ,βd ≤ 2, exist. According to [7] or [15], the order of the

interpolation error in the maximum norm is then given by

‖ f −Aq,d( f )‖∞ = O(N−2 · | log2 N|3·(d−1)), (3.46)

with N denoting the number of grid points of HCCq,d or HM

q,d . Piecewise multilinear approximation

on a full grid with N grid points is much less efficient, i.e. O(N− 2d ).

39

3 Tensor Product and Sparse Grid Interpolation

3.3.3 Polynomial basis functions

The piecewise multilinear approach can be significantly improved by using higher-order basisfunctions, such as the Lagrangian characteristic polynomials. The approximation properties ofsparse grid interpolation techniques using polynomial basis functions have been studied exten-sively in [7], where error bounds depending on the smoothness of the function were derived.These results are summarized at the end of this section.

Selection of a suitable sparse grid From the one-dimensional case, we know that oneshould not use equidistant nodes for higher-order polynomial interpolation. This directly sug-gests using Chebyshev-based node distributions. Since an additional requirement of an ef-ficient sparse grid algorithm is the nesting of the sets of nodes, X i ⊂ X i+1, the ChebyshevGauss-Lobatto nodes are clearly the best choice, and are therefore also suggested in [7]. Wethus define the sets X i = xi

1, . . . ,ximi, i ∈ N by

mi =

1 if i = 1,

2i−1 +1 if i > 1.

xij =

(−cos(π( j−1)/(mi−1))+1)/2 for j = 1, . . . ,mi if mi > 1,

0.5 for j = 1 if mi = 1,

and denote the resulting Chebyshev-Gauss-Lobatto sparse grid by HCGL. Fig. 3.5 illustratesthe grids HCGL

6,2 and HCGL7,3 . The number of grid points of the CGL-grid is identical to the one

of the Clenshaw-Curtis grid.

0 0.5 10

0.2

0.4

0.6

0.8

1

Points: 65, Level: 4 00.5

1

0

0.5

10

0.5

1

Points: 177, Level: 4

PSfrag replacements

(a) (b)

Figure 3.5: Sparse grids using polynomial interpolation; (a): HCGL6,2 , (b): HCGL

7,3 .

40

3.3 Sparse grid interpolation

The univariate nodal basis functions In principle, the polynomial basis functions are thecharacteristic polynomials of Eq. (3.7),

ax11(x) = 1 for i = 1, and

axij(x) =

mi

∏k=1k 6= j

x− xik

xij − xi

k

for i > 1 and j = 1, . . . ,mi.

Accuracy of polynomial interpolation From the error bounds of the univariate case, thefollowing general error bounds depending on the smoothness of the objective function f arederived in [7]. For f ∈ Fk

d ,

Fkd = f : [−1,1]d → R | Dβ f continuous if βi ≤ k ∀ i, (3.47)

with β ∈ Nd0 , Dβ f according to Eq. (3.45), the order of the interpolation error in the maximum

norm is given by‖ f −Aq,d( f )‖∞ = O(N−k · | logN|(k+2)(d+1)+1). (3.48)

3.3.4 From univariate nodal to multivariate hierarchical

In this section, we will show how one can obtain a multivariate hierarchical formulation ofSmolyak’s algorithm of Section 3.3.1 in explicit form. The univariate nodal basis functions arehereby transformed into multivariate hierarchical bases. To do this, we utilize that U i( f ) canexactly represent U i−1( f ). This is the case for the piecewise linear basis functions chosen forthe Clenshaw-Curtis grid HCC and the maximum-norm-based grid HM including the boundary,and for the polynomial basis functions of the Chebyshev-Gauss-Lobatto grid HCGL.

Remark. The nodal basis functions of the no-boundary-nodes grid HNB violate this assump-tion close to the boundary. The following construction of the hierarchical bases is therefore notapplicable in this particular case. Despite this, the no-boundary-nodes grid performed well inthe numerical tests, which led to the decision to include this grid type in our implementation.

By taking advantage of the subset property X i ⊂ X i+1, we start with the transformation ofthe univariate nodal basis into the hierarchical one. By definition, we have

∆i( f ) = U i( f )−U i−1( f ).

With U i( f ) = ∑xi∈X i axi · f (xi) and U i−1( f ) = U i(U i−1( f )), we obtain

∆i( f ) = ∑xi∈X i

axi · f (xi)− ∑xi∈X i

axi ·U i−1( f )(xi)

= ∑xi∈X i

axi ·(

f (xi)−U i−1( f )(xi)),

and, since f (xi)−U i−1( f )(xi) = 0 ∀ xi ∈ X i−1,

∆i( f ) = ∑xi∈X i

axi ·(

f (xi)−U i−1( f )(xi)), (3.49)

41

3 Tensor Product and Sparse Grid Interpolation

recalling X i∆ = X i \X i−1. Clearly, X i

∆ has m∆i = mi − mi−1 elements, since X i−1 ⊂ X i. By

consecutively numbering the elements in X i∆, and denoting the jth element of X i

∆ as xij, we can

rewrite Eq. (3.49) as

∆i( f ) =m∆

i

∑j=1

aij ·(

f (xij)−U i−1( f )(xi

j))

︸ ︷︷ ︸wi

j

, (3.50)

To simplify the notation, we have replaced axij

by aij. Note that for all ∆i( f ), i > 1, we only

have to consider the contributions of the basis functions belonging to the grid points that havenot jet occurred in a previous set X i−k, 1 ≤ k ≤ i− 1. For a comparison of the nodal and thehierarchical basis functions, see Fig. 3.6. For the construction of the interpolant of a univariateobjective function f using nodal basis functions and function values vs. using hierarchicalbasis functions and hierarchical surpluses, see Fig. 3.8.

The tensor product formula Eq. (3.31) and the Smolyak algorithm Eq. (3.37) can now beapplied to the ∆i from Eq. (3.50) to obtain the sparse grid interpolation formula for the multi-variate case in hierarchical form. Recalling Eq. (3.37), we have

Aq,d( f ) = Aq−1,d( f )+∆Aq,d( f ), with (3.51)

∆Aq,d( f ) = ∑|i|=q

(∆i1 ⊗·· ·⊗∆id)( f ), (3.52)

with Ad−1,d = 0. We can express U i−1 in Eq. (3.50) by the following sum by using the tele-scopic property ∆i = U i−U i−1:

U i−1( f ) =i−1

∑i1=1

∆i1( f ).

In case of the full grid, we would thus obtain a multivariate extension of an interpolant U i−1

with the tensor product formula Eq. (3.31) to

(U i−1⊗·· ·⊗U i−1)( f ) =i−1

∑i1=1

· · ·i−1

∑id=1

(∆i1 ⊗·· ·⊗∆id )( f ).

However, the Smolyak formula Aq−1,d only uses the support nodes and basis functions of thesparse grid with |i| ≤ q−1, (between the index i of the univariate interpolation formula U i( f )and the parameter q of the Smolyak formula Aq,d( f ) constructed from U 1( f ), . . . ,U i( f ), wehave the relation q = i+d−1). Therefore, we use the reduced sum

Aq−1,d( f ) = ∑|i|≤q−1

(∆i1 ⊗·· ·⊗∆id)( f )

instead of (U i−1 ⊗ ·· ·⊗U i−1)( f ) when constructing ∆Aq,d( f ) in Eq. (3.52) from Eq. (3.50).Finally, we obtain the Smolyak algorithm in entirely hierarchical form with Eq. (3.51) and

∆Aq,d( f ) = ∑|i|=q

∑j

(ai1j1⊗·· ·⊗aid

jd)

︸ ︷︷ ︸ai

j

·(

f (xi1j1, . . . ,xid

jd)−Aq−1,d( f )(xi1

j1, . . . ,xid

jd))

︸ ︷︷ ︸wi

j

, (3.53)

42

3.3 Sparse grid interpolation

(a) (b)

1

1 3ax1

031x

21x 3

1x 11x 3

2x 2

2x

01

1 1a

1

3a

2

2a2

2a

1

3a

1

32x 3

3x 34x 3

5x

3ax2

3ax3

3ax4

3ax5

Figure 3.6: Nodal basis functions ax3j, x3

j ∈ X3 (a) and hierarchical basis functions aij with the

support nodes xij ∈ X i

∆, i = 1, . . . ,3 (b) for the Clenshaw-Curtis grid.

(a) (b)

0

1

PSfrag replacements

x31 x3

2 x33 x3

4 x35

ax31

ax32

ax33

ax34

ax35

0

1

PSfrag replacementsx3

1x3

2x3

3x3

4x3

5ax3

1ax3

2ax3

3ax3

4ax3

5

x21 x3

1 x11 x3

2 x22

a11

a21

a22

a31

a32

Figure 3.7: Nodal basis functions ax3j, x3

j ∈ X3 (a) and hierarchical basis functions aij with the

support nodes xij ∈ X i

∆, i = 1, . . . ,3 (b) for the Chebyshev-Gauss-Lobatto grid.

(a) (b)

31

21x 3

1x 11x 3

2x 2

2x3

2x 33x 3

4x 35xx

f(x1)3

f(x2)3

f(x3)3 f(x

4)3

f(x5)3

w21

w31

w11

w32 w2

2

Figure 3.8: Nodal (a) vs. hierarchical (b) interpolation in 1D.

43

3 Tensor Product and Sparse Grid Interpolation

with j denoting the multi-index ( j1, . . . , jd), jl = 1, . . . ,m∆il, and l = 1, . . . ,d. Note that all the

required support nodes xij = (xi1

j1, . . . ,xid

jd) of a single level k are included in the set ∆Hk+d,d , as

defined in Eq. (3.39). Furthermore, it is useful to define

wk,ij = f (xi

j)−Ak+d−1,d(xij)

as the hierarchical surpluses [15] at level k with k = |i|− d, since Ak+d,d corrects Ak+d−1,d atthe points xi

j to the actual value of f (xij). For continuous functions, the hierarchical surpluses

tend to zero as the level k tends to infinity (see Fig.3.8, (b)). This makes the hierarchicalsurpluses a natural candidate for error estimation and control. We define

wnabs = max

|i|=n+d, j

|wn,i

j |

and wnrel =

max|i|=n+d, j

|wn,i

j |

max|i|≤n+d, j

f (xi

j)− min

|i|≤n+d, j

f (xi

j) (3.54)

as the estimated absolute and relative error of Aq,d( f ), respectively.

i1= 2

i2= 1

i = 2 i = 3 i = 4

i1= 3

i2= 1

i1= 1

i2= 1

i1= 1

i2= 2

i1= 1

i2= 3

i1= 2

i2= 2

0

1

a11 ⊗ a

11

|i| = 2

0

1

a11 ⊗ a

1,22

0

1

a11 ⊗ a

1,23

0

1

a1,22 ⊗ a

11

|i| = 3

0

1

a1,22 ⊗ a

1,22

0

1

a1,23 ⊗ a

11

|i| = 4

Figure 3.9: 2D example: Sparse grid HCC4,2 and according bilinear basis functions of A4,2.

3.3.5 Algorithms

In this section, we present detailed algorithms for performing sparse grid interpolation. Wehave abstracted the data structures to ordered sets, since depending on the programming en-vironment, different data types may be available that are suitable to hold the data, such as thesets of multi-indices, the multivariate sparse grid coordinates, and the hierarchical surpluses.However, we provide information on an efficient organization of the data that we have used inour implementation.

44

3.3 Sparse grid interpolation

3.3.5.1 General remarks

Let us first state some general remarks on the notation. The # operator denotes the cardinalityof a set. The algorithms produce nested sets, i.e. a set will often contain subsets. Note that inthis case, the cardinality refers to the number of subsets only. To extract subsets or elementsfrom a set, we use the notation s = (S)k, meaning that s is the kth element (or subset) of S. InAlgorithms 4, 5, 7, we use the + = (− =) operator on sets. In this case, we mean that eachelement at the lowest level (i.e. the values) is incremented (decremented) by the right-handside value at the same position in the set (the sets on the left- and on the right-hand side are ofequal size). Similarly, the min and max operations in Algorithm 4 run over each element at thelowest level.

The total number of index sets of an interpolant An+d,d( f ) can be easily computed by theformulae

Sn,d =n

∑k=0

#∆Sk,d =

(n+d

d

), with (3.55)

#∆Sk,d = ∑|i|=k+d

1 =

(d + k−1

d −1

)(proof see e.g. [76, p. 137]). (3.56)

Also useful in analyzing the complexity of the sparse grid algorithms are upper bounds on thenumber of sparse grid points #Hn+d,d . We have

#Hn+d,d =n

∑k=0

#∆Hn+d,d =n

∑k=0

∑i∈∆Sk,d

n(i), (3.57)

with n(i) as defined in Section 3.3.1 in the paragraph after Eq. (3.40). More specifically, weobtain for the grid type HNB (see [76, p. 37]),

#HNBn+d,d =

n

∑k=0

#∆HNBk+d,d ≤ 2n

(n+d −1

d −1

)·min

2,

n+dd

, with (3.58)

#∆HNBk+d,d = 2k ·#∆Sk,d. (3.59)

With respect to the other grid types, the following relations hold:

#HCCn+d,d = #HCGL

n+d,d ≤ #HNBn+d,d, and (3.60)

#HMn+d,d =

d

∑j=0

(dj

)·2d− j ·#HNB

n+ j, j (see [15, p. 35]), (3.61)

with #HNBn,0 := 1.

3.3.5.2 Description of the algorithms

Algorithm 4, , summarizes the procedure of obtaining an increasingly accurate sparse

grid interpolant via hierarchical construction. The hierarchical surpluses wk are used to es-timate the current interpolation error, and to formulate the break condition. One obtains the

45

3 Tensor Product and Sparse Grid Interpolation

interpolation depth n and an ordered set of hierarchical surpluses Zn,d as the output of the algo-rithm (actually, Zn,d contains subsets of subsets of hierarchical surpluses), which can then beused by to evaluate the according interpolant An+d,d( f ). Note that the sparse gridcoordinates need not be stored.

Algorithm 5, , is called multiple times by

to compute the hierarchical

surpluses by subtracting the interpolated values Ak−1+d,d( f )(xij) at the new grid points xi

j ∈∆Hk+d,d from the function values f (xi

j), according to Eq. (3.53). The test in the if-then clause

assures that sub-domains where the interpolated values at the points xij are known to be Zero

are omitted.Algorithm 6,

, explicitly constructs the set of sparse grid points ∆Hn+d,d accordingto Eq. (3.40), which is required by

to evaluate the objective function at these points.

This function also returns the according set of multi-indices.Algorithm 7, , evaluates the interpolant An+d,d( f ) using the set of hierarchical

surpluses Zn,d computed by . The subroutine performs the actual work.

Note that we recompute the sets of indices ∆Sk,d here instead of retaining the index sets inmemory after the construction of the hierarchical surpluses using

, since this does not

significantly affect the computational cost.Finally, Algorithm 8,

, computes interpolated values for the given (sub)sets of

hierarchical surpluses Zk with according index sets ∆Sk,d . In the presented form of ,

the sub-function computes the interpolated values for all i with |i| = k + d atonce. This has proved more efficient, since the number of function calls is not too high. Thisis due to the fact that with increasing d, the cardinality of ∆Sk,d can become quite large.

3.3.5.3 Data structure

The most important data to be handled by the algorithms provided in the previous section arethe sets of multi-indices ∆Sk,d , k = 0, . . . ,n, the sets of sparse grid points ∆Hk+d,d , k = 0, . . . ,n,and the set of hierarchical surpluses Zn,d . We suggest to store the information in the followingstraightforward way:

Multi-indices ∆Sk,d is a two-dimensional array with d columns and #∆Sk,d rows. Each rowcontains one multi-index. ∆Sk,d can be computed on-the-fly by an internal function and doesnot have to be permanently stored.

Grid points Also not permanently stored are the sparse grid points ∆Hk+d,d computed by . They are only internally used by the

algorithm. The points are consecutively

stored as a single row in a two-dimensional double array with d columns. This is done in thesame order as the multi-indices in ∆Sk,d . Note that the number of points n(i) = #X i1

∆ ×·· ·×X id∆

per multi-index i usually varies (see also Fig. 3.10, indicated by corresponding shading of therow indices).

Hierarchical surpluses Finally, the sets of hierarchical surpluses can be organized as a 1×(n + 1) cell array consisting of the sub-arrays Zk, k = 0, . . . ,n. These hold the hierarchical

46

3.3 Sparse grid interpolation

Algorithm 4 f d : Compute set of hierarchical surpluses Zn,d .

In: d ∈ N. f : [0,1]d → R: Objective function.δrel, δabs: Relative and absolute error tolerance.nmax ∈ N: Maximum interpolation depth.

Out:n: Interpolation depth. Zn,d: Ordered set of hierarchical surpluses.

Let w−1max = ∞, ymin = ∞, ymax = −∞, k = 0.

While wk−1max ≥ maxδrel · (ymax − ymin), δabs And k ≤ kmax Do

[∆Hk+d,d , ∆Sk,d] = k d .Yk = f (∆Hk+d,d). Evaluate y = f (x) at all points x ∈ ∆Hk+d,d Let Zk = Yk.For m = 0 To k−1

Zk− = d Zm ∆Hk+d,d ∆Sk,d ∆Sm,d .

Endymax = max

ymax,y ∀ y ∈ Yk

. ymin = min

ymin,y ∀ y ∈ Yk

.

wkmax = maxwk ∀ wk ∈ Zk.

k = k +1.EndLet n = k−1. Let Zn,d = Z0, . . . ,Zn.

Algorithm 5 (d,Zold,∆Hnew,∆Snew,∆Sold): Subroutine of

.

In: d ∈ N. Zk: Ordered set of hierarchical surpluses.∆Hnew: Ordered set of sparse grid points.∆Snew, ∆Sold: Ordered sets of multi-indices.

Out:∆Y new: Ordered set of interpolated values.

Let mold = #∆Sold, mnew = #∆Snew.Let ∆Y new = (∆Y )1, . . . ,(∆Y )mnew, Initialize ∆Y to contain all zeros

with (∆Y ) j = 0, . . . ,0, #(∆Y ) j = #(∆Hnew) j, j = 1, . . . ,mnew.For lnew = 1 To mnew Do

Let inew = (∆Snew)lnew.For all iold ∈ iold = (∆Sold)lold | iold

j ≤ inewj ∀ j ∈ 1, . . . ,d, lold = 1, . . . ,mold Do

(∆Y )lnew+ = (d,(Zold)lold (∆Hnew)lnew iold).End

End

47

3 Tensor Product and Sparse Grid Interpolation

Algorithm 6 n d : Compute the set of sparse grid points ∆Hn+d,d .

In: n ∈ N0, d ∈ N.Out:∆Hn+d,d: Ordered set of points.

∆Sn,d: Ordered set of according indices.

Let ∆Sn,d =

i ∈ Nd | |i| = n+d, |i| = i1 + · · ·+ id

. Let m = #∆Sn,d .

For k = 1 To m DoLet i = (∆Sn,d)k. Let Xk = X i1

∆ ×·· ·×X id∆ .

EndLet ∆Hn+d,d = X1, . . . ,Xm.

Algorithm 7 d n Zn,d P : Evaluate the interpolant An+d,d( f ).

In: d ∈ N. n ∈ N0: Interpolation depth.

Zn,d : Ordered set of hierarchical surpluses.P: Set of points to interpolate.

Out:Y : Ordered set of interpolated values Y = Ad+n,d( f )(P).

Let Y = 0, . . . ,0 with #Y = #P.For k = 0 To n Do

Let ∆Sk,d =

i ∈ Nd | |i| = k +d, |i|= i1 + · · ·+ id

.

Y+ = d (Zn,d )k P ∆Sk,d .End

Algorithm 8 d Zk P Sd : Subroutine of .

In: d ∈ N. Zk: Ordered set of hierarchical surpluses.P: Set of points to interpolate.Sd: Ordered set of indices.

Out:∆Y : Ordered set of interpolated values.

Let ∆Y = 0, . . . ,0 with #∆Y = #P. Let m = #Sd .For l = 1 To m Do

Let i = (Sd)l.For Each pr ∈ P, r = 1, . . . ,#P Do

For Each wij ∈ (Zk)l with pr ∈ supp(ai

j) Do (∆Y )r+ = aij(pr) ·wi

j.End

End

48

3.3 Sparse grid interpolation

surpluses of level k constructed by the algorithm. Fig. 3.10 illustrates the ordering of

the hierarchical surpluses according to the sparse grid point ordering.

k ∆Sk,d ID Data

0 ∆S0,3 1 1 1 1

∆Hk+d,d ID Data

∆H3,3 1 0.5 0.5 0.5

Zk ID Data

Z0 1 w1

1 ∆S1,3 123

2 1 11 2 11 1 2

∆H4,3 123456

0 0.5 0.51 0.5 0.5

0.5 0 0.50.5 1 0.50.5 0.5 00.5 0.5 1

Z1 123456

w1

w2

w3

w4

w5

w6

2 ∆S2,3 123456

3 1 12 2 11 3 12 1 21 2 21 1 3

∆H5,3 123456

.25 0.5 0.5

.75 0.5 0.50 0 0.51 0 0.50 1 0.51 1 0.5

...

Z2 123456

w1

w2

w3

w4

w5

w6

...

3 ∆S3,3 12

5 1 14 2 1

......

Figure 3.10: Data structure, example for d = 3.

3.3.5.4 Computational cost

In the following, we briefly address the computational complexities of computing the hierar-chical surpluses with

and evaluating the sparse grid interpolant with , for the

piecewise linear as well as the polynomial approach.

Computational complexity of Both and require subse-

quent calls of . Therefore, we asses the complexity of this function first. Theinnermost loop can be performed in O(d) in case of piecewise linear basis functions, since theevaluation of a d-variate basis function takes O(d), and there is only one basis function ai

j with

pr ∈ supp(aij) for all wi

j ∈ (Zk)l . This holds for all i for the grids HCC,HNB, and in case of HM,for all i with i1, . . . , id > 1. Considering the outer loops, the computational complexity is givenby

cost( , p,Sd,d,LI) = O(p ·#Sd ·d), (3.62)

where p = #P is the number of points to interpolate.

49

3 Tensor Product and Sparse Grid Interpolation

If polynomial basis functions are used, all basis functions aij have a global support, i.e.

pr ∈ supp(aij) ∀ ai

j. By employing barycentric polynomial interpolation (see Algorithm 3) –slightly modified taking into account the hierarchical representation, where only every secondbasis function in each dimension is contributing to the numerator of the multivariate barycentricformula (see Fig. 3.7, (b)) – requires a cost that grows linearly with the numberof basis functions ai

j associated with the support nodes xij ∈ ∆Hk+d,d . Therefore,

cost( , p,Sd,d,CGL) = O

(p · ∑

i∈Sd

n(i)). (3.63)

Computational complexity of Determining the hierarchical surpluses wi

j at thesparse grid points is computationally more involved than applying the Smolyak formula di-rectly to the nodal representation [7, Eq. (3)]

Aq,d( f ) = ∑q−d+1≤|i|≤q

(−1)q−|i| ·(

d −1q−|i|

)· (U i1 ⊗·· ·⊗U id), (3.64)

which represents a superposition of several full tensor product sub-grids. It is therefore oftencalled combination technique [15, p. 48]. The advantage of this approach is that it can beimplemented in a very straightforward way, e.g. in [7], the Aitken–Neville formula is used tocompute the univariate polynomials U ik . This approach could be improved by applying thebarycentric form, for the reasons mentioned in the previous sections. However, there are twoimportant disadvantages to Eq. (3.64): Firstly, by using the function values rather than thehierarchical surpluses, an error estimate is difficult to obtain, and no natural stopping criteriaare available for the grid refinement. On the other hand, the hierarchical surpluses allow oneto reliably asses the current interpolation error, which is crucial for the automatic terminationof the

algorithm provided that the requested error tolerance is satisfied. Secondly, the

number of the support nodes of the combined full grids is higher than the support nodes of thesparse grid, which leads to a higher computational effort in the evaluation of the interpolant.This is especially important if a large number of interpolated values must be performed, asin the context of this thesis. We therefore propose using the hierarchical formulas, althoughcomputing the hierarchical surpluses initially implies an additional computational effort.

Let us start with analyzing that is called multiple times by

. The outer

loop runs over all new multi-indices inew at level n contained in the set ∆Snew = ∆Sn,d . Theinner loop runs over the old multi-indices iold at level k from ∆Sold = ∆Sk,d , but it is onlyfor old indices with all components smaller than the components of the new indices that themethod must be called. This is due to the hierarchical scheme, where all basisfunctions aiold

j evaluate to zero at the grid points associated with the index set inew. Thus, weobtain

cost( ,n,k,d) = O

(∑

inew∈∆Sn,d

∑iold∈∆Sk,d

ioldj ≤inew

j

cost( ,n(inew),iold,d)).

(3.65)

50

3.3 Sparse grid interpolation

The cost of is governed by the outer while- and the inner for-loop. We have

cost( ,n,d) = O

( n

∑k=0

k−1

∑l=0

cost( ,k, l,d)

). (3.66)

Note that this cost does not include the cost for the required #Hn+d,d evaluations of the objectivefunction f , which will govern the overall time of

if its evaluation is costly.

Now, proceeding with the piecewise linear case, by inserting the cost of ,

, and #iold = 1, we get

cost( ,n,d,LI) = O

( n

∑k=0

k−1

∑l=0

∑inew∈∆Sk,d

∑iold∈∆Sl,d

ioldj ≤inew

j

n(inew) ·1 ·d)

(3.67)

= O(d ·

n

∑k=0

∑inew∈∆Sk,d

n(inew)k−1

∑l=0

∑iold∈∆Sl,d

ioldj ≤inew

j

1

︸ ︷︷ ︸= cold(inew)

). (3.68)

This can be simplified further by explicitly computing the cardinality of all admissible oldindices iold with respect to a new index inew, denoted by cold(inew) in the equation above. Onefinds by careful examination of the grid structure that this number can be directly expressedonly in terms of inew by

cold(inew) =d

∏l=1

inewl −1. (3.69)

Consider Fig. 3.11 for an illustration. The total number of new indices at step k = 3, forinstance, is #∆S3,2 = 4. For each of the indices inew ∈ ∆S3,2 = (4,1);(3,2);(2,3);(1,4), coldcan be computed as shown. Therefore,

cost( ,n,d,LI) = O

(d ·

n

∑k=0

∑i∈∆Sk,d

n(i) ·( d

∏j=1

i j −1))

. (3.70)

Simpler upper bounds of this formula

cost( ,n,d,LI) ≤ O

(d ·

n

∑k=0

#∆Hk+d,d ·((k +d

d

)d−1))

(3.71)

≤ O

(#Hn+d,d ·d ·

(n+dd

)d)(3.72)

can be derived by using Eq. (3.57) and

d

∏j=1

i j ≤(k +d

d

)dfor all i ∈ ∆Sk,d . (3.73)

51

3 Tensor Product and Sparse Grid Interpolation

By using Eq. (3.72) together with Eqs. (3.60)–(3.61), one can easily get a conservative esti-mation of the cost of

depending on n,d involving only simple algebraic operations.

In case of polynomial basis functions, we arrive at

cost( ,n,d,CGL) = O

( n

∑k=0

∑inew∈∆Sk,d

n(inew)k−1

∑l=0

∑iold∈∆Sl,d

ioldj ≤inew

j

n(iold)). (3.74)

Unfortunately, this term cannot be simplified further as in the piecewise linear case due to theinner summand n(iold). We could bound the inner sum using Eqs. (3.56) or (3.69) and boundson n(iold), but this gave much too conservative results, especially in higher dimensions.

Computational complexity of We immediately obtain the cost of computing asingle interpolated value with to

cost( ,n,d) = O( n

∑k=0

cost( ,1,∆Sk,d,d)), (3.75)

by simply considering the number of calls to . In the piecewise linear case, weget

cost( ,n,d,LI) = O( n

∑k=0

#∆Sk,d ·d)

= O

(d ·(

n+dd

)), (3.76)

i1

i2

1

1 2 3 4

2

3

4

H

3+2,2 where k =3,

|inew|=5, and #

S3,2

=4.

here, all hierarchical basis functions evaluate to zero.

inew=(4,1) and contributingold indices, #=4*1-1=3.

inew=(3,2) and contributingold indices, #=3*2-1=5.

Figure 3.11: Multi-indices and sparse grid points of HCC5,2 .

52

3.3 Sparse grid interpolation

applying Eq. (3.56). In the polynomial case,

cost( ,n,d,CGL) = O( n

∑k=0

∑i∈∆Sk,d

n(i))

= O(#HCGL

k+d,d

), (3.77)

i.e. the cost grows linearly with the number of grid points.

3.3.6 Numerical results

We have conducted a comparison of the piecewise multilinear and the polynomial interpolationschemes using the testing package of Genz [25], designed for evaluating the performance ofnumerical integration algorithms. In [7], it was also used to test the performance of sparsegrid interpolation. The testing package consists of six families of functions defined on [0,1]d

(here, we omit the discontinuous test function, which cannot be approximated by a continuousinterpolant), with the following characteristics:

oscillatory: f1(x) = cos

(2πw1 +

d

∑i=1

cixi

),

product peak: f2(x) =d

∏i=1

(c−2

i +(xi −wi)2)−1

,

corner peak: f3(x) =

(1+

d

∑i=1

cixi

)−(d+1)

,

Gaussian: f4(x) = exp

(−

d

∑i=1

c2i · (xi−wi)

2

),

continuous: f5(x) = exp

(−

d

∑i=1

ci · |xi−wi|)

.

Varying test functions can be obtained by altering the parameters c = (c1, . . . ,cn) and w =(w1, . . . ,wn). We chose these parameters randomly from [0,1]. Similar to [7], we normalizedthe ci such that ∑d

i=1 ci = b j, with b j depending on d, f j according to

j 1 2 3 4 5b j 1.5 d 1.85 7.03 20.4

Furthermore, we normalized the wi such that ∑di=1 wi = 1.

Figs. 3.12–3.14 show the absolute error

e = maxi=1,...,1000

| f (yi)−Aq,d( f )(yi)| (3.78)

over the total number of sparse grid points N for d = 2,5,10, for the five test functions, where(a) compares the three different choices of grids for the piecewise multilinear case, and (b)

53

3 Tensor Product and Sparse Grid Interpolation

shows the interpolation error of the polynomial case in comparison to the multilinear one. In(3.78), we have replaced the error norm from Eq. (3.46) by a discrete approximation. Thepoints y1, . . . ,y1000 ∈ [0,1]d were generated randomly. [spc] in Figs. 3.12–3.14, (a) is theasymptotic convergence rate according to Eq. (3.46). The curve labeled “full” shows the er-ror of equidistant multilinear interpolation (a), and of Chebyshev-Gauss-Lobatto polynomialinterpolation (b) at the full grid. As expected, all schemes in (a) show the same asymptoticbehavior according to Eq. (3.46) in case of f ∈ F . However, for the oscillatory, the productpeak, and the Gaussian-shaped test functions, interpolation with HCC and HNB produced betterresults than HM, i.e. fewer support nodes were needed to achieve similar accuracies. In case ofthe corner peak test function, HM sometimes performed slightly better. This difference resultsfrom the different distribution of the support nodes (see Figs. 3.3, 3.4), which is more densefor HM at the boundary. In case of the continuous test function, all four grid types could notprovide the asymptotic error decay of Eq. (3.46), since f /∈ F . Since the test functions f1– f4

are infinitely smooth, ACGL outperforms ALI asymptotically, as expected from Eq. (3.48).

3.3.7 Performance results

In this section, we demonstrate the performance of our reference implementation in MATLAB.The performance tests were carried out using a MATLAB V7.0 implementation running on aLinux i686 3.06 GHz PC.

Fig. 3.15, (a) shows the time to compute the hierarchical surpluses depending on the dimen-sion d with respect to the number of sparse grid support nodes N. Fig. 3.15, (b) shows the timeto compute 1000 interpolated values depending on N. Both curves are plotted for the Clenshaw-Curtis grid. Similar results are obtained for the other two grid types. The dashed lines indicatethe expected computational costs according to the formulae Eq. (3.70) and Eq. (3.76) (positionof the asymptotic curves chosen for reasons of clarity).

Fig. 3.15, (c) and (d) depict the performance of our implementation for polynomial inter-polation. Interestingly, the computational cost of computing the hierarchical surpluses with

decreases with the dimension d for a fixed number of support nodes N. This can

be explained intuitively (without providing a rigorous proof here) by taking a closer look atEq. (3.74). In case of the Clenshaw-Curtis grid, we can bound the inner two sums from aboveby applying Eq. (3.57) to

k−1

∑l=0

∑iold∈∆Sl,d

ioldj ≤inew

j

n(iold) ≤ #Hk+d−1,d, inew ∈ ∆Sk,d, (3.79)

#Hd−1,d := 0. This basically means that we neglect the condition iold ≤ inew, such that allprevious grid points would contribute to the cost. Then,

cost( ,n,d,CGL) ≤ O(

n

∑k=0

#∆Hk+d,d ·#Hk+d−1,d). (3.80)

From Table 3.2, we observe that for increasing dimension d, the ratio #HCCn+d,d/#HCC

n+d−1,d in-creases for an about equal number of grid points, and thus, the product in the equation above

54

3.3 Sparse grid interpolation

(a)

100

102

104

106

10−15

10−10

10−5

100

oscillatory

100

102

104

106

10−10

10−5

100

product peak

100

102

104

106

10−10

10−5

100

corner peak

100

102

104

106

10−10

10−5

100

Gaussian

100

102

104

106

10−10

10−5

100

continuous

full

HM

HNB

HCC

[spc]

(b)

100

101

102

103

104

105

10−15

10−10

10−5

100

oscillatory

100

101

102

103

104

105

10−20

10−10

100

product peak

100

101

102

103

104

105

10−20

10−10

100

corner peak

100

101

102

103

104

105

10−20

10−10

100

Gaussian

100

101

102

103

104

105

10−5

100

continuous

full

HCGL

HCC

Figure 3.12: Error plots for d = 2; (a): ALIq,2( f ), with HM, HNB and HCC, (b): ACGL

q,2 ( f ) vs.

ALIq,2( f ).

55

3 Tensor Product and Sparse Grid Interpolation

(a)

100

102

104

106

10−10

10−5

100

oscillatory

100

102

104

106

10−6

10−4

10−2

100

product peak

100

102

104

106

10−5

100

corner peak

100

102

104

106

10−5

100

Gaussian

100

102

104

106

10−4

10−2

100

continuous

full

HM

HNB

HCC

[spc]

(b)

100

102

104

106

10−15

10−10

10−5

100

oscillatory

100

102

104

106

10−10

10−5

100

product peak

100

102

104

106

10−10

10−5

100

corner peak

100

102

104

106

10−15

10−10

10−5

100

Gaussian

100

102

104

106

10−3

10−2

10−1

100

continuous

full

HCGL

HCC

Figure 3.13: Error plots for d = 5; (a): ALIq,5( f ), with HM, HNB and HCC, (b): ACGL

q,5 ( f ) vs.

ALIq,5( f ).

56

3.3 Sparse grid interpolation

(a)

100

102

104

106

10−6

10−4

10−2

100

oscillatory

100

102

104

106

10−4

10−2

100

product peak

100

102

104

106

10−3

10−2

10−1

100

corner peak

100

102

104

106

10−3

10−2

10−1

100

Gaussian

100

102

104

106

10−2

10−1

100

continuous

full

HM

HNB

HCC

(b)

100

102

104

106

10−10

10−5

100

oscillatory

100

102

104

106

10−10

10−5

product peak

100

102

104

106

10−4

10−3

10−2

10−1

corner peak

100

102

104

106

10−5

100

Gaussian

100

102

104

106

10−3

10−2

10−1

100

continuous

full

HCGL

HCC

Figure 3.14: Error plots for d = 10; (a): ALIq,10( f ), with HM, HNB and HCC, (b): ACGL

q,10 ( f ) vs.

ALIq,10( f ).

57

3 Tensor Product and Sparse Grid Interpolation

becomes smaller, already suggesting a decreasing cost. Furthermore, the ratio of actually con-tributing old index sets iold compared to the total number of old index sets #Sk−1,d , as used by#Hk+d−1,d in Eq. (3.79),

#iold ∈ ∆Sl,d | ioldj ≤ inew

j , l = 0, . . . ,k−1, inew ∈ ∆Sk,d#Sk−1,d

≤(k+d

d

)d −1(d + k−1

d

) , (3.81)

k ≥ 1, decreases with increasing dimension d, which further adds to the effect. E.g. comparingthis upper bound for d = 2, n = 10 and d = 4, n = 7 for an about equal number of nodes#H10,2 = 7169 and #H7,4 = 7537, we get the ratios 0.6364 and 0.2676, respectively.

The curves for computing interpolated values achieves the predicted linear dependence onthe number of sparse grid nodes according to Eq. (3.77).

(a) (b)

100

101

102

103

104

105

10−2

10−1

100

101

102

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16asymptotic

100

101

102

103

104

105

10−2

10−1

100

101

102

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16asymptotic

(c) (d)

101

102

103

104

10−2

10−1

100

101

102

103

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16

100

101

102

103

104

10−2

10−1

100

101

102

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16asymptotic

Figure 3.15: (a): Time to compute the hierarchical surpluses (CC-grid), (b): Time to evaluateinterpolant 1000 times (CC-grid), (c): Time the compute the hierarchical surpluses(CGL-grid), (d): Time to evaluate interpolant 1000 times (CGL-grid).

58

3.4 Dimension-adaptive tensor-product interpolation

3.4 Dimension-adaptive tensor-product interpolation

With the standard sparse grid approach, all dimensions are treated equally, i.e. in each coordi-nate direction, the number of grid points is equal. The question arises as to whether one can fur-ther reduce the computational effort for objective functions where not all input variables carryequal weight. This is especially important in the case of higher-dimensional problems, wherethis property is often observed. Unfortunately, it is usually not known a priori which variables(or, in this context, dimensions) are important. Therefore, an efficient approach should be ableto automatically detect which dimensions are the more or less important ones, without wastingany function evaluations. Hegland [39] and Gerstner and Griebel [26] show that this is indeedpossible. They propose an approach to generalize sparse grids such that the number of nodes ineach dimension is adaptively adjusted to the problem at hand. Here, the adaptive refinement isnot performed in a spatial manner, as it is commonly done in two- and three-dimensional prob-lems (e.g. [15]), where more support nodes are placed in areas of increased nonlinearity ornon-smoothness (this becomes impractical in higher dimensions due to the required complexdata structure and refinement criteria).

We have not yet specified what is considered high-dimensional in this context. In [26], prob-lems with up to 256 unknowns were successfully treated. But even in lower-dimensional prob-lems, dimension-adaptive techniques can outperform standard sparse grids by balancing thenumber of nodes in each coordinate direction according to the considered problem, especiallyif the problem exhibits additive or nearly additive [26] structure. This is due to the fact that thedimension-adaptive algorithm can automatically detect separability or partial separability.

But even dimension-adaptive sparse grids do not scale well to very high dimensions of sev-eral thousand unknowns and more. In this case, it may be inevitable to neglect parts of theinformation in a preprocessing step, and consider only a reduced model. Reduced models maybe obtained with SVD-based methods (e.g. proper orthogonal decomposition, also known asprincipal component analysis or the Karhunen-Loéve expansion), or Krylov-based methods.See [4, 5] for an overview. This is often possible, since with very high-dimensional data,mostly strong correlations and dependencies exist between the dimensions.

The original paper [26] applies the dimension-adaptive sparse grid approach to numericalquadrature. However, as already stated in [26], this approach can be adapted to other problemsas well. In our case, we adapt the proposed algorithms to multivariate interpolation. Further-more, we suggest additional enhancements of the data structure and the algorithms to improvethe efficiency specifically for high-dimensional data.

3.4.1 Generalized sparse grid interpolation

The Smolyak algorithm uses, in its conventional form as stated in Eq. 3.37, for a given inter-polation depth n ∈ N0, the sets of indices Sn,d = i | |i| ≤ n + d to construct An+d,d( f ). Amore general algorithm is obtained if one considers a less stringent admissibility condition onthe sets of indices used by the formula. The only formal requirement for such a condition isthe fact that the telescopic property ∆i = U i−U i−1 must still be satisfied.

59

3 Tensor Product and Sparse Grid Interpolation

Definition 3.7 (admissibility condition). A set of indices S is called admissible if for all i ∈ S,

i− e j ∈ S for 1 ≤ j ≤ d, i j > 1

holds, where e j is the j-th unit vector, and i ∈ Nd . Let S denote the space of all admissible

sets of indices.

With Def. 3.7, the general sparse grid construction becomes

ASk( f ) = ∑i∈Sk

(∆i1 ⊗·· ·⊗∆id )( f ), (3.82)

with Sk ∈ S , where the lower index k ∈ N denotes the cardinality of the set of indices #Sk.To construct an efficient hierarchical algorithm of increasing accuracy with growing num-

ber of indices k, one should use nested sequences of index sets Sk such that Sk−1 ⊂ Sk for allk > 1. The main idea of [26] is to select, in each step of the algorithm, a multi-index such that apossibly large reduction of the approximation error is achieved. To do this, an estimated errorg(i) is assigned to each index i ∈ Sk. The indices in the forward neighborhood of the indexwith the largest estimated error are then added prior to indices with a lower error indicator,where the forward neighborhood of an index i is defined as the d indices i+e j | j = 1, . . . ,d.This leads to the desired dimension-adaptive grid refinement. One usually starts this adaptivehierarchical construction with the root index set S1 = (1, . . . ,1), and successively adds theindices i ∈ (2,1, . . . ,1),(1,2,1, . . .,1), . . .,(1, . . . ,1,2), to obtain an initial set of error indi-cators. Newly added indices are pooled as so-called active indices, while indices of which theforward neighborhood has been processed become old indices.

For the most part, our implementation follows the one proposed in [26]. We also adapt thenotation of [26], denoting the set of active indices by A and the set of old indices by O . In thefollowing, we mainly focus on the differences of our implementation compared to [26].

Error indicators It is obvious that different error indicators are required for interpolationthan for integration. Among the many possible choices, let us suggest

g(i) =1

n(i) ∑j|wi

j|, (3.83)

where wij are the hierarchical surpluses of the sub-grid Xi = X i1

∆ ×·· ·×X id∆ , with j = ( j1, . . . , jd),

jl = 1, . . . ,m∆il

, and n(i) = #Xi. This indicator can be computed cheaply and it performed wellin numerical tests.

For the global (absolute) error estimator, we propose the obvious choice of computing themaximum over the hierarchical surpluses of all active indices, i.e.

η = maxi∈A , j

|wij|. (3.84)

60

3.4 Dimension-adaptive tensor-product interpolation

Greedy/conservative refinement We propose a similar but more reliable approach to pre-vent too early stopping of the algorithm, or a stagnation of refinement in some neighborhood,in case of underestimated errors. We follow the original idea of a single parameter ω ∈ [0,1]that allows the user to gradually chose between a greedy, purely adaptive approach (ω = 1),and a conventional sparse grid construction (ω = 0). But instead of introducing ω into the errorindicator g, as suggested in [26, Sec. 3], we use a separate indicator that relates the maximumvalue max |i|, i ∈ A ∪O of the set of already considered indices to the minimum value min |i|,i ∈ A of the set of currently active indices. More specifically, we add the forward neighbors ofiact = argmini∈A |i| if

mini∈A

|i|

maxi∈A ∪O

|i| ≤ (1−ω), (3.85)

regardless of the current values of the error indicators g(i), i ∈ A . The advantage of thisapproach is that the active indices at the front cannot move too far ahead of the remainingactive indices. The allowable relative distance is measured by ω , and is not affected by thedimension of the problem or the desired accuracy, as is the case in the suggested choice for qin [26]. There, values of ω other than Zero or One must be chosen carefully depending on dand the targeted accuracy to obtain a grid that does not lead to either of the two extreme cases.

Basis functions and grid types Since there are no additional restrictions on the grid be-sides the nesting of the univariate formulas, we can apply any of the univariate basis functionsand node distributions of the regular sparse grid approach discussed in the previous section.Most suitable, however, are grids that build on univariate sequences with a single point at thelowest level, such as the grids HCC, HCGL, and HNB, which perform well in high dimensions.Otherwise, already the number of points of the root index set grows exponentially with thedimension, e.g. for the grid HM, n(i1) = 3d .

3.4.2 Algorithms

In case of interpolation, two separate routines are necessary, one for the computation of the hie-rarchical surpluses (which is actually the dimension-adaptive one), and one for the evaluationof the interpolant. The algorithms are summarized in Alg. 9 and Alg. 10.

The dimension-adaptive approach should scale well even to very high-dimensional prob-lems, and it should minimize the overhead for storing the necessary data. Furthermore, thedimension d should not seriously affect the performance of the sparse grid algorithms. Somedetails on how to achieve this are summarized in [26], such as the efficient treatment of inser-tion/removal of active indices as well as the test for admissibility of new indices via a neigh-bor array. Gerstner and Griebel [26] also suggest a data structure that works well with thedimension-adaptive approach; this was demonstrated with examples from numerical integra-tion with up to 256 dimensions. However, further significant improvements are possible, whichwe describe in the following section.

61

3 Tensor Product and Sparse Grid Interpolation

Algorithm 9 f d ω : Adaptively compute set of hierarchical surpluses Zk.

In: d ∈ N. f : [0,1]d → R: Objective function.δrel, δabs: Relative and absolute error tolerance.Nmax ∈ N: Maximum number of nodes. ω ∈ [0,1]: Degree of dimensional adaptivity.

Out:Sk: Set of multi-indices. Zk: Ordered set of hierar. surpluses of corresp. sub-grids.

Let E⊕ be the set of unit vectors ei | i = 1, . . . ,d in Rd .Let eest = ∞, k = 1.Let A = (1), O = /0.Let X1 = X1

∆ ×·· ·×X1∆, N = #X1.

Let Z1 = f (X1). Evaluate y = f (x) at all points x ∈ X1 Let ymax = max

y ∀ y ∈ Z1

, ymin = min

y ∀ y ∈ Z1

.

While eest ≥ maxδrel · (ymax − ymin), δabs And N ≤ Nmax DoLet iact = argmin

|i| ∀ i ∈ A

.

If |iact| > (1−ω) ·max|i| ∀ i ∈ A ∪O

Then

Let iact = argmax

g(i) ∀ i ∈ A

.EndLet A = A \iact, O = O ∪iact, ZO = ZO ∪Ziact .For j = 1 To d Do

Let inew = iact + e j.If inew − el ∈ O for all el ∈ el ∈ E⊕ | il > 1, l = 1, . . . ,d Then

Let A = A ∪inew.

Let Xinew = Xinew1

∆ ×·· ·×Xinewd

∆ . Let Yinew = f (Xinew).Let Zinew = Yinew −

(d,ZO ,Xinew,inew,O).

Let ymax = max

ymax,y ∀ y ∈ Yinew

, ymin = min

ymin,y ∀ y ∈ Yinew

.Let N = N +#Xinew, k = k +1.

EndEndLet eest = max

w ∀ w ∈ Zi ∀ i ∈ A

.

EndLet Sk = O ∪A , Zk = ZO ∪ ⋃

i∈A

Zi.

Algorithm 10 (d,Zk ,P,Sk): Evaluate dimension-adaptive interpolant ASk( f ).

In: d ∈ N. P: Set of points to interpolate.Sk: Set of multi-indices. Zk: Ordered set of corresponding hierarchical surpluses.

Out:Y : Ordered set of interpolated values Y = ASk( f )(P).

Let Y = (d,Zk,P,Sk).

62

3.4 Dimension-adaptive tensor-product interpolation

3.4.2.1 Data structure

Multi-indices Unlike with regular sparse grids, where the sequence of indices is pre-deter-mined by the Smolyak algorithm, the multi-indices must now be stored explicitly. In [26], themulti-indices are stored as full m× d array, where m is the maximum number of generatedindices, and d is the problem dimension. However, in case of higher-dimensional problems,most array entries will contain the index of the lowest level, i.e. the value 1. This suggested theidea of storing the array of multi-indices as a sparse array, which is immediately obtained bysubtracting 1 from all array entries. Usually, storing sparse matrices is accompanied by somecomputational overhead arising from the insertion of new entries. However, in our case, thiscan be avoided entirely, since new multi-index sets can simply be appended at the end of thedata structure.

One additional difficulty has to be kept in mind. Since the construction of the grid also relieson storing the forward and the backward neighbors of each index set (to achieve an efficientadmissibility check, as required by the dimension-adaptive algorithm), this gain will be lost ifthe data structure of the backward indices and the forward indices, which [26] also suggest tobe stored as m×d arrays, cannot be modified accordingly.

Neighbor arrays The backward neighbor array exhibits exactly the same sparsity structure asthe multi-index arrays, since, unless an index entry is of the lowest level, a backward neighborexists and must be stored. Thus, the same simplification can be applied here. The forwardneighbor array can remain a full array. However, one should only store the forward neighborsof an index once the index becomes an old index, since active indices do not yet have anyforward neighbors. The number of active indices is usually large compared to the number ofpassive indices, this is thus a very important point to be considered.

Active/old indices and error indicators are stored as vectors, as described in [26].

Other meta-data Apart from the multi-indices and the neighbor arrays, it is advisable to storesome additional meta-data, such as the number of grid points associated with each multi-index,and the storage location of its according hierarchical surpluses, which can be stored in a con-tiguous one-dimensional array.

The entire data structure for the indices, neighbors, and meta-data is illustrated by a simpletwo-dimensional example in Fig. 3.16. Apart from the forward neighbor array, all data arestored as vectors. As in [26], we use relative addressing, i.e. the variables containan index into an array, not a pointer.

Remark. The fields and could also be computed from thefields and to save additional memory.

Example 3.3. Consider a regular sparse grid with d = 1000 of level n = 2. The number ofindex sets can be computed by Eq. (3.56) to S2,1000 = 501501. If the index entries are storedas bytes, and the neighbors are stored as 32-bit integers, over 4.2 GB of memory are requiredto store them as full m× d matrices. However, only 1001000 entries of the multi-index array

63

3 Tensor Product and Sparse Grid Interpolation

are different from 1, only 1001000 backward neighbors exist, and only 1001 index sets haveforward neighbors. With the proposed storage scheme, the total memory used amounts to lessthan 13 MB (see Table 3.3). Thus, an improvement by a factor of more than 300 is achieved inthis case.

3.4.2.2 Computational cost

The computational cost of the dimension-adaptive algorithm is asymptotically still governedby the subroutines

and the , which do the main work in the Algo-

rithms 9 and 10, respectively. One might expect that employing the more complex sparse datastructure will result in a higher computational cost. But this is not the case; on the contrary,it is even reduced in case of the grids HCC and HNB, which is due to the constant univariatebasis functions ax1

1= 1 for i = 1 that do not contribute to the multilinear basis function axi

j.

These can now be omitted without requiring any conditional statement, since with the pro-posed sparse storage scheme, index entries of the lowest level (i = 1) are not stored. Sincea multi-index set Sn,d only contains multi-indices with at most n entries greater than one, thecomputational complexity of

is improved from Eq. (3.62) to

cost( , p,Sn,d,d,CC,NB) = O(

p ·#Sn,d ·mind,maxn,1). (3.86)

Obviously, the actual overall computational complexity will depend on the problem at hand.But regarding the sparse storage scheme of the multi-indices, assuming that a regular sparse

grid HCC,NBn+d,d is obtained, the computational complexities of

and improve

according to the complexity of , replacing the factor d by a factor mind,maxn,1 in Eqs. (3.66) and (3.75).

In case of the polynomial interpolation scheme at the Chebyshev Gauss-Lobatto grid H CGL,the improvements are not as significant, since the dimensions with a degree 0 polynomial(i.e. the ones with level i = 1) are eliminated in the preprocessing step of Algorithm 3 (inthe first loop over d). However, in case of large d and small n, this loop can dominate theperformance of the algorithm; by applying the sparse multi-index storage scheme, this is nolonger a problem, since the loop can only run over the dimensions stored for each multi-index,which is again limited to at most mind,maxn,1. Asymptotically, the complexity remains

cost( , p,Sn,d,d,CGL) = O(

p · ∑i∈Sd

n(i)), (3.87)

but the algorithm performs better for large d and small n than with the regular, non-sparsestorage of the multi-indices. Similarly, the overhead for the bookkeeping of the indices is onlyof order O(d log( )+ d min(d,max(n,1)) compared to the O(d log( )+ d2) mentioned in[26] due to the reduced inner loop iterations required in Algorithm 9.

3.4.3 Numerical examples

We measure the absolute interpolation error by a discrete approximation of the ∞-norm

eadapt = maxi=1,...,1000

| f (yi)−ASk( f )(yi)|, (3.88)

64

3.4 Dimension-adaptive tensor-product interpolation

Table 3.3: Example 3.3: Required storage space for the multi-index and neighbor data ofA1002,1000( f ).

field name type bytes 501501 501501×4 1001000×2 1001000

1001000×4 1001×4

1001×1000×4Total 13522509

0indicesNDims 1 1 1 2 1 1 2 2 1

indicesAddr 0 1 2 3 4 6 7 8 10 12

indicesDims 1 2 1 1 2 2 1 1 2 1 2 2

1 1 2 1 1 2 3 2 1 1 2 3indicesLevs

backwardNeighbors 1 1 2 3 2 3 4 5 4 6 5 6

forwardNeighbors

1 2 3 4 5 6

2 4 5 7 8 93 5 6 8 9 10

uint8

uint32

uint16

uint8

uint32

uint32

field name index ID / index data

d=2

type

uint32

forwardAddr

subGridPoints

subGridAddr

z.vals (surpluses)

1 2 2 2 4 2 4 4 4 4

1 2 4 6 8 12 14 18 22 26

uint32

uint32

w1 w2 w3 w4 w5 double

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6

1 2 3 4 5 6 7 8 9 10

...

1

2

3

4

5

6 10

9

8

7

0

1

2

3

0 1 2 3i1

i2

Figure 3.16: Example: Data structure of the index sets, neighbor information, and the hierar-chical surpluses of a two-dimensional dimension-adaptive interpolant.

65

3 Tensor Product and Sparse Grid Interpolation

with randomly sampled points y1, . . . ,y1000 ∈ [0,1]d.Before examining the performance of the dimension-adaptive approach in higher dimen-

sions, let us consider two simple two-dimensional examples to illustrate how the algorithmworks. In these examples, we set ω = 1 (applying the greedy, purely adaptive grid refinement).

Example 3.4. The first example deals with the detection of the important dimension. Considerthe objective function f : [0,1]2 → R, f (x1,x2) = exp(−x2

1 − ρx22), where ρ ∈ 10−1, 10−2,

10−4. Clearly, for the considered range of the variables, x1 will dominate the result. Thedimension-adaptive approach takes advantage of this, i.e. up to a certain point, only the firstdimension is refined. We consider both the Clenshaw-Curtis grid HCC with its piecewise linearbasis functions as well as the Chebyshev-Gauss-Lobatto grid HCGL with its polynomial basisfunctions. The first few steps of the adaptive algorithm are shown in Fig. 3.17 and Fig. 3.18,respectively. The interpolation error eadapt, as defined in Eq. (3.88), is plotted in Fig. 3.19. Theplots also show the decay of the global error indicator η from Eq. (3.84) and, for comparison,the error decay of the conventional sparse grid ereg. The point where the second dimensionbecomes active is indicated by the bold circle in the figures.

Example 3.5. The second example illustrates the detection of separability. Let f : [0,1]2 → R,f (x1,x2) = exp(−x2

1)+ exp(−x22). The first few steps of the algorithm are shown in Fig. 3.20.

The interpolation error eadapt, the decay of the global error indicator η , and the error decayof the conventional sparse grid ereg are plotted in 3.21. Note that since the error indicatorg(2,2) is zero, no further refinement is performed in joint dimensions with the greedy ap-proach (ω = 1).

Remark. Separability is also a very desirable feature in optimization problems [31]. Onecould therefore use this information also in the global optimization framework that is discussedin the next chapter. This possibility has not yet been further studied in this work.

1 2 3 4 5 6

123456

k = 3

N = 5

1 2 3 4 5 6

123456

k = 4

N = 7

1 2 3 4 5 6

123456

k = 5

N = 11

1 2 3 4 5 6

123456

k = 6

N = 19

1 2 3 4 5 6

123456

k = 8

N = 25

Figure 3.17: Example 3.4, ρ = 10−2, grid type HCC. Top row: index sets Sk, with activeindices (). The active index with largest error indicator is marked in bold red.Bottom row: corresponding grids.

66

3.4 Dimension-adaptive tensor-product interpolation

1 2 3 4 5 6

123456

k = 3

N = 5

1 2 3 4 5 6

123456

k = 4

N = 7

1 2 3 4 5 6

123456

k = 5

N = 11

1 2 3 4 5 6

123456

k = 7

N = 17

1 2 3 4 5 6

123456

k = 8

N = 21

Figure 3.18: Example 3.4, ρ = 10−2, grid type HCGL.

(a)

100

101

102

103

10−6

10−5

10−4

10−3

10−2

10−1

100

ρ = 0.1

number of points N

ereg

ηe

adapt

100

101

102

103

10−6

10−5

10−4

10−3

10−2

10−1

100

ρ = 0.01

number of points N

ereg

ηe

adapt

100

101

102

103

10−6

10−5

10−4

10−3

10−2

10−1

100

ρ = 0.0001

number of points N

ereg

ηe

adapt

(b)

100

101

102

103

10−16

10−14

10−12

10−10

10−8

10−6

10−4

10−2

100

ρ = 0.1

number of points N

ereg

ηe

adapt

100

101

102

103

10−16

10−14

10−12

10−10

10−8

10−6

10−4

10−2

100

ρ = 0.01

number of points N

ereg

ηe

adapt

100

101

102

103

10−16

10−14

10−12

10−10

10−8

10−6

10−4

10−2

100

ρ = 0.0001

number of points N

ereg

ηe

adapt

Figure 3.19: Example 3.4. (a): HCC; (b): HCGL. Comparison of the error decay, dimension-adaptive vs. regular sparse grid.

67

3 Tensor Product and Sparse Grid Interpolation

(a)

1 2 3 4 5 6

123456

k = 3

N = 5

1 2 3 4 5 6

123456

k = 4

N = 7

1 2 3 4 5 6

123456

k = 6

N = 13

1 2 3 4 5 6

123456

k = 7

N = 17

1 2 3 4 5 6

123456

k = 8

N = 21

(b)

1 2 3 4 5 6

123456

k = 3

N = 5

1 2 3 4 5 6

123456

k = 4

N = 7

1 2 3 4 5 6

123456

k = 6

N = 13

1 2 3 4 5 6

123456

k = 7

N = 17

1 2 3 4 5 6

123456

k = 8

N = 21

Figure 3.20: Example 3.5. (a): HCC; (b): HCGL. Legend see Fig. 3.17.

(a) (b)

100

101

102

103

10−6

10−5

10−4

10−3

10−2

10−1

100

number of points N10

010

110

210

−16

10−14

10−12

10−10

10−8

10−6

10−4

10−2

100

number of points N

ereg

ηe

adapt

ereg

ηe

adapt

Figure 3.21: Example 3.5. (a): HCC; (b): HCGL. Comparison of the error decay, dimension-adaptive vs. regular sparse grid.

68

3.4 Dimension-adaptive tensor-product interpolation

We now take a look at higher-dimensional functions in the following two examples.

Example 3.6. In the first higher-dimensional example, we look at the test functions of Genzin ten dimensions, using the same constants as in Section 3.3.6. We compare the dimension-adaptive approach to the regular one for both the Clenshaw-Curtis and the Chebyshev Gauss-Lobatto grid. Here, all dimensions carry about the same importance; the functions are notseparable. Thus, no significant advantage is achieved by the dimension-adaptive approach, al-though a slight improvement can be observed in case of the Gaussian test function in Fig. 3.22.Also shown is the decay of the global error indicator η from Eq. (3.84).

Example 3.7. We cannot expect a significant improvement unless the problem has either someseparable structure, or the importance of the dimensions varies. However, it is often observedin practical applications that with increasing dimensionality, fewer variables have a significantinfluence on the result. In this example, we model this behavior by artificially introducing avarying importance to the test functions of Genz by altering the objective interpolation rangewith respect to each dimension. More precisely, instead of approximating the test function fover the range [0,1]d, we now interpolate over [a1,b1]×·· ·× [ad,bd], where 0 ≤ ai ≤ bi ≤ 1,and the width of the intervals wi are defined as

wi = 10ri− max

i=1,...,dri

,

with normally distributed random numbers ri, i = 1, . . . ,d. The centers of the intervals (ai +bi)/2 are also randomly chosen, but equally distributed in [0,1]. Now, the dimensions are nolonger equally important; in dimensions with small width, less support nodes are required.

We consider the case d = 100. To obtain reasonably scaled function values, the constants b j

of Genz’ test functions were adjusted to

j 1 2 3 4 5b j 1.5 1.75d 1.85/d 7.03 20.4/d

Otherwise, we proceeded as in the previous Section 3.3.6. A histogram of the randomly ob-tained interval widths is shown in Fig. 3.23. The absolute interpolation error, as defined inEq. (3.88), is shown in Fig. 3.24. One observes that the dimension-adaptive approach signifi-cantly outperforms the regular sparse grid refinement.

3.4.4 Performance results

Since the computational complexity of the dimension-adaptive approach will depend on theproblem itself, we only provide performance results for the non-adaptive sparse grid algorithm,but employing the new sparse indices data structure presented in section 3.4.2.1. One can ex-pect the performance of the dimension-adaptive algorithm to lie close to the cost of the non-adaptive algorithm of the same dimension if all dimensions carry equal importance (and thus, aconventional sparse grid is generated by the algorithm). Otherwise (if the sparse grid is refinedprimarily with respect to some dimensions only), one can expect that the algorithm will per-form according to its effective dimension, i.e. the performance curve will lie close to the curve

69

3 Tensor Product and Sparse Grid Interpolation

(a)

100

102

104

106

10−10

10−5

100

oscillatory

100

102

104

106

10−5

10−4

10−3

10−2

10−1

product peak

100

102

104

106

10−5

10−4

10−3

10−2

10−1

corner peak

100

102

104

106

10−6

10−4

10−2

100

Gaussian

100

102

104

106

10−5

10−4

10−3

10−2

continuous

ereg

eadapt

η

(b)

100

102

104

106

10−15

10−10

10−5

100

oscillatory

100

102

104

106

10−6

10−4

10−2

100

product peak

100

102

104

106

10−5

10−4

10−3

10−2

10−1

corner peak

100

102

104

106

10−10

10−5

100

Gaussian

100

102

104

106

10−5

10−4

10−3

10−2

continuous

ereg

eadapt

η

Figure 3.22: Example 3.6, dimension-adaptive vs. regular, d = 10. (a): HCC; (b): HCGL.

70

3.4 Dimension-adaptive tensor-product interpolation

Figure 3.23: Ex. 3.7: Histogram of inter-val widths wi, i = 1, . . . ,d.

10−4

10−3

10−2

10−1

100

0

5

10

15

20

25

interval width

num

ber

of d

imen

sion

s

100

102

104

106

10−15

10−10

10−5

100

oscillatory

100

102

104

106

10−10

10−8

10−6

product peak

100

102

104

106

10−15

10−10

10−5

100

corner peak

100

102

104

106

10−15

10−10

10−5

100

Gaussian

100

102

104

106

10−15

10−10

10−5

100

continuous

εreg

(CC)

εreg

(CGL)

εadapt

(CC)

εadapt

(CGL)

Figure 3.24: Example 3.7, dimension-adaptive vs. regular, d = 100.

71

3 Tensor Product and Sparse Grid Interpolation

of the regular sparse grid with the same dimension as the effective dimension of the dimension-adaptive one. This is obvious in case of the interpolation algorithm , since noadditional computational effort arises from the adaptively constructed grid. It is also true incase of the adaptive construction of the grid with , since the overhead for book-keeping of the indices is of order O(d log( )+d min(d,max(n,1)), and thus, small comparedto the main work done in the innermost loop by calling the

function. Fig. 3.25 im-

pressively demonstrates the efficiency of the proposed algorithms and data structure that doesnot degenerate even for very high dimensions d > 100. The results were obtained using animplementation in MATLAB V7.0 running on a Linux i686 3.06 GHz PC.

(a) (b)

101

102

103

104

105

106

107

10−3

10−2

10−1

100

101

102

103

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16d = 32d = 64d = 200d = 2000

101

102

103

104

105

106

107

10−3

10−2

10−1

100

101

102

103

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16d = 32d = 64d = 200d = 2000asymptotic O(N)

(c) (d)

101

102

103

104

105

106

107

10−2

100

102

104

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16d = 32d = 64d = 200d = 2000

101

102

103

104

105

106

107

10−2

100

102

104

time

[s]

number of nodes N

d = 1d = 2d = 4d = 8d = 16d = 32d = 64d = 200d = 2000asymptotic O(N)

Figure 3.25: Performance in high dimensions with sparse multi-index storage scheme. (a):Time to compute the hierarchical surpluses (CC-grid), (b): Time to evaluate in-terpolant 1000 times (CC-grid), (c): Time the compute the hierarchical surpluses(CGL-grid), (d): Time to evaluate interpolant 1000 times (CGL-grid).

72

4 Fuzzy Calculus using Sparse Grids

Having provided a tool to obtain a surrogate function (that can be made arbitrarily accuratewith increasing sparse grid resolution), we will now show how to use a sparse grid interpolantA( f ) to efficiently compute functions of fuzzy numbers according to the extension principle.Firstly, we introduce the notation for the required discretization of the fuzzy numbers. Then,we describe the procedure in detail.

4.1 Discretization of the fuzzy numbers

Let pi, i = 1,2, . . .,d denote the fuzzy-valued input parameters with the membership func-tions µ pi(xi), µi : R → [0,1]. We obtain an arbitrarily accurate discrete formulation of thefuzzy numbers with m → ∞ by decomposing them into sets of m + 1 intervals [35] Pi =

I(0)i , I(1)

i , . . . , I(m)i

with the intervals of confidence

I( j)i =

[a( j)

i ,b( j)i

], a( j)

i < b( j)i , j = 0, . . . ,m. (4.1)

The intervals of confidence [46] are also called α-cuts with the α-level α = j/m ∈ [0,1]. Thus,this discretization is usually referred to as α-cut representation. Note that by definition, a fuzzynumber is convex, i.e. any fuzzy number can be decomposed into its α-cuts with the property

I( j+1)i ⊆ I( j)

i , ∀ j ∈ 0, . . . ,m−1. (4.2)

In the following, we refer to I(0)i as the support of the fuzzy number pi. I(0)

i must be bounded,i.e. must be a closed interval. We define the Cartesian product of the supports as the supportbox

Ω = I(0)1 × I(0)

2 ×·· ·× I(0)p ,

which is a d-dimensional interval vector.

4.2 Summary of the procedure

The procedure is composed of two main parts:

• Part 1. Determining the sparse grid surrogate function, and

• Part 2. Computing the extension principle solution by a suitable method.

73

4 Fuzzy Calculus using Sparse Grids

We first compute the sparse grid interpolant A( f ) with sufficient accuracy for the support boxΩ of the fuzzy input parameters, using only a low number of real-valued function evaluations.Depending on the objective function characteristics and accuracy requirements, this can beeither a regular or a dimension-adaptive interpolant, using either piecewise linear or polynomialbasis functions. The hierarchical structure of the sparse grid interpolation scheme allows usto subsequently increase the number of support nodes until a given relative or absolute errortolerance is reached.

In case of convex fuzzy sets and continuous functions, the extension principle can be for-mulated as a global optimization problem that must be solved for each considered α-cut (seeSection 2.2), i.e. in Part 2 of the algorithm, by replacing the objective function f with thesparse grid interpolant A( f ), one must solve

c( j) = minx∈Ω( j)

A( f )(x), d( j) = maxx∈Ω( j)

A( f )(x), (4.3)

where Ω( j) = I( j)1 × ·· · × I( j)

d are d-dimensional boxes formed by the Cartesian product of

the intervals of confidence I( j)i of each α-cut with index j of the fuzzy input parameters pi,

i = 1, . . . ,d, j = 0, . . . ,m. We denote the resulting intervals of confidence forming the discreterepresentation of the fuzzy result by J( j) = [c( j),d( j)]. We will study two approaches in furtherdetail that are of varying accuracy and computational cost, and provide the means to use themwithin our approach in Section 4.3.

The achieved accuracy of the fuzzy result depends on both parts of the algorithm. The initialcontributor to the quality of the fuzzy result is of course the accuracy of the interpolant, whichcan be easily monitored during its hierarchical construction. The order of convergence in themaximum norm is well known, as stated in Eqs. (3.46) and (3.48). We thus have a solid basisfor the second part of the algorithm. The quality of the final fuzzy result, however, can still varydepending on the actual fuzzy arithmetic algorithm chosen to implement Zadeh’s extensionprinciple. If one uses a method that computes the global minimum and the global maximumof the surrogate function for each α cut exactly, one can eliminate the error resulting fromPart 2. On the other hand, if one uses an approximative method to solve the global optimizationproblem, a second error source is introduced.

4.3 Computing the extension principle solution

In general, one is free to select any suitable algorithm to solve the optimization problem givenby Eq. (4.3). Since the evaluation of sparse grid interpolants is explicitly given for single pointsin the algorithms of Section 3, implementations of the extension principle requiring only real-valued function evaluations are applicable without any major additions or modifications. Thetransformation method [35, 36], for example, is based on real-valued function evaluations, wecan therefore directly apply it by just replacing the function evaluations of f by evaluations ofthe surrogate function A( f ). However, computationally more efficient and usually more accu-rate are incomplete global search methods specifically designed for sparse grids. We thereforeprovide a modified coordinate search algorithm in Section 4.4. It is also possible to implementcomplete search algorithms based on interval extensions of A( f ), i.e. implement inclusion

74

4.4 Applying incomplete global search methods

functions [A( f )] that take interval vectors (also called boxes) instead of single points as argu-ments. By doing so, we can apply branch-and-bound optimization algorithms based on intervalarithmetic. This approach will be discussed in Section 4.5.

4.4 Applying incomplete global search methods

The global optimization problems arising for each α-cut (Eqs. (4.3)) can be solved in a straight-forward way by incomplete global search methods. In general, a drawback of incomplete meth-ods is the fact that they cannot guarantee that the global optimum has been found, since thesearch might have terminated prematurely according to the applied stopping criteria. The moststraightforward approach of an incomplete global search method is the globalization of localsearch methods by multiple random starts, but it is of course more efficient to use the alreadycomputed sparse grid points to achieve globalization, as described below.

Modified coordinate search algorithm As an example of an incomplete global search algo-rithm, we have implemented a variation of a coordinate search algorithm (often also known ascompass search) [57]. If piecewise multilinear sparse grid interpolants are used, the smallestsearch step-length to be used can be limited to the minimum sparse grid step width, since theoptimum can only lie at the points of the full grid Hfull,q,d , or at the boundary of the search box(see Section 4.5.1). The modified coordinate search algorithm for the Clenshaw-Curtis grid isgiven in Algorithm 11.

A standard coordinate search algorithm can only guarantee convergence to a local minimizer.In case of regular sparse grids Aq,d( f ), we can modify the method such that with increasingaccuracy of the sparse grid interpolant, it becomes globally convergent. From the constructionof the interpolant Aq,d( f ), we have a set of grid points Hq,d and corresponding function valuesavailable. As the parameter q goes to infinity, the set Hq,d forms a dense subset of the unithypercube, i.e., given any point x in the hypercube and any δ > 0, a grid point lies withina distance δ of x. Hq,d is dense since it contains the regular full grid X i f × ·· · × X i f withi f = floor(q/d). If we select the optimum over all sparse grid points contained in the searchbox as the start point of our search algorithm, we will eventually use a start point within theattraction of the global optimizer, and the method will converge to the global optimum forq → ∞.

In practice, the above result is only of theoretical importance, since the aim is to use sparsegrid interpolants of only small depth, especially in case of the dimension-adaptive approach.Assuming that the interpolant approximates the objective function reasonably well with a lownumber of support nodes, it may seem unlikely that this interpolant would exhibit optima withattraction radii that are not sufficiently covered by the sparse grid points. However, if the sparsegrid interpolant contains several optima of rather similar magnitude, then one often observesthat only a slightly suboptimal optimizer is found, although the search is started from the bestavailable point of the grid. Despite this drawback, the proposed modified coordinate searchoften gives sufficiently accurate results from an engineering point of view.

75

4 Fuzzy Calculus using Sparse Grids

Algorithm 11 Coordinate search on (regular) Clenshaw-Curtis sparse grids.

In: Ω = [a(0)1 ,b(0)

1 ]×·· ·× [a(0)d ,b(0)

d ]: Support box of fuzzy input variables.Aq,d( f ): Sparse grid interpolant of f .HCC

q,d (Ω): Set of sparse grid points, scaled to Ω.I = [a1,b1]×·· ·× [ad,bd]: Box of confidence intervals from Eq. (4.1).

Out:x, ymin: Minimizer and minimum.

Let x = argminAq,d( f )(x) | x ∈ HCCq,d (Ω)∩ I.

Let ymin = Aq,d( f )(x).Let ∆ = 1/2floor(q/d) be the initial value of the step-length control parameter.Let E⊕ be the set of coordinate directions ei | i = 1, . . . ,d, ei is ith unit vector in R

d .While ∆ ≥ 1/2q−d

If there exists ei ∈ E⊕ such that Aq,d( f )(x) < ymin, with

x ∈ xli,x

ri,

xli =

x−∆ei(b

(0)i −a(0)

i ) = xl, xl ∈ I,

x+ ei(ai− (x)i), xl /∈ I,

xri =

x+∆ei(b

(0)i −a(0)

i ) = xr, xr ∈ I,

x+ ei(bi− (x)i), xr /∈ I,

Then

x = argmin

Aq,d( f )(x) | x ∈ xli,x

ri | i = 1, . . . ,d

.

ymin = Aq,d( f )(x).

Else contract the step-length control parameter: Let ∆ = 12∆.

End

Adapting other local search methods The modified coordinate search algorithm choosesits steps along the d coordinate directions, and its iterates always remain on the points of thefull grid (including the boundary points of the search box). This makes a lot of sense whenoptimizing a piecewise multilinear interpolant, since we know that the optimizer lies on a fullgrid point. However, in case of higher-order polynomial interpolation, as with the Chebyshev-Gauss-Lobatto grid, the optima are no longer restricted to any subset of points in the searchdomain, and it is thus desirable to use other search algorithms that are more flexible withrespect to the search direction.

Similar to the coordinate search algorithm from the previous section, we can always startthe search from the best available point of the sparse grid. To impose the box constraints onthe optimization problem, we can add a penalty function to the sparse grid interpolant, and

76

4.5 Applying global search methods based on interval arithmetic

optimize, for each considered α-level, the function

B( f ,Ω( j))(x) = A( f )(minmaxx1,a( j)1 ,b( j)

1 , . . . ,minmaxxd ,a( j)d ,b( j)

d )+ p( f ,Ω( j))(x),

p( f ,Ω( j))(x) =

0 x ∈ Ω( j)

w( f ) ·h(x∗) x /∈ Ω( j) , x∗i = maxa( j)i − xi, xi −b( j)

i , 0, i = 1, . . . ,d,

where h(x∗) : Rd+ → R+ is strictly monotonic increasing (minimization) or decreasing (max-imization) for all x∗i , i = 1, . . . ,d (e.g. h(x∗) = ±‖x∗‖2), and w( f ) is a suitably chosen scalingfactor (such as the range of the function values at the sparse grid points).

Of the multitude of the available classes of algorithms for local optimization, we have suc-cessfully tested this approach using the well-known Nelder-Mead simplex method, which rep-resents a derivative-free method. Note that other, non-direct optimization methods require thecomputation of the gradient and/or the Hessian, which can be done both algorithmically (i.e.by providing suitable algorithms) and numerically (by finite differences).

4.5 Applying global search methods based on intervalarithmetic

In contrast to the approach described in Section 4.4, we will now formulate methods to per-form a complete search. Thus, we will solve the global optimization problem given by Eq. (4.3)without introducing an additional possible source of error. To do this, we use the tools pro-vided by interval analysis. To apply fuzzy arithmetic based on interval arithmetic, we mustdefine an interval inclusion [A( f )] of the sparse grid interpolant. An interval inclusion functiontakes interval boxes as input arguments, and gives a guaranteed inclusion of the output rangeof the function as result. Different types of inclusion functions can be implemented with vary-ing computational cost. In the following, we will discuss the minimal inclusion function, thenatural inclusion function, and the centered inclusion function. The natural and the centeredinclusion functions can be obtained with significantly lower computational effort than the min-imal inclusion function, but at the price of overestimation. We will also show how to obtain aninclusion of the gradient vector of A( f ), since it is required for the centered inclusion function,and it is also often used to perform a monotonicity test in branch-and-bound algorithms.

In the following, we restrict this approach to piecewise multilinear sparse grids; detailed al-gorithms are given for the regular Clenshaw-Curtis grid. The provided algorithms can be easilyadapted to the dimension-adaptive case. Although higher order interval inclusion functions candefinitely be constructed for the sparse grid polynomial interpolation scheme discussed in Sec-tion 3.3.3 by employing, e.g., Taylor forms [63] or lower bound functions based on the Bern-stein form [24], this was not further investigated, mainly due to the following reasons: (1) Theinclusion functions will yield much more pessimism, since the simplification using the intervalhull from Eq. (4.6) cannot be applied due to the global support of the basis functions. (2) Com-puting the bounds of a higher-order polynomial basis function is computationally much moreinvolved. (3) In the context of this thesis, the high-dimensional case is of great significance.But even interval inclusions of piecewise linear interpolants did not scale well to higher di-

77

4 Fuzzy Calculus using Sparse Grids

mensions in numerical tests – Thus, due to the increased pessimism, the performance can beexpected to decline even more in the polynomial case.

4.5.1 The minimal inclusion function

According to the definition by Jaulin et. al. [44], an inclusion function [ f ] is minimal if for anybox I, [ f ](I) is the smallest box that contains f (I).

The minimal inclusion function can be computed by sampling all points at the full grid witha mesh width chosen according to the sparse grid interpolation depth, evaluating these pointsusing Aq,d( f ), and computing the maximum and minimum over all results. This results in aminimal interval, since a piecewise multilinear interpolant has its maximum and minimum val-ues over a search box I at the full grid points Hfull,q,d ∩ I, with Hfull,q,d according to Eq. (3.41),or at a point on the boundary of I. We define

[Aq,d( f )]∗(I) =[

minAq,d( f )(x) | x ∈ Hfull, maxAq,d( f )(x) | x ∈ Hfull], with (4.4)

I = I1 × . . .× Id, Ii = [ai, bi], i = 1, . . . ,d,

Y i =(x | x = a(0)

i + x(b(0)i −a(0)

i ), x ∈ Xq−d+1∩ Ii)∪ai,bi,

Hfull = Y 1 × . . .×Y d.

In the above equations, we use a(0)i , b(0)

i as defined in Eq. (4.1) and the sets X i as definedin Eq. (3.44). With this simple method, we can compute the minimal resulting interval (i.e.without overestimation) for any interval box I ⊆ Ω, using N∗ = #Hfull ≤ #Hfull,q,d evaluationsof Aq,d( f ). See Fig. 4.1 for an example.

In case of the minimal inclusion function [Aq,d( f )]∗, we can directly give an efficient algo-rithm to obtain the fuzzy result. Instead of computing the fuzzy result Q = J(0), . . . ,J(m)by applying the minimal inclusion function [Ap,q( f )]∗ to each α-cut separately, we proceedas follows: By using the convexity property Eq. (4.2), we eliminate recurring points in Hfullfor subsequent α-cuts (similar to the idea presented in [49]), and arrive at Algorithm 12. Thecomplexity of this algorithm is similar to the one of the transformation method if the numberof α-cuts (m+1) ' 2q−d , and it gets better in comparison with increasing m.

4.5.2 The natural inclusion function

The natural inclusion function [Aq,d( f )]n is immediately obtained by replacing each real vari-able x by an interval variable I and each real operator by its interval counterpart (for variousexamples, see [44, pp. 29–32]).

Note that the natural inclusion [aij]n of the basis functions ai

j is minimal (see Fig 4.2 (a)). Byreplacing the real basis functions in the Smolyak tensor product formula (3.53) by its interval-valued counterparts, we obtain the natural inclusion function [Aq,d( f )]n with

[∆Ak+d,d( f )]n = ∑|i|=k+d

∑j([ai1

j1]n ⊗·· ·⊗ [aid

jd)]n) ·

(f (xi

j)−Ak+d−1,d( f )(xij))

(4.5)

78

4.5 Applying global search methods based on interval arithmetic

Figure 4.1: Example: Sparse grid pointsHCC

5,2 (Ω), Ω = [0,1]2, andthe set of full grid pointsHfull (including bound-ary points) for the boxI = [0.1,0.9]× [0.05,0.8]. 0 0.2 0.4 0.6 0.8 1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1sparse grid pointsfull grid points w/ boundary points

Algorithm 12 Minimal fuzzy inclusion [Aq,d( f )]∗(p1, . . . , pd).

In: Aq,d( f ): Sparse grid interpolant of f .m+1: Number of α-cuts.

Pi = I(0)i , . . . , I(m)

i : Discretized fuzzy input parameters, with

I( j)i = [a( j)

i ,b( j)i ], j = 0, . . . ,m, i = 1, . . . ,d.

Out:Q = J(0), . . . ,J(m): Discretized fuzzy result, J( j) = [c( j),d( j)].

Let Y i = /0, i = 1, . . . ,d.For j = m DownTo 0

For i = 1 To dY i

old = Y i.

Y i = x | x = a(0)i + x(b(0)

i −a(0)i ), x ∈ Xq−d+1∩ I( j)

i .

Y i = Y i ∪a( j)i ,b( j)

i .End∆H j

full = Y 1 × . . .×Y d \ Y 1old × . . .× Y d

old.c( j) = minAq,d( f )(x) | x ∈ ∆Hfull. d( j) = maxAq,d( f )(x) | x ∈ ∆Hfull.If j < m Then c( j) = minc( j+1),c( j). d( j) = maxd( j+1),d( j).

End

79

4 Fuzzy Calculus using Sparse Grids

from (3.52). Due to the non-overlapping support of the piecewise multilinear tensor productbasis functions for equal i in Eq. (4.5) in case of the grids HCC and HNB, we can further improvethis natural inclusion function by replacing the inner sum by the interval hull operator t [44, p.18]. We call this inclusion function the reduced natural inclusion function [Aq,d( f )]n,red with

[∆Ak+d,d( f )]n,red = ∑|i|=k+d

j

[([ai1

j1]n ⊗·· ·⊗ [aid

jd)]n)

·(

f (xij)−Ak+d−1,d( f )(xi

j))]

. (4.6)

Remark: This simplification does not apply to the grid HM in general, since sub-grids witha multi-index entry one (1) do have overlapping supports.

In comparison to the minimal inclusion function [Aq,d( f )]∗, computing [Aq,d( f )]n(I) and[Aq,d( f )]n,red(I) requires only a single interval-valued evaluation composed of at most N∗ =

#HCC,NBq,d inclusion functions of the multilinear basis functions ([ai1

j1]n ⊗ ·· · ⊗ [aid

jd]n). Thus,

the natural inclusion functions are much cheaper to obtain than [Aq,d( f )]∗, but at the cost ofoverestimation. We explicitly provide the natural inclusion function of the basis functions forthe Clenshaw-Curtis grid type in the following; others can be obtained in a similar manner.

Natural inclusion function of the basis functions, Clenshaw-Curtis grid We only have tomake a minor adjustment to the definition of the basis functions [ai

j]n for i > 1 and 1/(mi−1)∈|I− xi

j|, since in this case, the interval boolean operator < does not give a unique result of true(1) or false (0) (see [44, p. 41] for the extension of the boolean operators to intervals). Takingthis special case into account, and defining I = [a,b], r = 1/(mi−1), we arrive at

[c,d] := |I − xij| =

[a− xi

j,b− xij

], if a− xi

j ≥ 0,[−b+ xi

j,−a+ xij

], if b− xi

j ≤ 0,[0, max

(|a− xi

j|, |b− xij|)]

, otherwise,

[aij]n(I) =

1− r · [c,d], if d < 1/r,

0, if c ≥ 1/r,

[0,1− cr], otherwise.

(4.7)

4.5.3 The centered inclusion function

One can also construct higher order inclusion functions, such as the mixed centered inclusionfunction [34, 44]

[Aq,d( f )]c(I) = Aq,d( f )(c)+d

∑l=1

[g(Aq,d( f ))l](I1, . . . , Il,cl+1, . . . ,cd)(Il − cl),

where [g(Aq,d( f ))l] is an inclusion function of the lth component of the gradient vector ofAq,d( f ), and c = (c1, . . . ,cd) is the midpoint of the interval box I. One cannot expect a tighter

80

4.5 Applying global search methods based on interval arithmetic

interval inclusion of the basis function itself, regardless of the input box size, since the inclu-sions of the basis functions are already minimal for the natural inclusion function. In fact, thecentered inclusion of the basis function even produces a wider result if the peak of the basisfunction is contained in I (see Fig. 4.2 (b)). However, once the hierarchical structure of theinterpolant is considered, the additional derivative information translates into tighter intervalbounds with decreasing box size.

Figure 4.2: Comparison of natural (a) andcentered (b) inclusion functionfor an interval with xi

j ∈ I.

(a) (b)PSfrag replacements

I I

[aij]c(I)[ai

j]n(I)

x x

y y

Figure 4.3: Comparison of inclusionfunctions [A4,1( f )]:(a): reduced natural,(b): centered,(c): n+c combined.

PSfrag replacements

k = 0k = 0

k = 1k = 1

k = 2k = 2

k = 3k = 3

I1I1I1I1I1I1 I2I2I2I2I2I2 I3I3I3I3I3I3 I4I4I4I4I4I4

(a)(a) (b)(b) (c)(c)

ffffff

[A4,1( f )]n,red[A4,1( f )]n,red [A4,1( f )]c[A4,1( f )]c [A4,1( f )]nc[A4,1( f )]nc

The hierarchical, additive structure of Aq,d( f ) permits an interesting additional inclusionfunction constructed from the mixed centered and the natural inclusion function, which we call

81

4 Fuzzy Calculus using Sparse Grids

the nc inclusion function [Aq,d( f )]nc. In a nutshell, we use the centered inclusion function, butreplace the contribution [∆Ak,d( f )]c at a level k by its natural counterpart [∆Ak,d( f )]n,red if theresulting interval is smaller. As a result, the combined inclusion function nc gives an improvedinclusion compared to both the natural inclusion function and the centered inclusion function.Fig. 4.3 compares [Aq,d( f )]n (a) to [Aq,d( f )]c (b) and [Aq,d( f )]nc (c) for a function f of onevariable (d = 1). In the example, the centered inclusion is basically exact (apart from roundingerrors) for the levels k = 0 to k = 2, since for the chosen intervals, the peaks at the support nodesxi

j are located at the interval bounds, and the typical cone (see Fig. 4.2 (b)) characterizing thecentered inclusion function degenerates to a line.

4.5.4 Computing the inclusion of the gradient vector

In addition to using an inclusion of the gradient vector to compute the centered inclusion func-tion, one can also conduct a monotonicity test based on an interval-valued evaluation of thegradient to eliminate boxes, or at least to reduce the dimension of boxes. This test is commonlyperformed in branch-and-bound algorithms [34] of global optimization to reduce the compu-tational effort. We therefore show how to obtain an inclusion of the (weak) partial derivativesof the interpolant (weak, since the piecewise multilinear interpolant is only continuous, but notcontinuously differentiable).

The partial derivatives of (3.52) are obtained to

∂ (∆Ak+d,d( f ))

∂xl= ∑

|i|=k+d∑

j

[(ai1

j1⊗·· ·⊗ail−1

jl−1 ⊗ (ailjl)′⊗ail+1

jl+1 ⊗·· ·⊗aidjd)

·(

f (xij)−Ak+d−1,d( f )(xi

j))]

, (4.8)

l = 1, . . . ,d. Thus, we can compute the partial derivatives of Aq,d( f ) composing the gradientvector g(Aq,d( f )) by applying the Smolyak formula (3.53), replacing the ∆Ak+d,d( f ) by (4.8).Analogously, we get its natural interval inclusion [g(Aq,d( f ))]n by replacing the real basisfunctions by its interval counterparts.

In terms of computational complexity, each component of the gradient vector is composed ofat most #Hq,d partial derivatives of the multivariate basis functions (ai1

j1⊗·· ·⊗ail−1

jl−1 ⊗ (ailjl)′⊗

ail+1jl+1 ⊗·· ·⊗ aid

jd). The complete gradient vector can thus be obtained at a cost proportional to

N∗g = d ·#Hq,d.

Inclusion of the derivatives of the basis functions, Clenshaw-Curtis grid As with thenatural inclusion function of the basis functions, we provide the inclusion of the derivatives ofthe basis functions ai

j for the Clenshaw-Curtis grid in detail, which are needed to construct thegradient vector. Inclusions of the derivatives for the other grid types can be obtained similarly.

82

4.5 Applying global search methods based on interval arithmetic

Computing the natural interval inclusion of the derivative (aij)′ yields

[a11]′n(I) = 0 for i = 1, and

[aij]′n(I) =

−(mi −1) · [u]′n(I), if |I− xi

j| < 1/(mi−1),

0, otherwise,(4.9)

with u′(x) =d|x−xi

j|dx . To resolve the ambiguous inequality condition |I − xi

j| < 1/(mi −1), andto correctly compute the interval-valued inclusion of the derivatives, we have to consider sevencases, which are depicted in Figure 4.4.

case conditions [aij]′(I)

1 b < xij − r [0,0]

2 a < xij + r [0,0]

3 a > xij − r and b < xi

j [s,s]4 a > xi

j and b < xij + r [−s,−s]

5 a ≤ xij and b ≥ xi

j [−s,s]6 a ≤ xi

j − r and b ≥ xij − r and b < xi

j [0,s]7 b ≥ xi

j + r and a ≤ xij + r and a > xi

j [−s,0]

with s = mi −1.

PSfrag replacements1

2

3

4

5

6

7

a b

xij

rr

Figure 4.4: Basis function shape and different resulting derivatives for different positions of theinterval I = [a,b] w.r.t. the peak xi

j and the support with r = 1/(mi−1).

4.5.5 A branch-and-bound method

Branch-and-bound algorithms split a problem recursively into subproblems. A subproblemis eliminated as soon as it is shown that it cannot contain the solution [64]. Interval branch-and-bound methods for global optimization usually start with an initial box, and subdivide itrepeatedly into sub-boxes. Sub-boxes that are guaranteed not to contain a global minimizerare removed, while the remaining boxes are split further until a specified accuracy is achieved.To determine whether a box does not contain a global minimum, various tests are applied thatutilize interval inclusion functions.

With the previously defined interval inclusion functions for piecewise multilinear sparsegrids, we can use an interval branch-and-bound method (e.g. [44, p. 119]) to solve the op-timization problem involving the sparse grid interpolant (as stated in Eq. (4.3)). We can thenemploy two tests to eliminate boxes, a cut-off test and a monotonicity test. An important differ-ence compared to standard interval branch-and-bound algorithms lies in the bisection rule. We

83

4 Fuzzy Calculus using Sparse Grids

denote the width of an interval I = [a,b] by w(I) = b−a, and the width of a box I = I1×·· ·× Id

by w(I) = maxdi=1 w(Ii). Since the minimum function value can only be attained at the full grid

points Hfull,q,d ∩ I or at a boundary point of the box, we bisect along the coordinate direction iwith w(Ii) = w(I) such that the boundaries along the cut are shifted to the nearest hyperplanesof grid points towards the inside of the two new boxes. This results in the boxes being disjointby a gap (e.g. ε = 1/2q−d , q > d, for the Clenshaw-Curtis grid in case of the domain of f beingthe unit cube), it also guarantees that the boxes will eventually degenerate to points lying onthe full grid or the boundary and become removed.

By applying the branch-and-bound algorithm repeatedly to the boxes formed by the intervalsof confidence of subsequent α-cuts of the fuzzy input parameters to compute both the mini-mum and the maximum, we can compute the exact range of the interpolant for each α-cut.Furthermore, if one proceeds from the highest α-cut down to the support box, one can easilyadd another test to the optimization algorithm: removing boxes as soon as they lie entirely inthe box formed by the intervals of the next-higher α-cut.

4.6 Numerical results

In Section 4.6.1, we will briefly comment on the performance of the sparse grid optimizationalgorithms introduced in Sections 4.4–4.5, which may be used for Part 2 of the procedure. InSection 4.6.2, we will illustrate the overall performance of our new sparse grid-based fuzzyarithmetic algorithm for test functions with different distinct properties. We assess the per-formance by relating the relative error of the fuzzy result to the number of required functionevaluations. For a definition of the relative error of a fuzzy number, see Section 2.1.6. Forcomparison, we have included the results obtained with the general transformation method[35] and the general transformation method considering recurring permutations [50]. Finally,in Section 4.7, we give examples for objective functions where the proposed method cannot beapplied successfully.

4.6.1 Performance of the optimization algorithms

We have performed extensive numerical tests using some well-known test problems [18] toanalyze the proposed optimization algorithms. In summary, the following suggestions can bemade. The modified coordinate search algorithm representing an incomplete search methodis by far the fastest of the proposed global optimization algorithms, but may not give theexact global optimum. However, experiments indicate that the error from the optimizationpart is often zero, or otherwise of similar order as the error resulting from the interpolation.The minimal inclusion function (Eq. (4.4)) represents a complete search algorithm consid-ering all full grid points, but is considerably more expensive for large d,q. The intervalbranch-and-bound method is well suited for higher values of q and low d. We suggest touse the combined inclusion function as discussed in Section 4.5.3, which often provides atighter inclusion than the mere natural inclusion regardless of the input interval width, andalso exhibits the higher-order convergence of a centered inclusion. Figure 4.5 gives a vi-sual impression of the performance of the branch-and-bound algorithm for different inclusion

84

4.6 Numerical results

functions for the minimization of the interpolant A9,2( fBR) of Branin’s function fBR(x1,x2) =

( 5π x1 − 5.1

4π2 x21 + x2 − 6)2 + 10(1− 1

8π )cosx1 + 10, with fBR : [−5,10]× [0,15] → R. Unfor-tunately, interval-based methods seem unsuited for solving difficult sparse grid optimizationproblems of higher dimension, since the number of sub-boxes to search may still be large dueto the pessimism of the inclusion functions and/or the objective function characteristics (e.g.many regions potentially containing the global optimum). In most cases, using an incompletesearch method is therefore the best choice, such as the presented modified coordinate searchalgorithm.

(a)

PSfrag replacements

2695 sub-boxes

(b)

PSfrag replacements

495 sub-boxes

(c)

PSfrag replacements

415 sub-boxes

(d)

PSfrag replacements

395 sub-boxes

(e)

PSfrag replacements

235 sub-boxes

(f)

PSfrag replacements

203 sub-boxes

Figure 4.5: Comparison of pavings obtained by the branch-and-bound optimization algorithmfor the Branin function with different inclusion functions. (a): natural, (b): cen-tered, (c): nc (all three without the application of the monotonicity test based on theinclusion of the gradient), (d)–(f): natural, centered, nc, including the monotonicitytest. Boxes degenerated to a line are marked in red color. Boxes degenerated to asingle point are indicated by a black dot.

85

4 Fuzzy Calculus using Sparse Grids

4.6.2 Overall performance results

We now take a look at the overall performance of the proposed fuzzy arithmetic algorithmbased on sparse grids. The test functions we have used are listed in Table 4.1. We have takensymmetric triangular fuzzy numbers as input parameters for all test functions. However, themethod is not restricted to this type of shape function, any convex fuzzy set, i.e. any fuzzynumber or fuzzy interval could be used. Also provided are the support box of the fuzzy inputparameters taken for each test function, i.e. the input fuzzy-valued inputs of f1 are given by thetriangular fuzzy numbers p1 = 〈2.5,2.5,2.5〉TFN and p2 = 〈3,2,2〉TFN since Ω1 = [0,5]× [1,5].The functions f1– f3 are taken from [49], the functions f4, f5, f7 are taken from [7], f8 from[18]. These test functions could be treated in a simpler way than within the framework of sparsegrids, since the functions are analytic and inexpensive to evaluate. But we have intentionallykept the numerical examples simple for mainly two reasons: (1) the exact result can be easilyobtained, and (2) the behavior of the method with different characteristics of the objectivefunction becomes apparent.

As an example for a model with multiple output parameters, we consider the second orderdifferential equation

f6 : Q′′(t)+aQ′(t)+b = 50cos(t) (4.10)

from [12, pp. 145–162] simulating an electrical circuit, with uncertain initial conditions Q(0)=〈5,1,1〉TFN and Q′(0) = 〈1,1,1〉TFN and uncertain parameters a = 〈2,1,1〉TFN, b = 〈4,1,1〉TFN.

Table 4.1: Test functions.

i function fi(x) : Ωi → R support box Ωi characteristics1 cos(πx1)x2 [0,5]× [1,5] Non-monotonic w.r.t. x1

2[(x1 −2)4 +(x2 −2)2 +0.2

]−1[0,5]× [1,5] One local extremum

3 3(1− x1)2 exp[−x2

1 − (x2 +1)2] [−3,3]× [−2,2] Multiple local optima−10( x1

5 − x31 − x5

2)exp[−x21

−x22]− 1

3 exp[−(x1 +1)2 − x22]

44∏i=1

(c−1

i +(xi−wi)2)−1

[0,1]4 Product peak (Genz)

5 cos(2πw1 +

d∑

i=1cixi)

[0,1]8 Oscillatory (Genz)

7 exp(−

d∑

i=1ci · |xi−wi|

)[0,1]2 Continuous (Genz)

8 −5∑

i=1

1(x−(A)i)(x−(A)i)T +ci

, [0,10]4 5 sharp peaks (Shekel)

where A ∈ R5×3, c ∈ R5

The constants for the test functions of Genz ( f4 to f7) have been taken to:f4: c = (0.8,0.5,1.3,1.4), w = (0.2,0.4,0.3,0.1),f5: c = (0.4,0.2,0.3,0.2,0.6,0.2,0.1,0.2), w1 = 0.2,f7: c = (2.1,2.2), w = (0.3,0.7).

86

4.6 Numerical results

The time-dependent fuzzy-valued result Q(t) was computed using piecewise multilinear sparsegrid interpolants based on function evaluations obtained numerically using MATLAB’s

solver for t ∈ [0,5] at 100 equally spaced steps. A sparse grid with interpolation depth n = 1using only nine crisp evaluations already gave a good indication of the result (Fig. 4.7(a)).With n = 3 (137 evaluations), an accurate contour plot with a relative error of about 1% wasobtained (Fig. 4.7(b)).

Figure 4.6 shows the fuzzy-valued outputs of the test functions f1– f8. For the ODE modelf6, the fuzzy-valued output Q(4) at time t = 4 is shown. Figure 4.8 shows convergence plots forthe fuzzy-valued results of the eight test functions. Note that the relative error of all methodsis provided with respect to the discrete solution with (m + 1) = 501 α-cuts. We have used anidentical number of α-cuts for the sparse grid-based solution such that the sparse grid errorcurves shown in Figs. 4.8, 4.9 are not affected by the discretization of the fuzzy numbers.

Performance using piecewise linear sparse grids One can observe the excellent asymp-totic error decay according to Eq. (3.46) with increasing number of function evaluations for thesmooth test functions of two variables f1 to f3 (Fig. 4.8 (a)–(c)), which all satisfy the smooth-ness properties defined in Eq. (3.45). As the dimension of the test functions increases, theefficiency of the sparse grid scheme becomes even more apparent (Fig. 4.8 (d)–(f)), especiallycompared to a method sampling points at the full grid, such as the transformation method.

Performance using the higher-order polynomial interpolant Using the higher-order in-terpolant based on the grid HCGL and optimization by a local search starting from the bestavailable point resulted in the rapid error decay known from interpolation in case of f1– f2, f4–f5. However, in case of the test function f3, the optimization algorithm only found sub-optimaloptimizers for some α-cuts in case of the test function f3, and therefore, could not exploit thelow error from the approximation.

Influence of the fuzziness magnitude on the performance In the numerical examples con-sidered so far, the supports of the fuzzy numbers have been rather large considering the factthat the fuzzy numbers usually represent uncertainties. If we look at the supports of the inputparameters taken for the function f4, for example, the width of the support corresponds to anuncertainty range of ±100% of the peak value 0.5. The input parameters taken for the other testfunctions exhibit similar ranges of uncertainty. Uncertainties of this magnitude are rather un-common in engineering applications. Instead, much smaller uncertainty ranges are of practicalinterest, say 5–20% or less. Clearly, with decreasing range of uncertainty, a smaller part of thefunction needs to be approximated by the sparse grid interpolant, and thus, less sparse grid sup-port nodes are required to accurately approximate the objective function. In other words, thecomplexity of the proposed method will automatically adjust if the problem at hand becomeseasier. To illustrate this fact, we have again used the test functions f1 to f5 from Table 4.1, butthis time, we have varied the fuzzy input parameters regarding the degree of uncertainty andthe membership function shape. In addition to symmetric triangular membership functions, wehave used quasi-Gaussian fuzzy numbers 〈m,σ ,3〉QGFN (see Section 2.1.5), where we chosethe standard deviation σ , and the mean value m such that the support and the peak value of

87

4 Fuzzy Calculus using Sparse Grids

−5 0 50

0.2

0.4

0.6

0.8

1

0 2 40

0.2

0.4

0.6

0.8

1

−5 0 50

0.2

0.4

0.6

0.8

1

0.1 0.2 0.3 0.4 0.50

0.2

0.4

0.6

0.8

1PSfrag replacements

(a) (b) (c) (d)

(e)(f)(g)(h)

−1 −0.5 00

0.2

0.4

0.6

0.8

1

−20 −15 −100

0.2

0.4

0.6

0.8

1

0 0.5 10

0.2

0.4

0.6

0.8

1

−10 −5 00

0.2

0.4

0.6

0.8

1PSfrag replacements

(a)(b)(c)(d)

(e) (f) (g) (h)

Figure 4.6: (a)–(h): Fuzzy-valued results of f1– f8 (from left to right, top to bottom) for thegiven fuzzy-valued input parameters of symmetric triangular shape.

(a) (b)

0 1 2 3 4 5−25

−20

−15

−10

−5

0

5

10

15

α = 0α = 0.5α = 1

PSfrag replacements

Q(t

)

t0 1 2 3 4 5

−25

−20

−15

−10

−5

0

5

10

15

α = 0α = 0.5α = 1

PSfrag replacements

Q(t

)

t

Figure 4.7: (a): Contour plot of fuzzy-valued solution Q(t) computed for a sparse grid inter-polant with n = 1 (N = 9 function evaluations); (b): solution for n = 3 (N = 137);the bold dashed line indicates the result Q(4) shown in Fig. 4.6(f).

88

4.7 Limitations

the resulting fuzzy number remained the same as for the according symmetric triangular fuzzynumber. For both membership function types, we left the peak value of the fuzzy numbersunchanged while setting the width of the supports to 100%, 20%, and 5%, respectively, of itsoriginal size according to Table 4.1.

Table 4.2 summarizes the results (using the piecewise multilinear approach, HCC grid). Wegive the number of function evaluations required for the fuzzy-valued result to reach a relativeerror below etol = 10−2. With decreasing uncertainty, much fewer function evaluations areneeded to attain the desired accuracy, regardless of the shape of the membership function.

4.7 Limitations

There are some cases when the proposed sparse grid approach cannot be applied successfully.These cases can be categorized as follows.

(a) Non-smooth objective functions f ( f does not satisfy Eq. (3.45)). For the continuousfunction f6, the method only converges slowly (Fig. 4.9 (a)).

(b) Smooth objective functions f : Ω → R ( f satisfies Eq. (3.45)) with strong local featureswithin the considered box Ω, e.g. a function with sharp peaks. In this case, many supportnodes are required until the local features are sufficiently approximated and the high or-der asymptotic convergence rate of sparse grid interpolation arises. An example of sucha function is the function f8 as shown in Fig. 4.9 (b). The transformation method per-forms quite satisfactory in this particular case, since the locations of the internal extremamatch the sampled full grid points of the transformation method.

(c) Smooth objective functions f with strong oscillatory behavior within the objective boxΩ. Again, a high number of support nodes is required until the oscillation is sufficientlyresolved.

The uncertainty ranges considered with fuzzy arithmetic are usually rather small, thus, theabove cases will not occur often. In the unlikely event, however, the sparse grid interpolantwill not converge within a reasonable refinement depth, which can be easily detected by acareful implementation.

Table 4.2: Number of function evaluations N required to reach a relative error etol < 10−2.e ·10−3 is the actually achieved relative error.

symmetric triangular100% 20% 5%N e N e N e

f1 321 4.9 65 4.0 13 3.4f2 705 7.3 65 5.4 13 8.8f3 1537 4.2 65 6.8 13 7.2f4 1105 4.6 41 8.3 41 1.8f5 849 4.4 145 1.8 17 8.7

symmetric quasi-Gaussian100% 20% 5%N e N e N e

f1 321 5.3 65 3.9 13 3.6f2 1537 4.1 65 6.5 13 1.3f3 1537 5.8 65 8.4 13 7.2f4 1105 6.7 137 4.8 41 4.7f5 849 5.0 145 4.0 17 7.9

89

4 Fuzzy Calculus using Sparse Grids

100

102

104

106

10−8

10−6

10−4

10−2

100

100

102

104

106

10−8

10−6

10−4

10−2

100

100

102

104

106

10−5

10−4

10−3

10−2

10−1

100

gtrmgtrmrecurspfuzzy−CCspfuzzy−CGL[spc]

PSfrag replacements

(a) (b) (c)

(d)(e)(f)

100

102

104

106

108

10−6

10−4

10−2

100

100

102

104

106

108

10−4

10−2

100

PSfrag replacements

(a)(b)(c)

(d) (e)

(f) 100

102

104

106

10−4

10−3

10−2

10−1

100

PSfrag replacements

(a)(b)(c)(d)(e)

(f)

Figure 4.8: (a)–(f): Relative error of the fuzzy-valued results of f1– f6 w.r.t. the number ofreal-valued function evaluations (Q(4) for the ODE model f6). [spc] indicatesthe expected convergence rate according to Eq. (3.46); the position of the curve ischosen for reasons of clarity. spfuzzy: proposed procedure, gtrm: general trans-formation method, gtrmrecur: general transformation method without recurringpermutations.

100

102

104

106

10−1

100

100

102

104

106

10−2

10−1

100

gtrmgtrmrecurspfuzzy−CC

PSfrag replacements

(a) (b)

Figure 4.9: (a)–(b): Relative error of the fuzzy-valued results of f7– f8 w.r.t. the number of real-valued function evaluations. spfuzzy depicts the curve obtained for the proposedalgorithm, gtrm represents the general transformation method, and gtrmrecur is thegeneral transformation method without recurring permutations.

90

5 Applications

The following applications show several examples where the sparse grid approach to fuzzycalculus can be successfully applied. The main focus is placed on systems with many outputparameters, since in this case, the benefits of the method are most significant compared toa direct optimization of the objective function, which could be done in case of just a singleor very few fuzzy output variables. The examples in Section 5.1 are computed using regularsparse grids, while we employ both dimension-adaptive and regular sparse grids in Section 5.2.For the applications, we only use the piecewise linear approach; from the numerical examplesconsidered in Chapter 4, it is evident that the higher-order approach can only offer significantadvantages if very high accuracies are desired. Moreover, the higher-order approach requires avery smooth output of the objective function, which is usually quite expensive to obtain if thenumerical solution of ODEs, PDEs, etc., is involved. In practical applications, a relative errorof around 1% is usually more than enough – thus, using the piecewise linear approach seemsto be a much more appropriate choice, not only from a computational point of view (it requiresmuch less computing time).

5.1 Dynamic systems

5.1.1 Infectious disease modeling under uncertainty

The periodic outbreak of a disease can be modeled with delay differential equations [32]. Delaydifferential equations are equations with so-called time-lags τ of the form

y′(t) = f (t,y(t),y(t− τ)), (5.1)

i.e. the derivative of the solution depends also on the solution at a previous time t − τ . Weconsider an enhanced Kermack-McKendrick model for epidemic modeling, as given in [32],where y1(t) is the susceptible, y2(t) is the infected, and y3(t) is the immunized portion of thepopulation at a time t:

y′1(t) = −y1(t)y2(t), y′2(t) = y1(t)y2(t)− y2(t), y′3(t) = y2(t). (5.2)

By introducing two time lags τ1 and τ2, the classical model becomes capable of modeling theperiodic outbreak of a disease. The enhanced model is given by

y′1(t) = −y1(t)y2(t − τ2)+ y2(t − τ1)

y′2(t) = y1(t)y2(t − τ2)− y2(t) (5.3)

y′3(t) = y2(t)− y2(t − τ1),

91

5 Applications

with τ2 denoting the incubation period, and τ1 denoting the time after which the immunizedones of the population become susceptible again. In this simple model, all rate constants areequal to one. The solution is given in [32, Figure 17.6] for the following time-lags and initialconditions: τ1 = 10, τ2 = 1, y1(t0) = 5, y2(t0) = 0.1, and y3(t0) = 1 for t0 ≤ 0. The consideredtime span is t ∈ [0,40]. Since y1 and y2 do not depend on y3, we will neglect y3 in the following.Alternatively to integrating the differential equation given in Eq. (5.3), y3 can be computed by

y3(t) = ytotal − (y2(t)+ y1(t)), (5.4)

where ytotal is the total population (ytotal = y1(t0)+ y2(t0)+ y3(t0)), which remains constant.We can interpret the above model (5.3) as a nonlinear function with five input parameters

and two output parameters (omitting y3), i.e.

(y1(t),y2(t)) = fdde(t,τ1,τ2,y1(t0),y2(t0)), (5.5)

t ∈ [0, t1], since its behavior is uniquely determined for a given set of time-lags and initialconditions. To compute this function, a numerical algorithm is applied that discretizes andintegrates the model equations with respect to the time t. Using a predefined number s ofequally-spaced discretization steps h = t1/s, a start time t0 = 0, and an end time t1, we arriveat the time-discrete function

(y1,1, . . . , y1,s, y2,1, . . . , y2,s) = f hdde(τ1,τ2, y1,0, y2,0, t1,s), (5.6)

where yi,k = yi(hk), k ∈ 0, . . . ,s, i ∈ 1,2.We now introduce uncertainty to the model. We assume the time-lags in Eq. (5.6) to be

uncertain, i.e. we replace τ1 and τ2 by the fuzzy-valued parameters τ1 and τ2, respectively.Furthermore, we replace the initial conditions in Eq. (5.6) by uncertain parameters, i.e. theinitial susceptible portion of the population y1,0 by the fuzzy-valued parameter y1,0 and theinitial infected portion of the population y2,0 by y2,0. Consequently, the output parametersbecome fuzzy as well. The resulting fuzzy-parameterized model function is given by

(y1,1, . . . , y1,s, y2,1, . . . , y2,s) = f hdde(τ1, τ2, y1,0, y2,0, t1,s). (5.7)

In our numerical example, we use fuzzy numbers with membership functions of quasi-Gaussianshape (see Section 2.1.5). The fuzzy input parameters are defined as

p1 = 〈10,3−1,3〉QGFN, p2 = 〈1,30−1,3〉QGFN,

p3 = 〈5,12−1,3〉QGFN, p4 = 〈0.1,600−1,3〉QGFN.

Thus, the base variations are ±10% for the time-lags, and ±5% for the initial conditions. Thepeak values of the fuzzy numbers correspond to the values from [32].

Since the objective function has multiple output arguments, the sparse grid surrogate func-tion Aq,d( f h

dde) must have an according number of outputs as well (indicated by the bold-facedcapital A). Formally, the sparse grid interpolation algorithm is applied separately with respectto each output parameter, but since the same sparse grid points are used, the number of func-tion evaluations remains constant (it is not affected). The memory and time complexity to

92

5.1 Dynamic systems

compute the interpolant grows linearly with each additional output parameter. Our MATLAB

implementation of piecewise multilinear sparse grid interpolation [55] is capable of handlingmultiple function output arguments. With the given base variations, the objective function f h

ddeis evaluated at the sparse grid points for the base box Ω = [9,11]× [0.9,1.1]× [4.75,5.25]×[0.095,0.105]. We have used the standard solver by Shampine and Thompson [77] to dothis, with the solver error tolerances εrel = 10−5 and εabs = 10−9. With , the discretiza-tion of the time is not equally-spaced by default, however, with the function providedwith , the solution vectors can be made equidistant. This is necessary, since we requirethe different function evaluations to produce solution vectors of equal length and time step-size,such that we can apply the sparse grid algorithm for each component of the solution vectors.

We have used s = 80 discretization steps, and the sparse grid interpolation depths n = 1,3,5(recalling n = q−d) to compute three sparse grid interpolants Aq,d( f h

dde) of increasing accuracyin Part 1 of the algorithm for fuzzy arithmetic on sparse grids, and (m + 1) = 51 α-cuts togenerate the plots. The results of the simulation are summarized in Figure 5.2. A maximumrelative error of the fuzzy results of less than 2% is achieved for the interpolation depth n = 5(1105 function evaluations), but even for n = 3 (137 evaluations), an average error of less than3% already provides a very good approximation of the solution.

To assess the accuracy of the results in greater detail, we present convergence histories for themaximum relative error εmax and the average relative error εavg of the fuzzy-valued results y1

and y2 over all time steps 0, . . . ,s in Figure 5.1. Since the exact results are not known, we haveused the solutions obtained for n = 8 as references to compute the relative errors. In the plots,wn

max,rel represents the maximum over the estimated relative errors of the interpolant Aq,d( f hdde)

according to Eq. (3.54) with respect to the outputs y1 and y2, again over all time steps. Onecan observe that the estimated interpolation error gives a good indication of the accuracy of thefuzzy-valued results, provided that in Part 2 of the algorithm, the global optimization problemsEq. (4.3) are solved accurately.

(a) (b)

101

102

103

104

10−3

10−2

10−1

100

number of points N

wmax,reln

εmax

εavg

1 2 3 4 5 6 7 8

level n

101

102

103

104

10−3

10−2

10−1

number of points N

wmax,reln

εmax

εavg

1 2 3 4 5 6 7 8

level n

Figure 5.1: Relative error plots, (a): y1 (susceptible), (b): y2 (infected).

93

5 Applications

0 10 20 30 40

0

2

4

6

susceptible

leve

l n =

1;

N =

9

0 10 20 30 40

0

2

4

6

infected

0 10 20 30 40

0

2

4

6

leve

l n =

3;

N =

137

0 10 20 30 40

0

2

4

6

0 10 20 30 40

0

2

4

6

leve

l n =

5;

N =

110

5

0 10 20 30 40

0

2

4

6α = 0α = 0.5α = 1

α = 0α = 0.5α = 1

0.0602 1.720

0.5

1susceptible, t = 20

← 0.1711.38 5.51

0

0.5

1susceptible, t = 30

4.87 →0.207 0.864 1.69

0

0.5

1infected, t = 20

0.004 1.590

0.5

1infected, t = 30

← 0.073

n = 1n = 3n = 5

n = 1n = 3n = 5

Figure 5.2: Fuzzy-valued results y1 (susceptible) and y2 (infected).

94

5.1 Dynamic systems

5.1.2 Computation of a multibody mechanism under uncertainty

Andrews’ squeezer mechanism, which is shown in Fig. 5.3, is a popular test example for multi-body dynamics. The plane mechanism consists of seven rigid bodies B1, . . . ,B7 connected byfrictionless joints and a spring c. The mechanism is fixed at the origin of the coordinate systemO and at the points A, B, and C. The positions of the bodies are described by the seven anglesβ , Θ, γ , Φ, δ , Ω, and ε as shown in the figure. Since there are three kinematic loops andcorrespondingly six algebraic constraints, the problem is actually a single degree of freedommechanism. However, for the numerical solution it is more convenient to keep the equationsof motion for the seven angles and the six algebraic constraints, and to treat the problem as asystem of differential algebraic equations. A complete description including geometric, inertiaand stiffness properties can be found in [33].

(a) (b)

PSfrag replacements

A

B

C

O

c

x

y

B1B2

B3

B4

B5

B6

B7

βδ

ε

γ

ΦΘ

ΩM

0 0.005 0.01 0.015 0.02 0.025 0.03−3

−2

−1

0

1

2

3an

gle

[rad

]

time t

βΦ

Figure 5.3: Andrews’ squeezer mechanism; (a): system, (b): crisp solution.

The mechanism is driven by a constant torque M at point O starting the system from restat Θ = 0, from which condition the complete initial state of the system can be calculated bya Newton iteration using just the geometric data. Time integration of the DAE system in theinterval t ∈ [0,0.03] is then performed using the standard MATLAB solver

, where arelative error tolerance of εrel = 10−6 has been enforced. Output has been requested at s = 60equal time steps with h = 5 · 10−4. The solution for the data given in [33] is shown (mod 2π)in Fig. 5.3, where the solutions for β and Φ have been highlighted for later reference.

We now consider uncertain values for the positions of the three fixed points A at (xA,yA),B at (xB,yB) and O at (xO,yO), while keeping the other data crisp. This assumption rendersthe initial state as well as the right hand side of the DAE system uncertain. The six coordinatevalues are assumed to be symmetric fuzzy numbers with triangular membership functions withpeak values taken from [33] and absolute base variations of ±0.001.

If the general transformation method (see Section 2.3.3.1) is used to evaluate the fuzzyproblem, a direct fuzzy simulation with d = 6 fuzzy parameters and 11 α-cuts requires N =3749966 evaluations of the system according to Eq. (2.40), which is a prohibitively high num-ber. However, the same problem can be easily solved using sparse grid interpolation, where an

95

5 Applications

estimated maximum relative interpolation error (over both fuzzy results for β and Φ at all timesteps) of εest < 0.01 is reached at an interpolation depth of n = 5 at a cost of only N = 4865evaluations. Figure 5.5 shows the fuzzy result for the angles β and Φ and interpolation depthsn = 1,3,5. The results are shown as contour plots over the time history and as membershipfunction plots for t = 0.02 and t = 0.03, respectively. The fuzzy results were obtained using11 α-cuts and the coordinate search algorithm described in Section 4.4, although in very fewcases, we had to manually adjust the optimization part to correctly compute the ranges of theinterpolant (by using the more expensive interval-based complete search). Nevertheless, thisdid not affect the number of required function evaluations.

As expected, the peak values of the fuzzy results are equal to the corresponding results ofthe crisp solution shown in Fig. 5.3. The non-linear input-output relationship of the modelbecomes manifest in the non-symmetric membership functions of the outputs for symmetricinputs. Analogously to the previously discussed model, we show the convergence histories ofthe interpolation error and the maximum and average error of the fuzzy-valued results over alltime steps in Fig. 5.4.

(a) (b)

102

103

104

10−4

10−3

10−2

10−1

number of points N

wmax,reln

εmax

εavg

1 2 3 4 5 6 7

level n

102

103

104

10−3

10−2

10−1

number of points N

wmax,reln

εmax

εavg

1 2 3 4 5 6 7

level n

Figure 5.4: Relative error plots, (a): β , (b): Φ.

5.2 Vibration engineering: Frequency response functionenvelopes

The influence of uncertain input data on response spectra of dynamic structures is consideredin this section. To assess the performance of the sparse grid approach, we have also usedtwo alternative implementations of the extension principle, namely the reduced transformationmethod (see Section 2.3.3.2) and the general transformation method (see Section 2.3.3.1). Acommon feature of both methods is the fact that they require real-valued function evaluationsonly, and are thus applicable in the same way as fuzzy arithmetic based on sparse grids.

96

5.2 Vibration engineering: Frequency response function envelopes

0 0.01 0.02 0.03

0

5

10

15

angle β

leve

l n =

1;

N =

13

0 0.01 0.02 0.03−0.8

−0.2

0.4angle Φ

0 0.01 0.02 0.03

0

5

10

15

leve

l n =

3;

N =

389

0 0.01 0.02 0.03−0.8

−0.2

0.4

0 0.01 0.02 0.03

0

5

10

15

leve

l n =

5;

N =

486

5

0 0.01 0.02 0.03−0.8

−0.2

0.4α = 0α = 0.5α = 1

α = 0α = 0.5α = 1

7.72 8.18 8.780

0.5

1angle β, t = 0.02

14.7 15.8 16.90

0.5

1angle β, t = 0.03

−0.49 −0.24 −0.0020

0.5

1angle Φ, t = 0.02

−0.59 −0.250

0.5

1angle Φ, t = 0.03

← −0.53

n = 1n = 3n = 5

n = 1n = 3n = 5

Figure 5.5: Fuzzy-valued results β and Φ.

97

5 Applications

5.2.1 Numerical realization

We propose the following procedure in [66].Step 1: Discretization. First, the objective frequency range [F0,F1] is divided into s− 1

equidistant or logarithmically spaced steps, giving s discrete frequencies fi, i = 1, . . . ,s. Wesuggest to use a logarithmic distribution when analyzing the dynamic response especially invibro-acoustic applications, since in this case, the resonance frequencies usually lie closertogether with increasing frequency. It is advisable to first compute the frequency responsefunction for a crisp set of input parameters to select an adequate resolution, i.e., capable ofclearly resolving the resonance frequencies. The d uncertain input parameters p1, . . . pd arediscretized into N discrete parameter vectors p j, j = 1, . . . ,N, p j ∈ Ω0 according to the chosenimplementation of the the extension principle of Section 4.3, and Ω0 as in Eq. (2.25). Note thatin case of the reduced and the general transformation method, N is determined by the numberof α-cuts (m+1) chosen for the fuzzy number discretization.

Step 2: Model evaluation. Then, the magnitude of the frequency response FRF( fi,p j)is computed for all s ·N permutations. An efficient implementation may vectorize the callsto the model to treat multiple discrete frequencies, or alternatively, several sets of parameterpermutations at once.

Step 3: FRF envelope construction. In case of the reduced and the general transformationmethod, the resulting discrete response magnitudes FRF( fi,p j) can be used directly to computean approximate envelope. For each α-cut ∈ [0,1] (where α must match the cuts selected forthe discretization), we compute FRFα( fi) =

[FRFα ,min( fi),FRFα ,max( fi)

], with

FRFα ,min( fi) = minp j∈Ωα

FRF( fi,p j) and (5.8)

FRFα ,max( fi) = maxp j∈Ωα

FRF( fi,p j). (5.9)

In case of sparse grid-based fuzzy arithmetic, the discrete response magnitudes FRF( fi,p j),i = 1, . . . ,s, j = 1, . . . ,N, are used to construct s sparse grid interpolants An+d,d(FRF( fi)) thatapproximate the frequency response function at each discrete frequency fi in the parameterdomain Ω0. To obtain the frequency response we compute

FRFα ,min( fi) = minp∈Ωα

An+d,d(FRF( fi))(p) and (5.10)

FRFα ,max( fi) = maxp∈Ωα

An+d,d(FRF( fi))(p). (5.11)

Here, any set of α levels can be chosen for the optimization part. Obviously, the sparse grid-based approach requires more computational effort to compute the envelope. However, oftenmuch fewer evaluations of the objective model are required to compute an accurate approxi-mation of the response envelope. In case of complex, expensive to evaluate models, this canresult in enormous time savings.

Remark. To obtain good results with the sparse grid-based approach, we compute the FRFfunction values in logarithmic scale, i.e. use log(FRF( fi,p j)) to construct the interpolant, sincethe underlying interpolation scheme will produce more appropriate interpolated values.

98

5.2 Vibration engineering: Frequency response function envelopes

Finally, the fuzzy-valued frequency response at any given frequency fi can be composedfrom the α-level sets FRF( fi)α . Furthermore, the response function envelopes for a giveninterval of confidence α are easily obtained by plotting the two curves of the minimum and themaximum FRF magnitudes FRFα,min( fi) and FRFα,max( fi), respectively, over the frequenciesfi, i ∈ [F0,F1].

5.2.2 Estimating frequency response function envelopes using thespectral element method

Traditionally, frequency response analyses are based on finite or boundary element models ofthe objective structure. In the case of the mid-frequency range problem, however, a very finemesh is required to correctly approximate the frequency response. This is particularly problem-atic in uncertainty modeling where the computational effort is usually increased significantlyby the need for multiple runs (e.g. when conducting a Monte Carlo analysis) to achieve reliableresults. The spectral element method combined with a fuzzy set-based uncertainty modelingapproach is presented in [66] as an appealing alternative.

We provide numerical results for two test problems. Please refer to [66] for a more detaileddiscussion of these models.

To get a detailed insight into the performance of the methods, we have performed severalruns on the models with different discretization parameters. In all simulation runs, the fre-quency domain was decomposed into s = 1000 frequencies at logarithmically spaced steps.This resolution is much higher than it would have been necessary from a practical point ofview to achieve good results. However, it permitted us to visualize the subtle differences in theconvergence behavior of the applied methods by zooming into the regions of interest.

We have also conducted an error analysis to assess the quality of the computed results. Thereference solutions Rmin and Rmax at α = 0 were obtained numerically with a highly accuratesparse grid interpolant using an interpolation depth of n = 9, which resulted in N = 3329 sup-port nodes per frequency. The maximum error emax and the average error emin of the frequencyresponse function envelopes were computed according to the following formulae:

emax = maxi=1,...,s

[|FRF0,min( fi)−Rmin( fi)|+ |FRF0,max( fi)−Rmax( fi)|

](5.12)

eavg =[ s

∑i=1

[|FRF0,min( fi)−Rmin( fi)|+ |FRF0,max( fi)−Rmax( fi)|

]]· s−1 (5.13)

For comparison, we have also included a Monte Carlo simulation with N = 10, 100, and 1000samples. The samples were uniformly distributed in Ω0, generated by the pseudo-randomnumber generator of MATLAB.

5.2.2.1 Coupled rod system

In the first example, we consider a system of two coupled rods. An axial force P is applied tothe free end of rod 1, as shown in Fig. 5.6. Table 5.1 summarizes the properties of rod 1 and rod2 adopted for the numerical model. The free-free boundary condition was used. The modulus

99

5 Applications

of elasticity E and the damping loss factor η are treated as uncertain parameters. Note that inthis simulation, E1/2 and η1/2 are not independent, i.e. E1 = E2 = E and η1 = η2 = η , whereE and η are the uncertain parameters. The uncertain parameters p are modeled as triangularfuzzy numbers with spread a, i.e. p = 〈m,a,a〉TFN. We have studied the frequency response forthe uncoupled case as well as the coupled case. For the coupled-rod case, the point receptanceat the connection of the rods is considered (see Fig. 5.6).

Table 5.1: Physical and geometric properties of the coupled rod system.parameter mean value m spread a unit

E1/2 2.71×109 10 % m N/m2

η1/2 1.0×10−2 10 % m –ρ1/2 1140 – kg/m3

A1 1.735×10−3 – m2

A2 1.862×10−4 – m2

L1 0.20 – mL2 2.46 – m

rod 1-

-

P

L1

rod 2

-L2

Figure 5.6: Model of the coupled rod system [66].

5.2.2.2 Plate with reinforcements

In the second example, a plate with simple support in the yz-plane and free-free support in thexz-plane is studied, see Fig. 5.7. The assumed properties are summarized in Table 5.2. TheFRF is computed at the drive point located at position (x,y) = (333.4, 160.0) mm.

Table 5.2: Physical and geometric properties of the plate.

parameter mean value m spread a unitE 69×109 5 % m N/m2

h 4 10 % m mmρ 2700 – kg/m3

ν 0.3 – –Lx 0.400 – mLy 0.704 – m

100

5.2 Vibration engineering: Frequency response function envelopes

0.07 0.18 0.18 0.18 0.07

0.4

0.006

0.004 0.015

x

y

z

Figure 5.7: Schematic diagram of the stiffened plate (units in meters) [66].

5.2.2.3 Uncertainty analysis results

For the discretization parameters and the achieved accuracy of the runs, please refer to Ta-ble 5.3. The computed frequency response function envelopes including zooms for differentdiscretization refinements are shown in Fig. 5.8, Fig. 5.9, and Fig. 5.10, for the uncoupledrod, the coupled rod, and the plate system, respectively. Only the envelopes for the 0-cut areshown, which reflect the maximum variation for the considered uncertainty range. An exem-plary fuzzy-valued result at a specific frequency fk is shown in the right-most column in caseof the fuzzy-arithmetical methods (rtrm: reduced transformation method, gtrmrecur: generaltransformation method considering recurring permutations, sparse: sparse grid-based). For theMonte Carlo (MC) analysis, the distribution of the sampled results at fk is shown in the right-most column. The location of fk in the frequency domain is indicated by the bold dashed linein the zoom plots.

Table 5.3: Discretization parameters and approximation error for the simulation runs.

uncoupled rod coupled rod platemethod (m+1) n N emax eavg emax eavg emax eavg

MC – – 10 4.6 1.3 7.4 0.57 14 3.3– – 100 0.73 0.15 0.85 0.083 6.5 0.86– – 1000 0.30 0.037 0.38 0.024 2.3 0.22

rtrm 2 – 5 5.0 0.52 7.0 0.37 14 3.05 – 17 1.1 0.11 1.8 0.092 8.6 1.2

17 – 65 0.49 0.054 0.58 0.042 3.9 0.3333 – 129 0.46 0.051 0.54 0.039 3.8 0.23

gtrmrecur 5 – 41 1.0 0.078 1.6 0.069 5.2 0.5617 – 545 0.085 0.0076 0.14 0.0068 0.55 0.05933 – 2113 0.028 0.0026 0.042 0.0023 − −

sparse 21 1 5 5.0 0.56 7.2 0.39 15 3.021 3 29 1.0 0.090 1.6 0.082 11 1.021 5 145 0.096 0.0089 0.15 0.0080 5.2 0.2721 6 321 0.027 0.0023 0.036 0.0020 2.1 0.13

101

5 Applications

(a)

−47.9937 −39.3936

N=10

N=100

N=1000

7000 8500−54

−52

−50

−48

−46

−44

−42

−40

7000 8500103

104

−65

−60

−55

−50

−45

−40

−35

−30

7000 8500

PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(b)

−47.9969 −39.69210

0.5

1

µ(F

RF

)

7000 8500−54

−52

−50

−48

−46

−44

−42

−40

7000 8500

m=2m=5m=17

103

104

−60

−55

−50

−45

−40

−35 α = 0α = 1

7000 8500

PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(c)

−47.9969 −39.34990

0.5

1

µ(F

RF

)

7000 8500−54

−52

−50

−48

−46

−44

−42

−40

7000 8500103

104

−60

−55

−50

−45

−40

−35

7000 8500

m=2m=5m=17

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(d)

−47.9969 −39.34990

0.5

1

µ(F

RF

)

7000 8500−54

−52

−50

−48

−46

−44

−42

−40

7000 8500103

104

−60

−55

−50

−45

−40

−35

7000 8500

n=1n=3n=5

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

Figure 5.8: Envelope FRFs for the uncoupled rod system. (a) MC, (b) rtrm, (c) gtrmrecur,(d) sparse grid; (i) full spectrum, (a,ii–iv) zoom for N = 10,100,1000, (b–c,ii–iv)zoom for (m+1) = 2,5,17 α-cuts, (d,ii–iv) zoom for level n = 1,3,5; (a,v) rangeof MC results depending on N at f892 = 7796.4 Hz, (b–d,v) fuzzy-valued result atf892 depending on m,n.

102

5.2 Vibration engineering: Frequency response function envelopes

(a)

−45.0722 −37.6265

N=10

N=100

N=1000

3000 5000

−48

−46

−44

−42

−40

−38

3000 5000101

102

103

104

−60

−50

−40

−30

−20

−10

0

3000 5000

PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(b)

−45.1877 −37.42750

0.5

1

µ(F

RF

)

3000 5000

−48

−46

−44

−42

−40

−38

3000 5000101

102

103

104

−50

−45

−40

−35

−30

−25

−20

−15

−10

3000 5000

m=2m=5m=17

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(c)

−45.1877 −37.42750

0.5

1

µ(F

RF

)

3000 5000

−48

−46

−44

−42

−40

−38

3000 5000101

102

103

104

−50

−45

−40

−35

−30

−25

−20

−15

−10

3000 5000

m=2m=5m=17

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(d)

−45.1877 −37.42750

0.5

1

µ(F

RF

)

3000 5000

−48

−46

−44

−42

−40

−38

3000 5000101

102

103

104

−50

−45

−40

−35

−30

−25

−20

−15

−10

3000 5000

n=1n=3n=5

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

Figure 5.9: Envelope FRFs for the coupled rod system. (a) MC, (b) rtrm, (c) gtrmrecur, (d)sparse grid; (i) full spectrum, (a,ii–iv) zoom for N = 10,100,1000, (b–c,ii–iv)zoom for (m+1) = 2,5,17 α-cuts, (d,ii–iv) zoom for level n = 1,3,5; (a,v) rangeof MC results depending on N at f867 = 3986.6 Hz, (b–d,v) fuzzy-valued result atf867 depending on m,n.

103

5 Applications

(a)

−74.6877 −56.7172

N=10

N=100

N=1000

800 1000−80

−75

−70

−65

−60

−55

−50

800 1000101

102

103

−75

−70

−65

−60

−55

−50

−45

−40

800 1000

PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(b)

−74.2888 −56.76370

0.5

1

µ(F

RF

)

800 1000−80

−75

−70

−65

−60

−55

−50

800 1000101

102

103

−75

−70

−65

−60

−55

−50

−45

−40

800 1000

m=2m=5m=17

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(c)

−74.8405 −56.71930

0.5

1

µ(F

RF

)

800 1000−80

−75

−70

−65

−60

−55

−50

800 1000101

102

103

−75

−70

−65

−60

−55

−50

−45

−40

800 1000

m=2m=5m=17

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

(d)

−75.006 −56.0960

0.5

1

µ(F

RF

)

800 1000−80

−75

−70

−65

−60

−55

−50

800 1000101

102

103

−75

−70

−65

−60

−55

−50

−45

−40

800 1000

n=1n=3n=5

α = 0α = 1PSfrag replacements

(i) (ii) (iii) (iv) (v)

f [Hz]f [Hz]f [Hz]Frequency [Hz]

FR

F[d

B,r

ef.m

/N]

FRF [dB, ref. m/N]

Figure 5.10: Envelope FRFs for the plate system. (a) MC, (b) rtrm, (c) gtrmrecur, (d) sparsegrid; (i) full spectrum, (a,ii–iv) zoom for N = 10,100,1000, (b–c,ii–iv) zoom for(m + 1) = 2,5,17 α-cuts, (d,ii–iv) zoom for level n = 1,3,5; (a,v) range of MCresults depending on N at f849 = 897.90 Hz, (b–d,v) fuzzy-valued result at f849

depending on m,n.

104

5.2 Vibration engineering: Frequency response function envelopes

101

102

103

10−2

10−1

100

101

101

102

103

10−3

10−2

10−1

100

MCrtrmgtrmrecursparse

MCrtrmgtrmrecursparse

PSfrag replacements

(a)

(b)

(c)(d)(e)(f)

N

N

e max

[dB

,ref

.m

/N]

e avg

[dB

,ref

.m

/N]

101

102

103

10−2

10−1

100

101

101

102

103

10−3

10−2

10−1

100

MCrtrmgtrmrecursparse

MCrtrmgtrmrecursparse

PSfrag replacements

(a)(b)

(c)

(d)

(e)(f)

N

N

e max

[dB

,ref

.m

/N]

e avg

[dB

,ref

.m

/N]

101

102

103

10−1

100

101

102

MCrtrmgtrmrecursparse

101

102

103

10−2

10−1

100

101

MCrtrmgtrmrecursparse

PSfrag replacements

(a)(b)(c)(d)

(e)

(f)

N

N

e max

[dB

,ref

.m

/N]

e avg

[dB

,ref

.m

/N]

Figure 5.11: Error plots. (a,b) uncoupled rod, (c,d) coupled rods, (e,f) plate.

5.2.2.4 Interpretation of the results

All of the fuzzy set-based methods significantly outperformed the Monte Carlo analysis interms of achieved accuracy vs. the number of required function evaluations. This is no surprise,since unlike in problems such as integration, where pure Monte Carlo methods provide theattractive convergence order of 1/

√N due to the central limit theorem independently of the

problem dimension, the convergence order decreases exponentially with the dimension. Weemphasize that the MC method was only used here to verify the correctness of the fuzzy-setbased results.

Both transformation method variants sample the corner points of the domain of the uncertainparameters, which are the relevant points when monotonicity is present. In proximity of theresonance frequencies, the response function is non-monotonic, and the sampled inner pointsbecome relevant. The reduced transformation method only samples the diagonals of the pa-rameter domain hypercube, and is thus not guaranteed to converge to the correct result. Thiscan be observed in the sub-plots (b,ii-iv) of the Figs. 5.8 and 5.9, where the envelope curveshows a kink near to the peak, which is not present in case of the other methods (a,c,d,ii-iv).

In these examples, the sparse grid-based approach showed mixed results. In the rod case, theperformance was very good. Compared to the general transformation method, a significantly

105

5 Applications

better asymptotic convergence rate was achieved (see Fig. 5.11), as was shown in Chapter 4for smooth functions. However, for the plate example, the encountered oscillations were toostrong to be correctly resolved by an interpolant with a small number of nodes.

5.2.3 Response curve envelopes of large-scale finite element models

The final two examples deal with the vibration analysis of a truck cabin model. We have firstexamined the dynamic response of the cabin floor with nine uncertain parameters to get aninitial idea of the model behavior. Then, the entire truck cabin was analyzed using 27 uncertainparameters, rendering both geometric and material properties uncertain.

5.2.3.1 Description of the models

Cabin floor model The cabin floor model already represents a realistic application example(see Fig. 5.13); however, the required computing time per model run is still relatively smallwith about 15 minutes on a Intel Pentium 3 GHz machine. The most important model char-acteristics are summarized in Table 5.4. The maximum displacement at the drive point in thedirection of the applied force is shown in Fig. 5.12, (a).

Entire truck cabin This model served as an example to test the applicability of the sparsegrid-based uncertainty modeling approach to a real world, large-scale finite element model.Here, the computing time was about two hours on a 3 GHz PC for a single evaluation of themodel. The most important characteristics of the model are summarized in Table 5.5. Themaximum displacement at the drive point in the direction of the applied force is shown inFig. 5.12, (b).

50 100 150 200 250 300 350 400 450 500

10−4

10−3

10−2

10−1

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)50 100 150 200 250

10−5

10−4

10−3

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)

Figure 5.12: Crisp displacement response spectrum; (a): floor, (b): cabin model

106

5.2 Vibration engineering: Frequency response function envelopes

Table 5.4: Floor model characteristics

Number of nodes 22395Number of elements 21254Type of elements QUAD4, TRI3, BAR, SPRING, RBE, MASSSupport conditions free–freeFrequency domain 1 – 500 Hz (modal basis up to 1kHz)

PSfrag replacements

P

PSfrag replacements P

Figure 5.13: Floor model

Table 5.5: Truck cabin model characteristics

Number of nodes 91702Number of elements 90553Type of elements QUAD4, TRI3, BAR, SPRING, RBE, MASS, PENTA, HEXASupport conditions free–freeFrequency domain 1 – 250 Hz (modal basis up to 500 Hz)

Figure 5.14: Truck cabin modelPSfrag replacements P

107

5 Applications

5.2.3.2 Implementational issues

In case of more complex models, external software packages are usually required to carry outthe model evaluations. Here, we have used the finite element software package PERMAS to dothis. PERMAS, developed by INTES GmbH, is a general system for the solution of complexengineering problems using the finite element method.

Interfacing MATLAB and PERMAS The following strategy was used to obtain the modelevaluations that were necessary for the adaptive construction of the sparse grid surrogate func-tion. The data file describing the model was split into two parts. The first part not containingany uncertain parameters was stored as a binary input file ( -file). The second part con-taining the supports of the uncertain parameters was stored as a text file ( -file). In the -File, we marked the uncertain parameters by a simple syntax convention, similar to otherPERMAS commands:

name r1 r2

This sequence was simply inserted instead of the original real-valued input parameter. Theremainder of the simulation could then be carried out automatically by our software. Thisinvolved parsing of the -files, i.e. reading in the uncertain parameters, generation of thepermutations to evaluate by the sparse grid algorithm, generation of regular files withregular real-valued parameters, system calls to PERMAS, and parsing the PERMAS result fileonce the run had completed. The interface concept is summarized in Fig. 5.15.

Figure 5.15: MATLAB – PERMAS interface

Parallelization approach For the truck cabin model, it became necessary to perform functionevaluations in parallel to achieve an acceptable overall computing time. With the dimension-adaptive approach, all function evaluations associated with the grid points belonging to the

108

5.2 Vibration engineering: Frequency response function envelopes

same index set can be performed simultaneously, without modification of the dimension-adaptive algorithm; we have distributed the permutations to the nodes of a high-performancecluster via a self-scheduling algorithm [30]. This worked well in case of sub-grids wherethe number of grid points was larger than the number of cluster nodes; however, in the high-dimensional case, there are many sub-grids with only a low number of grid points, whichleaves, in each step, some nodes of the cluster unused. Further research could be devoted toextending the dimension-adaptive algorithm into a fully parallel algorithm that takes the num-ber of available cluster nodes into account when determining the next sets of multi-indices toadd to the dimension-adaptive interpolant.

5.2.3.3 Uncertain input and output data

Both models were initially subjected to just two uncertain parameters: the applied drive forceP = 〈1,0.1,0.1〉TFN and the modal damping parameter η = 〈0.04,0.01,0.01〉TFN. The spreadscorrespond to an uncertainty range of ±10% and ±25%, respectively, with respect to the peakvalue. The aim of this evaluation was to quantify the influence of the modal damping on themodel behavior, since the damping factor is often assumed by the engineers as an empirically,globally constant value.

In the main simulation, the floor model was then subjected to 9 uncertain input parameters,see Table 5.6, which represented some uncertainty in all relevant parts, both in the geometry(the thickness of the plate) and in the material properties. The cabin model was subjected to 27uncertain input parameters, see Fig. 5.16 and Table 5.7.

Table 5.6: Uncertain input parameters of the floor model

Input parameter Mean value UncertaintyDrive force P [N] 1.0 ±10%Modal damping parameter η [-] 0.04 ±25%Frame: E modulus E1 [N/mm2] 2.1e+5 ±10%

Poisson ratio ν1 [-] 0.28 ±10%Density ρ1 [t/mm3] 8.64e-9 ±10%

Plates: E modulus E2 [N/mm2] 2.1e+5 ±10%Poisson ratio ν2 [-] 0.28 ±10%Density ρ2 [t/mm3] 1.0e-10 ±10%Thickness d [mm] 1.0 ±10%

All input parameters were taken as symmetric triangular fuzzy numbers with the spreadcorresponding to the maximum uncertainty with respect to the mean value.

For both models, the uncertain displacement response spectrum at the drive point in directionof the applied force was taken as the model output. To this end, the frequency domain wasdiscretized in steps of 1 Hz, and sparse grid interpolants were computed simultaneously foreach discrete frequency. Then, the worst-case envelope curve was determined approximatelyfor the considered uncertainty range by computing two curves: a lower curve through thelower bounds of the supports of the fuzzy outputs at each discrete frequency, and an uppercurve through the lower bounds of the supports, using piecewise linear interpolation.

109

5 Applications

PSfrag replacements

6

1

2

3

4

5

PSfrag replacements

612345

7

8

10

9

Figure 5.16: Cabin model, exploded view

Table 5.7: Uncertain input parameters of the cabin model

# Input parameter Mean value UncertaintyDrive force P [N] 1.0 ±10%Modal damping parameter η [-] 0.04 ±25%All plates: E modulus Ep [N/mm2] 2.1e+5 ±5%

Poisson ratio νp [-] 0.28 ±5%Density ρp [t/mm3] 8.64e-9 ±5%

1 Front plate thickness d1 [mm] 1.0 ±10%2 Floor plate thickness d2 [mm] 1.0 ±10%3 Roof bottom plate thickness d3a [mm] 1.0 ±10%

Roof top plate thickness d3b [mm] 0.9 ±10%4 Rear plate thickness d4 [mm] 0.9 ±10%5 Door plate thickness d5 [mm] 0.9 ±10%6 Windshield: Thickness d6 [mm] 6.0 ±10%

E modulus Ew [N/mm2] 7.3e+5 ±5%Poisson ratio νw [-] 0.22 ±5%Density ρw [t/mm3] 2.5e-9 ±5%

7 Connection windshield/roof: E modulus Ecw [N/mm2] 3.5 ±2%Poisson ratio νcw [-] 0.48 ±2%Density ρcw [t/mm3] 1.18e-9 ±2%

8 Connection doors: E modulus Ecd [N/mm2] 0.35 ±2%Poisson ratio νcd [-] 0.48 ±2%Density ρcd [t/mm3] 6.0e-10 ±2%

9 Spot welds1: E modulus Es [N/mm2] 2.1e+5 ±5%Poisson ratio νs [-] 0.28 ±5%Density ρs [t/mm3] 1.0e-10 ±5%

10 Connection sun roof: E modulus Ecs [N/mm2] 2.1e+5 ±5%Poisson ratio νcs [-] 0.28 ±5%Density ρcs [t/mm3] 2.0e-6 ±5%

1 modeled as beam elements

110

5.2 Vibration engineering: Frequency response function envelopes

5.2.3.4 Uncertainty analysis results, floor model

Fig. 5.17 shows the computed envelope curve for five and thirteen model evaluations. Since theuncertain force P and the uncertain damping loss factor η only cause an increase or decreaseof the amplitudes but not a shift of the resonance frequencies, only few model evaluations arerequired to compute a very accurate envelope curve. The maximum estimated error of thesparse grid surrogate function is just 0.0053 in the exponent for all discrete frequencies.

50 100 150 200 250 300 350 400 450 50010

−5

10−4

10−3

10−2

10−1 min/max

crisp

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)50 100 150 200 250 300 350 400 450 500

10−5

10−4

10−3

10−2

10−1 min/max

crisp

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)

Figure 5.17: Floor, displacement response spectrum envelopes for uncertain force P (±10%)and uncertain damping η (±25%); (a): N = 5, (b): N = 13.

For the main simulation of the model using nine uncertain parameters, we employed thedimension-adaptive approach, with up to 399 model evaluations. Already with less than 100model evaluations, a good approximation of the envelope curve was achieved, see Fig. 5.18.Since the displacement response now behaves very nonlinear for the considered uncertaintydomain, more iterations are required in comparison to the first approximation of level n = 1(Fig. 5.18,(a)) using 2d +1 = 19 model evaluations, which represents a linear superposition ofunivariate interpolants with just three support nodes per dimension. The dimensional adaptivityof the algorithm causes dimensions with high influence to be refined primarily. For the givenuncertain parameters, these are the modal damping factor η , the plate thickness d, and thematerial properties of the frame E1 and ρ1. The estimated maximum error of the dimension-adaptive interpolant over all frequencies is shown in Fig. 5.19.

The envelope curves represent the (approximated) worst case of the maximum uncertainty.In fact, this is already a summarizing result of the uncertain outputs of the model, i.e. the modelresponse at 500 discrete frequencies. We can of course determine the fuzzy response at eachfrequency separately in order to examine certain frequencies of interest in greater detail, and tovisualize the degree of nonlinearity. Such a result is shown exemplary in Fig. 5.20, having beencomputed using 51 α-cuts. Note that reconstructing the fuzzy-valued results does not requireany additional model evaluations; in this example, we have employed the dimension-adaptiveinterpolant constructed from the 399 model evaluations.

111

5 Applications

50 100 150 200 250 300 350 400 450 50010

−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)

(b)(c)(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250 300 350 400 450 500

10−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)

(b)

(c)(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]

50 100 150 200 250 300 350 400 450 50010

−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)(b)

(c)

(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250 300 350 400 450 500

10−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)(b)(c)

(d)

(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]

50 100 150 200 250 300 350 400 450 50010

−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)(b)(c)(d)

(e)

(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250 300 350 400 450 500

10−6

10−5

10−4

10−3

10−2

10−1

100

min/maxcrisp

PSfrag replacements

(a)(b)(c)(d)(e)

(f)

disp

lace

men

t[m

m]

frequency [Hz]

Figure 5.18: Floor model, displacement response spectrum envelopes for nine uncertain pa-rameters according to Table 5.6 and increasing refinement of the interpolant; (a):N = 19, (b): N = 45, (c): N = 65, (d): N = 97, (e): N = 179, (f): N = 399.

112

5.2 Vibration engineering: Frequency response function envelopes

0 100 200 300 4000

0.02

0.04

0.06

0.08

0.1

0.12

0 100 200 300 4000.2

0.4

0.6

0.8

1

1.2

1.4

1.6w

avg, abse

max, abs

PSfrag replacements

(a) (b)

aver

age

ofab

solu

tesu

rplu

ses

estim

ated

erro

r

number of points Nnumber of points N

Figure 5.19: Floor model: (a): Average of absolute surpluses of grids with active index, (b):estimated maximum absolute error in the exponent over all frequencies.

Figure 5.20: Fuzzy receptance at f =50 Hz

10−5

10−4

10−3

10−2

0

0.2

0.4

0.6

0.8

1

PSfrag replacements

displacement [mm]

degr

eeof

poss

ibili

ty(α

-lev

el)

5.2.3.5 Uncertainty analysis results, cabin model

As with the floor model, we have first determined the displacement response spectrum en-velopes for just two uncertain parameters, the force P and the modal damping η . The sameobservations as with the smaller floor models were made; very few evaluations were neededto get an accurate approximation of the envelope curve. The maximum estimated absoluteerror of the surrogate function was just 0.0046 in the exponent over all discrete frequencies.Fig. 5.21 shows the computed envelope curve for five and thirteen model evaluations.

Then, the main simulation using 27 uncertain input parameters was carried out. By per-forming the model evaluations simultaneously on a high-performance computing cluster withthe procedure described in Section 5.2.3.2, we were able to construct an increasingly accuratesparse grid surrogate function with over 1000 support nodes, using the dimension-adaptive al-

113

5 Applications

50 100 150 200 25010

−5

10−4

10−3

min/maxcrisp

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)50 100 150 200 250

10−5

10−4

10−3

min/maxcrisp

PSfrag replacements disp

lace

men

t[m

m]

frequency [Hz]

(a)

(b)

Figure 5.21: Cabin, displacement response spectrum envelopes for uncertain force P (±10%)and uncertain damping η (±25%); (a): N = 5, (b): N = 13.

gorithm. However, it turned out that the uncertainty in more than ten parameters contributedsignificantly to the resulting interpolant, i.e., the sparse grid was refined by the algorithm withrespect to these dimensions. In view of this fact, a mere thousand model evaluations were stilltoo few evaluations to achieve a converging result. Nevertheless, the hierarchical surplusescomprising the estimated absolute error decreased quite significantly with increasing numberof nodes, as shown in Fig. 5.22. The overall shape of the frequency response envelope emergedalready around a few hundred model evaluations, see Fig.5.23. From an engineering point ofview, these results can already be considered quite revealing; the estimated error gives theengineer a good idea on the reliability of the result.

0 200 400 600 800 10002

4

6

8

10

12

14

16x 10

−3

0 200 400 600 800 10000

0.1

0.2

0.3

0.4

0.5

0.6

0.7w

avg, abse

max, abs

PSfrag replacements

(a) (b)

aver

age

ofab

solu

tesu

rplu

ses

estim

ated

erro

r

number of points Nnumber of points N

Figure 5.22: Cabin model; (a): Average of absolute surpluses of grids with active index, (b):estimated maximum absolute error in the exponent over all frequencies.

114

5.2 Vibration engineering: Frequency response function envelopes

50 100 150 200 25010

−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)

(b)(c)(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250

10−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)

(b)

(c)(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]

50 100 150 200 25010

−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)(b)

(c)

(d)(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250

10−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)(b)(c)

(d)

(e)(f)

disp

lace

men

t[m

m]

frequency [Hz]

50 100 150 200 25010

−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)(b)(c)(d)

(e)

(f)

disp

lace

men

t[m

m]

frequency [Hz]50 100 150 200 250

10−6

10−5

10−4

10−3

10−2

min/maxcrisp

PSfrag replacements

(a)(b)(c)(d)(e)

(f)

disp

lace

men

t[m

m]

frequency [Hz]

Figure 5.23: Cabin model, displacement response spectrum envelopes for 27 uncertain param-eters according to Table 5.7 and increasing refinement of the interpolant; (a):N = 55, (b): N = 95, (c): N = 237, (d): N = 427, (e): N = 881, (f): N = 1027.

115

6 Concluding Remarks

Sparse grid interpolation offers a powerful tool to accurately perform uncertainty modelingbased on fuzzy sets. Due to the excellent ratio of the number of required function evaluationscompared to the interpolation quality, the proposed method is especially appealing when theobjective function is high-dimensional and expensive to evaluate. In the context of this thesis,the following main points were addressed:

• Suitable algorithms were developed for the hierarchical construction of piecewise multi-linear and polynomial sparse grid interpolants and their efficient evaluation. In particular,barycentric polynomial interpolation was extended to the multivariate case and combinedwith the sparse grid technique to achieve a stable algorithm that allows the evaluation ofpolynomial interpolants in O(N).

• The dimension-adaptive approach proposed by Gerstner and Griebel [26] was success-fully adapted to the problem of interpolation. The original data structure proposed in thiscontext was significantly further improved to not only reduce the required storage space,but also to lower the computational complexity.

• Several ways were proposed to solve the sparse grid optimization problems that arise inthe implementation of the extension principle.

• The entire procedure of uncertainty modeling using fuzzy calculus and sparse grids wasillustrated by means of applications in dynamic systems; the wide applicability of theapproach was illustrated by applying the method to objective models involving the solu-tion of ordinary differential equations, delay differential equations, algebraic differentialequations, and involving numerical methods such as the spectral element method and thefinite element method.

Despite the promising results presented here, further research is needed to bring sparse grid-based uncertainty modeling to its full potential. The following list indicates some points thatcould be addressed in the future.

• The optimization methods, both complete and incomplete, can certainly be further im-proved; a comparably small amount of work was dedicated to this task.

• Other sparse grid techniques, such as the hierarchical polynomial basis approach byBungartz [15] could be combined with the dimension-adaptive piecewise linear approachto more effectively refine regions with strong local features. The hierarchical polynomialbases may also be well-suited for interval-based branch-and-bound optimization due totheir compact support.

117

6 Concluding Remarks

• Classical sensitivity information could be employed to further reduce the initial 2d + 1evaluations required with the dimension-adaptive approach, which can be inhibitive incase of very high-dimensional problems.

• Reliably quantifying the degree of influence of each uncertain input parameter on theuncertainty of the output [36, 38], at an acceptable cost, is another challenge that shouldbe tackled.

• The information gathered from the uncertainty analysis could used be to provide infor-mation on how to best optimize the considered objective models with respect to a desireddesign target and a maximum permitted uncertainty.

• Last but not least, developing efficient parallel routines is a must in providing applicabil-ity to today’s real-world problems, such as the truck cabin model presented in Chapter 5.The evaluations of the objective model as well as the evaluation and construction of theinterpolants, especially in case of multiple output variables, should be parallelized.

118

Bibliography

[1] S. Achatz. Adaptive finite Dünngitter-Elemente höherer Ordnung für elliptische partielleDifferentialgleichungen mit variablen Koeffizienten. PhD thesis, Technische UniversitätMünchen, 2003. 37

[2] C. S. Adjiman, I. P. Androulakis, and C. A. Floudas. A global optimization method,αBB, for general twice-differentiable constrained NLPs - II. Computers and ChemicalEngineering, 22:1159–1179, 1998. 15

[3] C. S. Adjiman, S. Dallwig, C. A. Floudas, and N. A. A global optimization method,αBB, for general twice-differentiable constrained NLPs - I. Computers and ChemicalEngineering, 22:1137–1158, 1998. 15

[4] A. C. Antoulas and D. C. Sorensen. Approximation of large-scale dynamical systems: anoverview. Int. J. Appl. Math. Comput. Sci., 11(5):1093–1121, 2001. 59

[5] A. C. Antoulas, D. C. Sorensen, and S. Gugercin. A survey of model reduction methodsfor large-scale systems. In Contemporary Mathematics, volume 280, pages 193–219.AMS Publications, 2001. 59

[6] B. M. Ayyub, A. Guran, and A. Haldar, editors. Uncertainty Modeling in Vibration andFuzzy Analysis of Structural Systems, volume 10 of Series on Stability, Vibration andControl of Systems B. World Scientific Publishing, Singapore, 1997. 1

[7] V. Barthelmann, E. Novak, and K. Ritter. High dimensional polynomial interpolation onsparse grids. Adv. Comput. Math., 12(4):273–288, 2000. 35, 36, 39, 40, 41, 50, 53, 86

[8] J.-P. Berrut and L. N. Trefethen. Barycentric Lagrange interpolation. SIAM Review,46(3):501–517, 2004. 28, 29, 30

[9] I. F. Blake. An Introduction to Applied Probability Theory. John Wiley & Sons, NewYork-Chichester-Brisbane, 1979. 7

[10] H.-H. Bothe. Fuzzy Logic. Springer-Verlag, Berlin, 2nd edition, 1995. 3

[11] L. Brutman. Lebesgue functions for polynomial interpolation—a survey. Ann. Numer.Math., 4(1-4):111–127, 1997. 26

[12] J. J. Buckley, E. Eslami, and T. Feuring. Fuzzy Mathematics in Economics and Engineer-ing. Physica-Verlag, Heidelberg, Germany, 2002. 86

119

Bibliography

[13] J. J. Buckley and Y. Qu. On using α-cuts to evaluate fuzzy functions. Fuzzy Sets andSystems, 38:309–312, 1990. 11

[14] H.-J. Bungartz. Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidi-mensionalen Poissongleichung. PhD thesis, Technische Universität München, Germany,1992. 37

[15] H.-J. Bungartz. Finite Elements of Higher Order on Sparse Grids. Shaker Verlag, Aachen,1998. 39, 44, 45, 50, 59, 117

[16] H.-J. Bungartz and M. Griebel. Sparse grids. Acta Numerica, 13:147–269, 2004. 23, 36

[17] C. W. Clenshaw and A. R. Curtis. A method for numerical integration on an automaticcomputer. Numerische Mathematik, 2:197–205, 1960. 37

[18] L. Dixon and G. Szego. The Global Optimization Problem: An Introduction, chapterTowards global optimization 2, pages 1–15. North Holland, New York, NY, 1978. 84, 86

[19] S. Donders, D. Vandepitte, J. Van de Peer, and W. Desmet. The short transformationmethod to predict the FRF of dynamic structures subject to uncertainty. In Proceedingsof the International Conference on Noise & Vibration Engineering ISMA 2004, Leuven,Belgium, 2004. 16, 18

[20] W. Dong and H. C. Shah. Vertex method for computing functions of fuzzy variables.Fuzzy Sets and Systems, 24:65–78, 1987. 14, 16, 17

[21] W. M. Dong and F. S. Wong. Fuzzy weighted averages and implementation of the exten-sion principle. Fuzzy Sets and Systems, 21:183–199, 1987. 16

[22] D. Dubois and H. Prade. Fuzzy Sets and Systems, Theory and Applications, volume 144of Mathematics in Science and Engineering. Academic Press, Inc., New York, 1980. 3,6, 10, 14

[23] D. Dubois and H. Prade. Possibility Theory. Plenum Press, New York, 1988. 1

[24] J. Garloff, C. Jansson, and A. P. Smith. Lower bound functions for polynomials. Journalof Computational and Applied Mathematics, 157:207–225, 2003. 77

[25] A. C. Genz. A package for testing multiple integration subroutines. In P. Keast andG. Fairweather, editors, Numerical Integration, pages 337–340. Kluwer, Dordrecht, 1987.53

[26] T. Gerstner and M. Griebel. Dimension-adaptive tensor-product quadrature. Computing,71(1):65–87, 2003. 2, 59, 60, 61, 63, 64, 117

[27] R. E. Giachetti and R. E. Young. Analysis of the error in the standard approximation usedfor multiplication of triangular and trapezoidal fuzzy numbers and the development of anew approximation. Fuzzy Sets and Systems, 91(1):1–13, 1997. 8

120

Bibliography

[28] R. E. Giachetti and R. E. Young. A parametric representation of fuzzy numbers and theirarithmetic operators. Fuzzy Sets and Systems, 91(2):185–202, 1997. 8, 14

[29] B. V. Gnedenko. Theory of Probability. Taylor & Francis, London, Great Britain, 1998.7

[30] W. Gropp, E. Lusk, and A. Skjellum. Using MPI: Portable Parallel Programming with theMessage-Passing Interface. MIT Press, Cambridge, MA, second edition edition, 1999.109

[31] W. Gropp and J. J. Moré. Optimization environments and the NEOS server. In Approx-imation Theory and Optimization, pages 167–182. Cambridge Univ. Press, Cambridge,1997. 66

[32] E. Hairer, S. P. Nørsett, and G. Wanner. Solving Ordinary Differential Equations I, vol-ume 8 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, 1993.91, 92

[33] E. Hairer and G. Wanner. Solving Ordinary Differential Equations II, volume 14 ofSpringer Series in Computational Mathematics. Springer-Verlag, Berlin, 1996. 95

[34] E. H. Hansen. Global Optimization Using Interval Analysis. Marcel Dekker, New York,NY, 1992. 14, 15, 80, 82

[35] M. Hanss. The transformation method for the simulation and analysis of systems withuncertain parameters. Fuzzy Sets and Systems, 130(3):277–289, 2002. 8, 14, 18, 73, 74,84

[36] M. Hanss. The extended transformation method for the simulation and analysis of fuzzy-parameterized models. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 11(6):711–727, 2003. 14, 18, 74, 118

[37] M. Hanss. Applied Fuzzy Arithmetic. Springer, Berlin, 2005. 3

[38] M. Hanss and A. Klimke. On the reliability of the influence measure in the transformationmethod of fuzzy arithmetic. Fuzzy Sets and Systems, 143(3):277–289, 2004. 14, 118

[39] M. Hegland. Adaptive sparse grids. In K. Burrage and R. B. Sidje, editors, Proceedingsof the 2001 International conference on Computational Techniques and Applications,University of Queensland, volume 44 of ANZIAM Journal, pages C335–C353, 2003. 2,59

[40] P. V. Hentenryck, L. Michel, and Y. Deville. Numerica: A Modeling Language for GlobalOptimization. MIT Press, Cambridge, MA, 1997. 16

[41] N. J. Higham. The numerical stability of barycentric Lagrange interpolation. IMA Journalof Numerical Analysis, 24:547–556, 2004. 30

121

Bibliography

[42] W. Huyer and A. Neumaier. Global optimization by multilevel coordinate search. J.Global Optim., 14(4):331–355, 1999. 15

[43] E. Isaacson and H. B. Keller. Analysis of numerical methods. John Wiley & Sons Inc.,New York, 1966. 26, 27

[44] L. Jaulin, M. Kieffer, O. Didrit, and É. Walter. Applied Interval Analysis. Springer,London, Great Britain, 2001. 2, 14, 15, 78, 80, 83

[45] D. R. Jones, C. D. Perttunen, and B. E. Stuckman. Lipschitzian optimization without theLipschitz constant. J. Optim. Theory Appl., 79(1):157–181, 1993. 15

[46] A. Kaufmann and M. M. Gupta. Introduction to Fuzzy Arithmetic. Van Nostrand ReinholdCo., New York, 1991. 7, 9, 14, 73

[47] R. Kearfott. Lecture Notes in Computer Science, volume 2861, chapter GlobSol: History,Composition, Advice on Use, and Future, pages 17–31. Springer Verlag, Berlin, 2003.16

[48] R. B. Kearfott. Rigorous global search: continuous problems, volume 13 of NonconvexOptimization and its Applications. Kluwer Academic Publishers, Dordrecht, 1996. 16

[49] A. Klimke. An efficient implementation of the transformation method of fuzzy arithmetic.In E. Walker, editor, Proceedings of NAFIPS 2003, pages 468–473, Chicago, IL, 2003.18, 78, 86

[50] A. Klimke. An efficient implementation of the transformation method of fuzzy arithmetic(extended preprint version), IANS preprint 2003/009. Technical report, University ofStuttgart, 2003. 18, 84

[51] A. Klimke. Uncertainty modeling using fuzzy arithmetic based on dimension-adaptivesparse grids. In Proceedings of the 20th Canadian Congress of Applied Mechanics CAN-CAM 05, pages 596–597, Montréal, QC, 2005.

[52] A. Klimke, K. Willner, and B. Wohlmuth. Uncertainty modeling using fuzzy arithmeticbased on sparse grids: applications to dynamic systems. Int. J. of Uncertainty, Fuzzinessand Knowledge-based Systems, 12(6):745–759, 2004.

[53] A. Klimke and B. Wohlmuth. Efficient fuzzy arithmetic for nonlinear functions of modestdimension using sparse grids. In IEEE International Conference on Fuzzy Systems 2004,volume 3, pages 1549–1554, Budapest, Hungary, 2004.

[54] A. Klimke and B. Wohlmuth. Computing expensive multivariate functions of fuzzy num-bers using sparse grids. Fuzzy Sets and Systems, 154(3):432–453, 2005.

[55] A. Klimke and B. Wohlmuth. Piecewise multilinear hierarchical sparse grid interpolationin MATLAB. ACM Transactions on Mathematical Software, 31(4), 2005. 93

122

Bibliography

[56] G. J. Klir. Fuzzy arithmetic with requisite constraints. Fuzzy Sets and Systems, 91:165–175, 1997. 14

[57] T. G. Kolda, R. M. Lewis, and V. Torczon. Optimization by direct search: new perspec-tives on classical and modern methods. SIAM Review, 45(3):385–482, 2003. 75

[58] A. J. Macleod. A comparison of algorithms for polynomial interpolation. Journal ofComputational and Applied Mathematics, 8:275–277, 1982. 30

[59] G. Maglaras, E. Nikolaidis, R. T. Haftka, and H. H. Cudney. Experimental comparisonof probabilistic methods and fuzzy set based methods for designing under uncertainty. InUncertainty Modeling in Vibration and Fuzzy Analysis of Structural Systems, volume 10of Series on Stability, Vibration and Control of Systems B, chapter 9, pages 253–318.World Scientific Publishing, Singapore, 1997. 2

[60] B. Möller and M. Beer. Fuzzy Randomness. Springer, Berlin, 2004. 3, 10

[61] R. E. Moore. Interval Analysis. Prentice Hall, Englewood Cliffs, NJ, 1966. 1, 14, 15

[62] M. Navara and Z. Zabokrtský. How to make constrained fuzzy arithmetic efficient. SoftComputing, 6:412–417, 2001. 14

[63] A. Neumaier. Taylor forms – use and limits. Reliab. Comput., 9(1):43–79, 2003. 77

[64] A. Neumaier. Complete search in continuous global optimization and constraint satisfac-tion. Acta Numerica, 13:271–369, 2004. 14, 15, 83

[65] E. Novak and K. Ritter. High-dimensional integration of smooth functions over cubes.Numer. Math., 75(1):79–97, 1996. 37

[66] R. F. Nunes, A. Klimke, and J. R. F. Arruda. On estimating frequency response func-tion envelopes using the spectral element method and fuzzy sets. Int. J. of Sound andVibration, 2005 (in press). 98, 99, 100, 101

[67] G. M. Phillips. Interpolation and approximation by polynomials. CMS Books in Math-ematics/Ouvrages de Mathématiques de la SMC, 14. Springer-Verlag, New York, 2003.26

[68] J. Pintér. Global optimization in action, volume 6 of Nonconvex Optimization and itsApplications. Kluwer Academic Publishers, Dordrecht, 1996. 15

[69] H. Pradlwarter and G. Schuëller. Stochastic structural dynamics – a primer for practicalapplications. In Uncertainty Modeling in Vibration and Fuzzy Analysis of StructuralSystems, volume 10 of Series on Stability, Vibration and Control of Systems B, chapter 1,pages 1–27. World Scientific Publishing, Singapore, 1997. 1

[70] A. Quarteroni, R. Sacco, and F. Saleri. Numerical Mathematics. Springer, Berlin, 2000.24, 25, 28

123

Bibliography

[71] A. Quarteroni and F. Saleri. Scientific Computing with Matlab. Springer, Berlin, 2003.23, 25

[72] T. J. Rivlin. An introduction to the approximation of functions. Blaisdell Publishing Co.,Waltham, MA, 1969. 26, 27

[73] T. J. Rivlin. Chebyshev polynomials. Pure and Applied Mathematics (New York). JohnWiley & Sons Inc., New York, 1990. 25, 29

[74] H. S. Ryoo and N. V. Sahinidis. A branch-and-reduce approach to global optimization. J.Global Optim., 8(2):107–138, 1996. 15

[75] N. V. Sahinidis. BARON: a general purpose global optimization software package. J.Global Optim., 8(2):201–205, 1996. 15

[76] A. Schreiber. Smolyak’s method for multivariate interpolation. PhD thesis, Georg-August-Universität Göttingen, Germany, 2000. 23, 35, 37, 45

[77] L. F. Shampine and S. Thompson. Solving DDEs in MATLAB. Appl. Numer. Math.,37(4):441–458, 2001. 93

[78] S. A. Smolyak. Quadrature and interpolation formulas for tensor products of certainclasses of functions. Soviet Math. Dokl., 4:240–243, 1963. 35

[79] F. Sprengel. Interpolation and wavelets on sparse Gauss-Chebyshev grids. In W. Hauss-mann et al., editor, Multivariate Approximation, volume 101 of Mathematical Research,pages 269–286. Akademie Verlag, Berlin, 1997. 23, 35

[80] F. Sprengel. Periodic interpolation and wavelets on sparse grids. Numer. Algorithms,17(1-2):147–169, 1998. 23, 35

[81] E. Stiefel. Einführung in die numerische Mathematik. B. G. Teubner, Stuttgart, 1976. 29

[82] A. Törn and A. Žilinskas. Global optimization, volume 350 of Lecture Notes in ComputerScience. Springer-Verlag, Berlin, 1989. 15

[83] K. L. Wood, K. N. Otto, and E. K. Antonsson. Engineering design calculations with fuzzyparameters. Fuzzy Sets and Systems, 52:1–20, 1992. 14, 16, 17

[84] H. Q. Yang, H. Yao, and J. D. Jones. Calculating functions of fuzzy numbers. Fuzzy Setsand Systems, 55:273–283, 1993. 14

[85] L. A. Zadeh. Fuzzy sets. Information and Control, 8:338–353, 1965. 1

[86] L. A. Zadeh. Outline of new approach to the analysis of complex systems and decisionprocesses. IEEE Trans. Systems, Man, and Cybernet., SMC-3:28–44, 1973. 1

[87] L. A. Zadeh. The concept of a linguistic variable and its application to approximatereasoning. Information Sci., 8:199–249, 1975. 10

124