Search Methods :: SAS/QC(R) 12.1 User's Guide

Search Methods

The search procedures available in the OPTEX procedure offer various compromises between speed and reliability in finding the optimum. In general, the longer an algorithm takes to arrive at an answer, the more efficient is the resulting design, although this is not invariably true. The right search procedure for any specific case depends on the size of the problem, the relative importance of using the best possible design as opposed to a very good one, and the computing resources available.

Useful Matrix Formulas

All of the search algorithms are based on adding candidate points to a design and deleting them from this design. If $V=(X’X)^{-1}$ is the inverse of the information matrix for the design at any stage, then the change in V that results from adding a point $\mb {x}$ to a design (which adds a new row $\mb {x}$ to the design matrix) is

$\displaystyle V$

$\displaystyle \rightarrow$

$\displaystyle V - \frac{V\Strong{x}\Strong{x}V}{1 + \Strong{x}V\Strong{x}}$

and the change in V that results from deleting the point $\mb {y}$ from this design is

$\displaystyle V$

$\displaystyle \rightarrow$

$\displaystyle V + \frac{V\Strong{y}\Strong{y}V}{1 - \Strong{y}V\Strong{y}}$

It follows that adding $\mb {x}$ multiplies the determinant of the information matrix by $1+\mb {x}’V\mb {x}$ . Likewise, deleting $\mb {y}$ multiplies the determinant by $1 - \mb {y}’V\mb {y}$ . For any point $\mb {z}$ , the quantity $\mb {z}’V\mb {z}$ is proportional to the prediction variance at the point $\mb {z}$ . Thus, the point $\mb {x}$ whose addition to the design maximizes the determinant of the information is the point whose prediction variance calculated from the present design is largest. The point whose deletion from the design costs the least in terms of the determinant is the point with the smallest prediction variance.

Similar rank-one update formulas can be derived for A-optimality, which is based on the trace of the inverse of the information matrix instead of its determinant. However, in this case there is no single quantity that can be examined for both adding and deleting a point. Here, the trace that results from adding a point $\mb {x}$ to a design depends on

$\displaystyle \frac{\Strong{x}V^2\Strong{x}}{1 + \Strong{x}V\Strong{x}}$

and the trace that results from deleting a point $\mb {y}$ to this design depends on

$\displaystyle \frac{\Strong{y}V^2\Strong{y}}{1 - \Strong{y}V\Strong{y}}$

This complication makes A-optimal designs harder to search for than D-optimal ones.

There are no useful rank-one update formulas for the distance-based design criteria.

Sequential Search Algorithm

The simplest and fastest algorithm is the sequential search due to Dykstra (1971), which starts with an empty design and adds successive candidate points so that the chosen criterion is optimized at each step. You can use the sequential procedure as a first step in finding a design

to judge the size of the problem in terms of time and space requirements
to determine the number of design points needed to estimate the parameters of the model

The sequential algorithm requires no initial design; in fact, it can be used to provide an initial design for the other search procedures (see the INITDESIGN= option ). If you specify a data set for an initial design for this search procedure, no search will be made; in this way, the OPTEX procedure can be used to evaluate an existing design.

Since the sequential search method involves no randomness, it requires only one try to find a design. The sequential procedure is by far the fastest of any of the search methods, but in difficult design situations it is also the least reliable in finding a globally optimal design. Also, the fact that it always finds the same design (due to the lack of randomness mentioned previously) makes it inappropriate when you want to find a design that represents a compromise between several optimality criteria.

Exchange Algorithm

The next fastest algorithm is the simple exchange method of Mitchell and Miller (1970). This technique tries to improve an initial design by adding a candidate point and then deleting one of the design points, stopping when the chosen criterion ceases to improve. This method is relatively fast (though typically much slower than the sequential search) and fairly reliable. METHOD=EXCHANGE is the default.

DETMAX Algorithm

The DETMAX algorithm of Mitchell (1974a) is the best-known and most widely used optimal design search algorithm. It generalizes the simple exchange method. Instead of requiring that each addition of a point be followed directly by a deletion, the algorithm provides for excursions in which the size of the design might vary between and . Here is the specified size of the design and k is the maximum allowed size for an excursion. By default k is 4, but you can change this (see the METHOD=DETMAX(level) option ). For the precise stopping rules for each excursion and for the entire search, refer to Mitchell (1974a). Due to the mentioned excursions, the DETMAX algorithm might not be a good choice when the design you want to construct is saturated or near-saturated.

Fedorov and Modified Fedorov Algorithms

The three algorithms discussed so far add and delete points one at a time. By contrast, the Fedorov and modified Fedorov algorithms are based on simultaneous switching—that is, adding and deleting points simultaneously. These two algorithms usually find a better design than the others, but because each step involves a search over all possible pairs of candidate and design points, they generally run much slower.

From the equations in “Useful Matrix Formulas” earlier in this chapter (see also Nguyen and Piepel (2005), Section 4) it follows that simultaneously adding a point x and deleting a point y multiplies the determinant of the information matrix by $1+\Delta (x, y)$ , where:

$\displaystyle \Delta (\Strong{x},\Strong{y})=\Strong{x}’\Strong{V}\Strong{x}-\Strong{y}’\Strong{V}\Strong{y}+(\Strong{x}’\Strong{V}\Strong{y})^2-(\Strong{x}’\Strong{V}\Strong{x})(\Strong{y}’{V}\Strong{y})$

The quantity $\Delta (\mb {x},\mb {y})$ is often referred to as Fedorov’s delta function.

At each step, the Fedorov algorithm (Fedorov 1972) seeks the pair $(\mb {x},\mb {y})$ of one candidate point and one design point that maximizes $\Delta (\mb {x},\mb {y})$ and then switches $\mb {x}$ for $\mb {y}$ in the design. Thus, after computing $\Delta (\mb {x},\mb {y})$ for all possible pairs of candidate and design points, the Fedorov algorithm performs only one switch.

The modified Fedorov algorithm of Cook and Nachtsheim (1980) computes the same number of $\Delta$ ’s on each step but switches each point $\mb {y}$ in the design with the candidate point $\mb {x}$ that maximizes $\Delta$ (x,y). This procedure is generally as reliable as the simple Fedorov algorithm in finding the optimal design, but it can be up to twice as fast.

Johnson and Nachtsheim (1983) introduce a generalization of both the simple exchange algorithm and the modified Fedorov search algorithm of Cook and Nachtsheim (1980), which is described later in this list. In the modified Fedorov algorithm, each of the points in the current design is considered for exchange with a candidate point; in the generalized version, only the k design points with smallest variance in the current design are considered for exchange. You can specify k-exchange as the search procedure for OPTEX by giving a value for k in parentheses after METHOD=EXCHANGE. When , the size of the design, k-exchange is equivalent to the modified Fedorov algorithm; when k = 1, it is equivalent to the simple exchange algorithm. Cook and Nachtsheim (1980) indicate that is typically sufficient.

For a detailed review of the preceding search methods, see Nguyen and Miller (1992).