Direct methods simplex search

Random Search / 6.1.2 Grid Search / 6.1.3 Univariate Search / 6.1.4 Simplex Search Method / 6.1.5 Conjugate Search Directions / 6.1.6 Summary... 

For the optimization of, for instance, a tablet formulation, two strategies are available a sequential or a simultaneous approach. The sequential approach consists of a series of measurements where each new measurement is performed after the response of the previous one is knovm. The new experiment is planned according to a direction in the search space that looks promising with respect to the quality criterion which has to be optimized. Such a strategy is also called a hill-climbing method. The Simplex method is a well known example of such a strategy. Textbooks are available that describe the Simplex methods [20]. 

There are two basic types of unconstrained optimization algorithms (1) those requiring function derivatives and (2) those that do not. Here we give only an overview and refer the reader to Sec. 3 or the references for more details. The nonderivative methods are of interest in optimization applications because these methods can be readily adapted to the case in which experiments are carried out directly on the process. In such cases, an actual process measurement (such as yield) can be the objective function, and no mathematical model for the process is required. Methods that do not require derivatives are called direct methods and include sequential simplex (Nelder-Meade) and Powells method. The sequential simplex method is quite satisfactory for optimization with two or three independent variables, is simple to understand, and is fairly easy to execute. Powell s method is more efficient than the simplex method and is based on the concept of conjugate search directions. This class of methods can be used in special cases but is not recommended for optimization involving more than 6 to 10 variables. 

Sometimes it is not necessary to determine a response surface model tor locate the optimum conditions. Hill-climbing by direct search methods, e.g. search along the path of steepest ascent [8] or sequential simplex search [9], will lead to a point on the response surface near the optimum. The computations involved in these methods are rather trivial and do not require a computer and will for this reason not be discussed further in this chapter. Readers who require details of these direct search methods should consult Refs. [1,8,9]. 

If xi and X2 are varied one at a time, then the method is known as a univariate search and is the same as carrying out successive line searches. If the step length is determined so as to find the minimum with respect to the variable searched, then the calculation steps toward the optimum, as shown in Figure 1.15a. This method is simple to implement, but can be very slow to converge. Other direct methods include pattern searches such as the factorial designs used in statistical design of experiments (see, for example, Montgomery, 2001), the EVOP method (Box, 1957) and the sequential simplex method (Spendley et ah, 1962). 

Nonderivative methods include random search, grid search, simplex search, and conjugate directions (or Powell s method). The nonderivative methods use various patterns for generating new test points for decision variables, and then a comparison of the new objective function value against previous values. A subsequent test point is then generated, either based on the immediate comparison or using the previous history of test points. 

Basically two search procedures for non-linear parameter estimation applications apply. (Nash and Walker-Smith, 1987). The first of these is derived from Newton s gradient method and numerous improvements on this method have been developed. The second method uses direct search techniques, one of which, the Nelder-Mead search algorithm, is derived from a simplex-like approach. Many of these methods are part of important mathematical computer-based program packages (e.g., IMSL, BMDP, MATLAB) or are available through other important mathematical program packages (e.g., IMSL). 

In the simplex method, die number of initial experiments conducted is one more than the number of parameters (temperature, gradient rate, etc.) to be simultaneously optimized. The conditions of the initial experiments constitute the vertices of a geometric figure (simplex), which will subsequently move through the parameter space in search of the optimum. Once the initial simplex is established, the vertex with the lowest value is rejected, and is replaced by a new vertex found by reflecting the simplex in the direction away from the rejected vertex. The vertices of the new simplex are then evaluated as before, and in this way the simplex proceeds toward the optimum set of conditions. 

A more sophisticated method uses a random walk or simplex optimization search pattern, which was developed and is used to find downed aircraft or ships lost at sea. Variable limits are set, then three conditions within these limits are selected at random, injections are made, and chromatograms are run. The resolution sums for the injections are measured and calculated, the lowest value is discarded, and a new variable setting is selected directly opposite the discarded value and equidistant from the reject on a line connecting the two remaining values from the original triad (Fig. 14.3). 

The optimization can be carried out by several methods of linear and nonlinear regression. The mathematical methods must be chosen with criteria to fit the calculation of the applied objective functions. The most widely applied methods of nonlinear regression can be separated into two categories methods with or without using partial derivatives of the objective function to the model parameters. The most widely employed nonderivative methods are zero order, such as the methods of direct search and the Simplex (Himmelblau, 1972). The most widely used derivative methods are first order, such as the method of indirect search, Gauss-Seidel or Newton, gradient method, and the Marquardt method. 

Statistical optimization methods other than the Simplex algorithm have only occasionally been used in chromatography. Rafel [513] compared the Simplex method with an extended Hooke-Jeeves direct search method [514] and the Box-Wilson steepest ascent path [515] after an initial 23 full factorial design for the parameters methanol-water composition, temperature and flowrate in RPLC. Although they concluded that the Hooke-Jeeves method was superior for this particular case, the comparison is neither representative, nor conclusive. 

Various more-or-less efficient optimization strategies have been developed [46, 47] and can be classified into direct search methods and gradient methods. The direct search methods, like those of Powell [48], of Rosenbrock and Storey [49] and of Nelder and Mead ( Simplex ) [50] start from initial guesses and vary the parameter values individually or combined thereby searching for the direction to the minimum SSR. 

With all the necessary ingredients in place, the task is now to derive a reliable force field. In an automated refinement, the first step is to define in machine-readable form what constitutes a good force field. Following that, the parameters are varied, randomly or systematically (15,42). For each new parameter set, the entire data set is recalculated, to yield the quality of the new force field. The best force field so far is retained and used as the basis for new trial parameter sets. The task is a standard one in nonlinear numerical optimization many efficient procedures exist for selection of the optimum search direction (43). Only one recipe will be covered here, a combination of Newton-Raphson and Simplex methods that has been successfully employed in several recent parameterization efforts (11,19,20,28,44). 

The classic example of a direct search algorithm is the simplex method of Nelder and Mead (1965), who utilized a method originally devised by Spendley et al. (1962). In p-dimensional space, a simplex is a polyhedron of p + 1 equidistant points forming the vertices. For a two-dimensional problem, the simplex is an equilateral triangle. For three-dimensions, the simplex is a tetrahedron. This algorithm, which has no relation to... 

---