Abstract: The main aim of the study was to develop an efficient search algorithm for locating D-optimal exact design. Within a design class, the procedure requires not more than 25% search on the total available designs. Specifically, under some arrangements, there exists a D-optimal exact design within a set of designs constituting about 25% of the total designs. An interesting property of the algorithm is that it eliminates as much as 80% of the total available designs, a lot of which are inferior to the optimal design. Also the new algorithm gives reduction in the number of determinant evaluations. With some rules of selection, the algorithm is certain to locate the required D-optimal exact design. The working of the algorithm has been tested using first order bivariate model defined on a design region that is supported by the points of the Circumscribed Central Composite Design.
INTRODUCTION
Algorithms play very important roles in design construction and have been widely used in the construction of D-optimal designs. Most D-optimal designs were generated by search algorithms such as the DETMAX algorithm of Mitchell (1974). The combinatorial algorithm of Onukogu and Iwundu (2007) which requires grouping design points in the design region according to their distances from the centre of the design region into g1, g2,..., gH groups, serves extensively well in locating D-optimal designs and is applicable under varying experimental conditions as seen in the study of Onukogu (2012). Rules for obtaining a starting design that is as close as possible to the optimal design as measured by the determinant value of the information matrix, have been suggested in the study of Iwundu (2010). The principles embodied in the combinatorial algorithm were utilized by Iwundu and Otaru (2014), while studing the effects of imposing D-optimality criterion on the design regions of the Central Composite Designs. Although the algorithm is certain to converge to the required optimal design measure, there is the need to reduce the number of determinant evaluations. The essence of this study was to present an algorithm that allows not more than a 25% search in locating the best design within a design class. The fundamental principles used in this study are as in the study of Onukogu and Iwundu (2007) and the elaborated algorithm of Iwundu and Otaru (2014). The sequential steps involved in the elaborated algorithm of Iwundu and Otaru (2014) are briefly outlined.
The algorithm assumes the initial tuple of support points at step 0 as:
where, r1 is the initial number of support points taken from group g1, r2 is the initial number of support points taktuple of support pointsen from group g2, r3 is the initial number of support points taken from group g3..., rf is the initial number of support points taken from group gf..., rH is the initial number of support points taken from group gH.
The group gf contains the number of support points, rf
held fixed while making increments on the ri’s of the other
groups. By incremental changes on the ri, the optimal number of support
points, namely, r1', r2',..., rH’, taken
from the H-groups while holding rf value fixed are approched. After
defining the initial tuple of support points
At each sub-step of step 1, the determinant value of information matrix associated
with the best design in the category is evaluated. These determinant values
are respectively,
increments in the decreasing direction is required and we do not need to explore all sub-steps of step 2. Incrementing r1 by 2 is equivalent to incrementing r1-1 by 1. Consequently, the required tuples of support points at this iteration are:
As before, the determinant value of the best designs in each of the combinations
or categories are computed. At step 2, the best determinant value is d2.
This value will again be compared with d1 to check for convergence.
If d2>d1, an increment of 3 is effected on r1.
If otherwise, then df* = d1. Continuing the process will
yield the tuple of support points.
where, ri* is the optimal number of support points taken from the ith group gi, i = 1, 2,..., r,..., H. The D-optimal exact design is contained in the immediate tuple and is associated with dc*.
MATERIALS AND METHODS
It was assumed that for given experimental space,
H1 search: The H1 search represents the algorithm
when all support points are taken from only one group. Let
| • | Obtain: |
| sub-designs from g1(N1) | |
| • | List the a1 sub-designs as ξ1 = {a11},
ξ2 = {a12},..., |
| • | Compute det i = det M(ξi); i = 1, 2,..., a1 |
| • | Set dc* = max {det 1, det 2,..., det a1} |
H2 search: The H2 search represents the algorithm
when support points are taken from only two groups. Let
| • | Obtain: |
| sub-designs from g1(N1) and: |
| sub-designs from g2(N2) | |
| • | List the a1 sub-designs as: |
| and the a2 sub-designs as: |
| • | Form sets of composite designs from a1 and a2 sub-designs as: |
| • | Set 1: |
| • | Set2: |
| • | Set a1: |
This arrangement holds provided a1≤a2. However, if a1>a2, the groups within the class, say:
c2 = {r1: r2} may be repositioned as c2 = {r2: r1}
| • | Choose any set i (i = 1,2,..., a1) and compute detM (ξi1) = det 1, detM (ξi2) = det 2,..., detM = det a2 |
| • | Set = max {det 1, det 2,..., det a2} |
It was remarked that provided the designs are such
H3 search: The H3 search represents the algorithm
when support points are taken from only three groups. Let
| • | Obtain: |
| sub-designs from g1(N1): |
| sub-designs from g2(N2) and: |
| sub-designs from g3(N3) | |
| • | List the a1 sub-designs as: |
| a2 sub-designs as: |
| and a3 sub-designs as: |
| • | Form sets of composite designs from a1, a2 and a3 sub-designs as: |
| • | Set 1: |
|
|
| • | Set2: |
| |
| • | Set a1: |
| |
This arrangement holds provided a1≤a2≤a3. Where the restriction does not hold, the groups within the class may be repositioned to achieve the restriction.
| • | Choose any set i (say i = 2 ) and compute detM(ξijk); i = 2; j = 1, 2,..., a3; k = 1, 2,..., a3 |
| • | Set = max {detM(ξijk)}; i = 2; j = 1, 2,..., a3; k = 1, 2,..., a3. |
It is reminded that here the essence of the new algorithum is to reduce the number of designs to be included in the search to the bearest minimum without losing the required optimal design. When selection is from only one group, it was observed that the number of designs to be investigated is reasonably small and a 100% search is tolerable. However, it is possible to do a 25% search or less if the selection rules of Oladugba and Madukaife (2009) are adhered to. Furthermore, S3 search is equivalent to S2 search if one of the groups contains only one support point. The difference lies in the inclusion of the one support point in the design. Similarly, S2 search is equivalent to S1 search if one of the groups contains only one support point. The difference also lies in the inclusion of the one support point in the design. Where there is only one support point in a group, we say that there is no competing design point in that group.
Selection rules: The following selection rules should be adhered to when considering design points from a design class to go into the design measure in the construction of D-optimal exact N-point designs:
| • | When selection of design points is only from one group; perform a 100% search. However, with the rules of Oladugba and Madukaife (2009), a 25% search or less is possible |
| • | When selection is from more than one group, perform a 25% search in the direction of maximum set combination to obtain the desired design measure. In performing the 25% search, selection of points to go into the design measure are such that: |
| • | ||
| • | |
RESULTS
The algorithm was applied on the problem of locating a 5-point D-Optimal exact design for the no intercept, three parameter first order model y(x1, x2) = a1x1+a2x2+a12x1a2+e defined on the geometric region in Fig. 1.
Following the suggestion of Iwundu (2010), the initial tuple of support points is {3: 1: 1}. Since the number of parameters, p, equals 3, the design size, N, need not exceed 7. Pazman (1987) has shown that N≤1/2 p (p+1)+1.
Also, by the algorithm of Onukogu and Iwundu (2007) the design points, {(1,1), (1,-1), (-1,1), (-1,-1), (1.414,0), (-1.414,0), (0,1.414), (0,-1.414), (0,0)}, that make up the design region, are arranged into H=3 groups according to their distances from the center of the design region. The group formation yields the following three groups with the associated design points:
| • | g1: {(1, 1), (1, -1), (-1, 1), (-1, -1)} |
| • | g2: {(1.414, 0), (-1.414, 0), (0, 1.414), (0, -1.414)} |
| • | g3: {(0, 0)} |
With the initial tuple, {3:1:1}, it is required to select 3 support points from g1, 1 support point from g2 and 1 support point from g3. Since, there are four design points in g1 the following design points are admissible:
| • | g11: {(1, 1), (1, -1), (-1, 1)} |
| • | g12: {(1, 1), (1, -1), (-1, -1)} |
| • | g13: {(1, -1), (-1, 1), (-1, -1)} |
| • | g14: {(1, 1), (-1, 1), (-1, -1)} |
| Fig. 1: |
Geometric region supported by points
of Circumscribed Central Composite Design |
Also since there are four design points in g2 the following designs points are admissible:
| • | g21: {(1.414, 0)} |
| • | g22: {(0, -1.414)} |
| • | g23: {(-1.414, 0)} |
| • | g24: {((0, 1.414)} |
For g3, since there is only one design points, the admissible design point is:
| • | g31: {(0, 0)} |
From the admissible design points the following sets of sub-designs are formed:
ξ21 = (1.414, 0), ξ22 = (0,
-1.414),
ξ23 = (-1.414, 0), ξ24 = (0, 1.414)
ξ31 = (0, 0)
where, a1 = 4, a2 = 4 and a3 = 1. Since, the restriction is not satisfied the groups are repositioned within the class of interest as {1: 3: 1}, where we select 1 support point from g3, select 3 support points from g1 and 1 support point from g2. The sub-designs are rearranged as:
ξ31 = (0, 0)
ξ21 = (1.414, 0), ξ22 = (0,
-1.414),
ξ23 = (-1.414, 0), ξ24 = (0, 1.414)
Thus, it has a3≤a1≤a2.
Arranging the sub-designs as composite designs, the following set of designs were formed:
| • | Set 1: |
| • | Set 2: |
| • | Set 3: |
| • | Set 4: |
Determinant evaluations of the information matrices of the designs in set 1 yield respectively:
| • | M {ξ(11)} = 0.3415 |
| • | M {ξ(13)} = 0.5224 |
| • | M {ξ(14)} = 0.5224 |
| Table 1: | Combinatorics for a 3, 4, 5, 6 and 7-point D-optimal exact design |
Determinant evaluations of the information matrices of the designs in set 2 yield respectively:
| • | M {ξ(21)} = 0.5224 |
| • | M {ξ(22)} = 0.5224 |
| • | M {ξ(23)} = 0.3415 |
| • | M {ξ(24)} = 0.3415 |
Determinant evaluations of the information matrices of the designs in set 3 yield respectively:
| • | M {ξ(31)}= 0.3415 |
| • | M {ξ(32)}= 0.5224 |
| • | M {ξ(33)}= 0.3415 |
| • | M {ξ(34)}= 0.5224 |
Determinant evaluations of the information matrices of the designs in set 4 yield respectively:
| • | M {ξ(41)} = 0.5224 |
| • | M {ξ(42)} = 0.3415 |
| • | M {ξ(43)} = 0.5224 |
| • | M {ξ(44)} = 0.3415 |
It is remarked that the determinant values need not to be identical for designs in the set. However, notice that in each ith set (i = 1, 2, 3, 4), there is an N-point equivalent design with same maximum determinant value. Irrespective of the set chosen, we are certain to locate the best design. By assessing any ith set, we successfully do a 25% search at the combination {3:1:1}. The rest of the task is as elaborated by Iwundu and Otaru (2014).
For this model, we shall constuct N-point D-optimal exact design; N = 3, 4,..., 7.
For N = 3, the initial tuple of support points is [3: 0: 0]. With this, we commence the search for the D-optimal exact design. The sequential steps are presented in Table 1.
| Table 2: | Some distinguishing features of the algorithm for the illustrations |
The maximum determinant value is det* = 5.926x10-1 and it is associated with design class [3:0:0] having the design points [(-11, 1-1, 11) or (-11, 11, -1-1) or (-11, 1-1, -1-1) or (1-1, 11, -1-1)]. Within the class [3:0:0], the number of D-optimal exact designs is 4.
For N = 4, the initial tuple of support points is [3:1:0]. With this, we commence the search for the D-optimal exact design. The sequential steps are presented in Table 1.
The maximum determinant value is det* = 1.000 and it is associated with design class [4:0:0] having the design points [(-11, 1-1, 11,-1-1)]. Within the class [3:1:0], the number of D-optimal exact designs is 1.
For N = 5, the initial tuple of support points is [3:1:1]. With this, we commence the search for the D-optimal exact design. The sequential steps are presented in Table 1. The maximum determinant value is det* = 8.960x10-1 and it is associated with design class [5:0:0] having the design points [(-11, 1-1, 11,-1-1, -11) or (-11, 1-1, 11, -1-1, 1-1) or (-11, 1-1, 11, -1-1, 11) or (-11, 1-1, 11, -1-1,-1-), ]. Within the class [3:1:1], the number of D-optimal exact designs is 4.
For N = 6, the initial tuple of support points is [3:2: 1]. With this, we commence the search for the D-optimal exact design. The sequential steps are presented in Table 1.
The maximum determinant value is det* = 8.889x10-1 and it is associated with design class [6:0: 0] having the design points [(-11, 1-1, 11, -1-1, -11, 1-1) or (-11, 1-1, 11, -1-1, -11, 11) or (-11, 1-1, 11, -1-1, -11, -1-1) or (-11, 1-1, 11, 1-1, 11) or (-11, 1-1, -11-1-1, 1-1, -1-1) or (-11, 1-1, 11, -1-1, 11, -1-1)].
Within the class [3:2:1], the number of D-optimal exact designs is 4.
For N = 7, the initial tuple of support points is [3:3: 1]. With this, we commence the search for the D-optimal exact design. The sequential steps are presented in Table 1.
The maximum determinant value is det* = 9.329x10-1 and it is associated with design class [7 0 0] having the design points [(-11, 1-1, 11, -1-1, -11, 1-1, 11) or (-11, 1-1, 11, -1-1, -11, 11, -1-1) or (-11, 1-1, 11, -1-1, -11, 1-1, -1-1) or (-11, 1-1, 11, -1-1, 1-1, 11, 11, -1-1)].
Within the class [3:3:1], the number of D-optimal exact designs is 4.
DISCUSSION
One of the fundamental theorems of Onukogu and Iwundu
(2007) in constructing D-optimal exact designs is based on the assertion
that for the pxp information matrices M (ξ1) = (mijξ1)
and M (ξ2) = (mijξ2) where, mii(ξ1)
= mii(ξ2), M (ξ1)≥M (ξ2)
if ||mij(ξ1)||≤2mij(ξ2)||;
I≠j., where,
Furthermore, the combinatorial algorithm of Onukogu and Iwundu (2007) uses arbitrary starting designs which in some cases are very far from the required optimal design as measured by the determinant value of information matrices. Neither the algorithm of Onukogu and Iwundu (2007) nor that of Iwundu and Chigbu (2012) provided information on the possible percentage reduction in the number of determinant evaluations.
The efficiency of the new algorithm is seen in its ability to significantly reduce the number of determinant evaluations. For instance, in constructing a 3-point D-optimal design for the 3-parameter bivariate model, a 100% search requires 93 determinant evaluations. However, using the new algorithm reduces the determinant evaluations to a maximum of 16. Similarly, for N = 4, 5, 6 and 7, the number of available designs for a 100% search are, respectively, 163, 227, 298 and 411. The number of determinant evaluations is drastically reduced to a maximum of 6, 28, 43 and 40, respectively, using the new algorithm. Thus the new algorithm provides computational ease as the number of determinant evaluations needed to reach the required optimal design is significantly reduced.
For the 3-parameter bivariate model, Table 2 summarizes the number of designs within the design classes to be investigated, the maximun number of designs for which determinant evaluations are required, the relative percentage of maximun number of designs for which determinant evaluations are required, the minimum percentage of designs to be eliminated, the optimal design combination and the D-optimum.
CONCLUSION
The use of optimal designs allows model parameters to be estimated without bias and with minimum variance. These designs are suitable for models with qualitative as well as quantitative factors and require few experimental runs to estimate the parameters. The D-optimal designs are often used when classical designs, such as factorial and fractional factorials are not adequate and are also suitable even for irregular design regions. The construction of D-optimal designs is often iterative and requires a number of determinant evaluations. The algorithm presented in this study converges very rapidly to the desired N-Point D-optimal exact design. The procedure requires not more than 25% search on the total available designs within a design class.
In searching for D-optimal exact design, the algorithm eliminates not less than 80% of the total available designs some of which are very inferior to the optimal design. Once a direction of increasing determinant has emerged, the algorithm continues in that direction and a quick convergence of the procedure to the require optimum is certain.