Cover Page

Series Editor
Nikolaos Limnios

Interpolation and Extrapolation Optimal Designs 2

Finite Dimensional General Models

Giorgio Celant

Michel Broniatowski

Wiley Logo


This second volume, dedicated to optimal designs in interpolation and extrapolation, extends the concepts developed in Volume 1 [CEL 16] to the general framework of regression models defined on arbitrary finite dimensional linear spaces of regressors. This generalization is handled in relation to a variety of aspects. It pertains to the class of regressors, and extends the approach of the first volume to numerous optimality criteria. Special attention is also paid to the relations between these optimality criteria. The object to be estimated is also of a more general nature than an interpolated or an extrapolated value of the response variable under a given operational condition; these quantities are considered as special cases of a linear form of the coefficients of the regression model. Many hypotheses which have been assumed in Volume 1 are weakened. Nonlinear models are considered, as well as heteroscedastic or autocorrelated ones. Some excursion is proposed in cases when the dimension of the regressors is finite but is unknown, and tests for such problems are discussed. Finally, the algorithmic approach to optimal designs is considered, along with a discussion on the corresponding criteria, in the multivariate setting.

This volume is somehow self-consistent, and Volume 1 helps as a benchmark.

The geometric approach to Elfving’s theory follows the one adopted by Pukelsheim; we adopted the arguments arising from the theory of uniform approximation of continuous functions by a Haar system in order to achieve the analysis of the optimal designs for linear forms of the parameters in a Chebyshev regression; this is in the vein of many fundamental contributions in this field, as promoted by Kiefer and Wolfowitz, Karlin and Studden, and others.

We have found it useful to present a number of algorithms; these are stated with greater emphasis on their principles, than on their implementation.

Giorgio CELANT
February 2017


The first four chapters contain material pertaining to the uniform approximation of continuous functions defined on a compact domain, making use of elements in a Haar finite dimensional linear space. The reader therefore has at their disposal the necessary topics to be used in a self contained volume. Also, much of the material presented here is to be used in the third volume, dealing with the infinite dimensional setting. The notation and style follow the approach which was adopted in the first volume.

The first chapter is devoted to the approximation of continuous functions in a normed space. Discussion is held on the advantages or drawbacks resulting from the fact that the norm is either induced by an inner product or not, in terms of existence and uniqueness of the approximation. We also consider natural questions pertaining to the approximating functions, such as rates of convergence, etc., in connection with some closeness considerations between the function to be approximated and the chosen class of approximating functions. Finally, we consider the choice of the norm in relation with requirements on the resulting measurement of the error. At the end of this first chapter, we deal with the special choice of Lp norms, together with some robustness considerations.

The second chapter is of fundamental importance for the topics covered in this volume. In the first volume, optimal interpolation and extrapolation designs were obtained, based on the Borel–Chebyshev theorem for the uniform polynomial approximation of continuous functions defined on a compact set of the real line. The generalization captured here holds on the substitution of the approximating elements by elements in a wider class than the class of polynomials with known degree. Extension of properties of such polynomials to larger classes of functions and the possible limits of such extensions is the core of this chapter, together with appropriate generalization of the Borel–Chebyshev theorem. Generalized polynomials, so-called Chebyshev or Haar systems are defined, and the corresponding properties of the linear space spanned by those systems (Haar spaces) are presented. In those spaces, generic elements share properties of usual polynomials, the Gauss d’Alembert theorem holds, as does an extended version of the Borel–Chebyshev theorem.

The chapter provides definitions for these generalized polynomials, together with a study of their algebraic properties (analysis of their roots, number of roots, etc.), and with a study of their properties with respect to the approximation of functions.

Chapter 3 is devoted to the various theorems that yield the tools for the approximation of functions in a Haar space.

Chapter 4 produces the explicit form of the best generalized polynomial that approximates a given continuous function uniformly. As such, the algorithms are similar to those presented in the first volume, at least in their approach; they generalize the algorithms of de la Vallée Poussin and Remez.

The interested reader will find much additional material in the following books: Rice [RIC 64], Dzyadyk [DZY 08], Achieser [ACH 92], Cheney [CHE 66], Karlin and Studden [KAR 66b], Natanson [NAT 64].

Chapters 5, 6, 7 and 8 are specifically devoted to the study of optimal designs.

Chapter 5 extends the results pertaining to extrapolation and interpolation designs to the context of the Chebyshev regression. The support of the designs is obtained through the Borel–Chebyshev theorem adapted to the generalized polynomials. The measure with such support, which determines the design, is characterized by a theorem due to Kiefer and Wolfowitz; the geometric approach which is adopted here is due to Hoel.

Chapter 6 is an extension of Chapter 5. The extrapolation is seen as a special linear form; in order to determine the optimal design for the estimation of a given linear form, a first analysis of the Gauss–Markov estimator is performed, hence focusing on the two ingredients which yield to specific questions in the realm of designs defined by generalized polynomials: bias and variance arguments. Unbiasedness is expressed in various ways, and yields to the notion of estimable linear forms. This approach induces a study of the moment matrix. The basic results that allow for the definition of the optimal design are Elfving and Karlin–Studden theorems.

Elfving’s theorem characterizes the optimal design for the estimation of a linear form cθ in a model of the form


in terms of the properties of the vector c which defines this form.

This result assesses that there exists some positive constant ρ such that ρ−1c is a convex combination of points of the form ± X(xi), i = 1, …, l where the xi’s are the supporting points of the c-optimal design; l denotes the cardinality of the support, and the weights of this convex combination are the frequencies of the design. Finally Elfving theorem assesses that

  1. 1) ρ2 is the variance of the least square estimator of cθ when evaluated on the xi’s
  2. 2) The X(xi)’s are frontier points of the so called Elfving set; the value of l results from Carathéodory theorem for convex sets.

Chapter 6 provides an account of the above construction and results. Only in a few cases can the Elfving theorem produce the optimal design in an explicit way. However, when combined with the theorem by Kiefer and Wolfowitz obtained in Chapter 5, together with the extended Borel–Chebyshev theorem and the Karlin and Studden theorem, an operational approach to the optimal design can be handled. The Hoel Levine design, obtained in Volume 1, is deduced as a by-product of Karlin and Studden theorem. The geometric approach to Elfving’s theory, which has been chosen, follows Pukelsheim’s arguments; the discussion of Karlin and Studden’s theorem makes use of the theory of uniform approximation of functions.

The beginning of Chapter 7 considers various optimization criteria for the design. Relations between them are stated in a fundamental result which is known as the Kiefer–Wolfowitz equivalence theorem. Schoenberg’s theorem (which is only partly proved in this volume) allows for a generalization of the optimal design by Guest (see Volume 1) to the general Chebyshev regression.

The chapter also considers the consequences of relaxing a number of hypotheses assumed in Volume 1, such as homoscedasticity or linearity. In the heteroscedastic case, the Elfving theorem is generalized, leading to the theorem of Letz, Dette and Pepelyshev.

Nonlinearity leads to the study of the Fisher information matrix. We also propose a brief excursion toward cases when the polynomials are substituted for analytic functions. Various results in relation to the support of the optimal design for a linear form close this chapter, following various remarks by Kiefer, Wolfowitz and Studden.

The last chapter presents algorithms leading to optimal designs with respect to various criteria. The main topics are related to the problem posed by multi-valued regressors, with a joint range that differs from the Cartesian product of their univariate ranges, a case commonly met in applications. Generally, the simultaneous variation of the factors induces constraints in the regressor range which invalidate various symmetries, which in turn makes the optimal design a challenge. This chapter starts with a short discussion on such issues, and turns to the pioneering works of Fedorov and Wynn, and their extensions. Exchange algorithms are presented as well as a recent algorithm by Pronzato and Zhigljavsky, which obtains an optimal design under a concave criterion.