محاسبه طرح آزمایشی CC بهینه با استفاده از روش سیمپلکس برنامه ریزی خطی

An experimental design is said to be cc-optimal if it minimizes the variance of the best linear unbiased estimator of View the MathML sourcecTβ, where cc is a given vector of coefficients, and ββ is an unknown vector parameter of the model in consideration. For a linear regression model with uncorrelated observations and a finite experimental domain, the problem of approximate cc-optimality is equivalent to a specific linear programming problem. The most important consequence of the linear programming characterization is that it is possible to base the calculation of cc-optimal designs on well-understood computational methods. In particular, the simplex algorithm of linear programming applied to the problem of cc-optimality reduces to an exchange algorithm with different pivot rules corresponding to specific techniques of selecting design points for exchange. The algorithm can also be applied to “difficult” problems with singular cc-optimal designs and relatively high dimension of ββ. Moreover, the algorithm facilitates identification of the set of all the points that can support some cc-optimal design. As an example, optimal designs for estimating the individual parameters of the trigonometric regression on a partial circle are computed.

Consider the linear regression model View the MathML source(f,X) with uncorrelated homoscedastic observations yy satisfying View the MathML sourceE(y)=fT(x)β, where ββ is an unknown mm-dimensional parameter and View the MathML sourcef is a known vector of regression functions linearly independent on the experimental domain X={x1,…,xk}X={x1,…,xk}. Let View the MathML sourcec be a fixed nonzero mm-dimensional vector. The main purpose of this paper is to propose an algorithm based on the simplex method of linear programming for constructing View the MathML sourcec-optimal approximate designs for the model View the MathML source(f,X). An experimental design View the MathML sourceξc∗ is said to be View the MathML sourcec-optimal if, under View the MathML sourceξc∗, the best linear unbiased estimator of View the MathML sourcecTβ has the minimal possible variance (see (2) for a more precise definition). For instance, if View the MathML sourcec is the ii-th unit vector View the MathML sourceei∈Rm, then View the MathML sourceξc∗ is optimal for estimating individual parameters βiβi, if View the MathML sourcec=f(x), then View the MathML sourceξc∗ is optimal for estimating the mean value of response in xx, and so on. Moreover, View the MathML sourcec-optimal designs are closely related to several other criteria of design optimality, in particular the so-called standardized criteria (see Dette (1997)). We refer the reader to Pázman (1986) and Pukelsheim (1993) for details on general optimal design of experiments. As is usual, by an approximate design we understand a probability ξξ on XX with the interpretation that ξ(x)ξ(x) represents the proportion of the measurements to be taken in xx. The set of all approximate designs on XX will be denoted by ΞΞ. A design ξ∈Ξξ∈Ξ is said to be an exact design of size nn, if and only if (iff) it can be realized by nn measurements, i.e., iff ξ(xj)=nj/nξ(xj)=nj/n for all j=1,…,kj=1,…,k and some nj∈N∪{0}nj∈N∪{0}. Let View the MathML sourceΞc be the set of all the designs ξ∈Ξξ∈Ξ that guarantee estimability of View the MathML sourcecTβ, i.e., such that View the MathML sourcec belongs to the range of the information matrix equation(1) View the MathML sourceM(ξ)=∑x∈Xf(x)fT(x)ξ(x). Turn MathJax on If we perform nn measurements according to an exact design View the MathML sourceξ∈Ξc of size nn, and if View the MathML sourceβˆξ is the least squares estimate of ββ, then the variance of the best linear unbiased estimator of the linear combination View the MathML sourcecTβ is equation(2) View the MathML sourceVar(cTβˆξ)=σ2n−1cTM−(ξ)c, Turn MathJax on where σ2σ2 is the variance of the individual observations yy, and View the MathML sourceM−(ξ) is a pseudoinverse of View the MathML sourceM(ξ). Note that for View the MathML sourceξ∈Ξc the value View the MathML sourcecTM−(ξ)c does not depend on the choice of the pseudoinverse. Equality (2) motivates the following definition: Any design View the MathML sourceξc∗∈Ξc that minimizes View the MathML sourcecTM−(ξ)c among all designs View the MathML sourceξ∈Ξc is said to be View the MathML sourcec-optimal for the model View the MathML source(f,X). We define the View the MathML sourcec-optimal variance of the model View the MathML source(f,X) to be View the MathML sourcecTM−(ξc∗)c, and the View the MathML sourcec-optimal information matrix to be the information matrix of any View the MathML sourcec-optimal design. It is possible to show that a View the MathML sourcec-optimal design always exists, but it does not have to be unique. Moreover, for many standard models and choices of the vector View the MathML sourcec, some or all of the View the MathML sourcec-optimal information matrices are singular. The Elfving set of the model View the MathML source(f,X) is defined by View the MathML sourceE=conv(f(X)∪−f(X)), Turn MathJax on where View the MathML sourcef(X)={f(x1),…,f(xk)} and View the MathML sourceconv is the convex hull. By ∂E∂E we will denote the boundary of EE. The Elfving theorem can be formulated as follows (Elfving (1952); see also Pázman (1986) or Pukelsheim (1993)). Theorem 1. Let ξ∈Ξξ∈Ξ. Then the following statements are equivalent: (i) The design ξξis View the MathML sourcec-optimal for View the MathML source(f,X); (ii) There exists h>0h>0and a selection of signs ϵ(x)∈{−1,1}ϵ(x)∈{−1,1}for all x∈Xx∈X, such that equation(3) View the MathML sourcehc=∑x∈Xϵ(x)f(x)ξ(x)∈∂E. Turn MathJax on In such a case h−2h−2is the View the MathML sourcec-optimal variance of the model View the MathML source(f,X). In López-Fidalgo and Rodríguez-Díaz (2004), the Elfving theorem has been used to construct algorithms for View the MathML sourcec-optimal designs (with a compact experimental domain, possibly infinite) requiring constrained nonlinear optimization routines and achieving a practically efficient performance for dimensions mm up to 4. In the present paper, we use the Elfving theorem to reformulate the problem of constructing a View the MathML sourcec-optimal design on a finite experimental domain as a specific problem of linear programming (LP). As a consequence, questions regarding View the MathML sourcec-optimality on a finite experimental domain can be directly answered by the extensive theory of LP. Moreover, LP gives us algorithmic tools for calculating View the MathML sourcec-optimal designs (such as the simplex method) that are rapid and reliable even in the case of relatively high dimensions of the parameter. With present computer hardware, the algorithm can be applied to problems with a very large experimental domain (e.g. thousands of design points). Thus, even in the case of an infinite experimental domain such as an interval, it is often possible to use a dense discretization with a negligible loss of efficiency.

In the opinion of the authors, the main contribution of this paper is the formulation of the problem of approximate View the MathML sourcec-optimal design on a finite experimental domain as a special case of linear programming (LP). As a consequence, it is possible to calculate the View the MathML sourcec-optimal designs by widely available LP algorithms. The algorithm SAC that we propose is based on the simplex method of LP and uses specifics of our problem that contribute to the efficiency of the computation, e.g. possibility of a rapid construction of an initial basic feasible solution. In addition, SAC allows us to easily identify the set of all the points that can support some View the MathML sourcec-optimal design. For a general LP problem, it has been proved that the worst-case complexity of the simplex method is exponential. However, it is also known (see, e.g. Borgwards (1987)) that for the average-case problems the number of iterations of the simplex method is only linear in the size of the problem. We numerically explored the average number of iterations of SAC for increasing number kk of design points. The computations for the cubic trigonometric model (see Fig. 3) suggest that the average number of iterations of SAC is even smaller than in the case of a general LP problem — we conjecture that it is sub -linear in kk. Consequently, the algorithm can be applied to View the MathML sourcec-optimal design problems with a large experimental domain without significant loss of efficiency. Full-size image (19 K) Fig. 3. Average number of SAC iterations (vertical axis) depending on the size kk of the experimental domain for the problem of View the MathML sourcee7-optimal designs in the cubic trigonometric model. The average is based on individual runs for different values of the half-length aa. Figure options To our best knowledge, computing the optimal designs with respect to other well-known criteria (such as DD-, AA- or EE-optimality) cannot be reduced to a linear programming problem. To compute such designs we can use more complex algorithms for solving semidefinite programming or max-det programming problems, as noted in Vandenberghe et al. (1998).