The Simplex Method

We will present the basics of the simplex method with the aid of a simulation and then describe the algorithm. As an example, Soylak et al. [18] optimised a procedure to preconcentrate lead (the studied response, Y) using a 2 factorial design in which the factors were  

RC the reagent concentration (mol 1 ) low level = 5x10 high level = 5 x 10 

Let us suppose that we are interested in implementing this procedure in our laboratory and we fix the time of agitation at 10 min. So, we want to look for the RC (Xi) and pH (X2) values that provide the largest percentage lead recovery (Y), and we will use the simplex method defined by Spendley etal [16]. 

If we call f the number of factors, a simplex is a convex and closed figure formed by/— 1 vertices in a space of/dimensions. This is a triangle for the case when we consider two factors (/= 2) or a tetrahedron if/= 3 for greater values of / the design cannot be drawn and we need to resort to matrix notation see Table 2.20. 

Initially, we establish the working intervals (boundaries) of each factor Xi, between 0 and 60 x 10 (mol 1 ) and X2, between 5.0 and 9.0. Then, we define 

In contrast to the simultaneous optimization procedures described in the previous section, the Simplex method is a sequential one. A minimum number of initial experiments is performed, and based on the outcome of these a decision is made on the location of a subsequent data point. This simplest form of a sequential optimization scheme can be characterized by the path 1012 in figure 5.4. 

The number of initial data points is one more than the number of parameters considered in the optimization process. These initial experiments define a geometrical figure in the parameter space which is called a Simplex. A two-dimensional Simplex is a triangle (often equilateral). A three-dimensional Simplex is a tetrahedron. The description of Simplexes in more dimensions is somewhat more difficult to envisage, but is mathematically straightforward. 

The initial experiments yield a set of chromatograms, each of which can be assigned a (criterion) value. Any of the criteria of chapter 4 that yields a single number for each chromatogram can be used. It will be assumed in the following that a criterion has been selected for which a maximum value needs to be obtained from the optimization procedure. 

The next step in the Simplex algorithm is to reject the lowest point, i.e. the chromatogram that yields the lowest response value, and the location of the next data point is found by reflecting the Simplex in the opposite direction. This process can then be repeated. 

Around the optimum, the situation will arise in which the reflection of the triangle results in a position at which a measurement has already been performed. This will be the case in the triangle MLN, in which N yields the lowest value. Instead of rejecting N and returning to measure K, the point with the second lowest response (L) is now rejected and the triangle is reflected towards point P. This procedure can be repeated until a measurement has been obtained at point R. Thereafter, no new measurements will be suggested from rejecting either the lowest or the second lowest response value and the optimization process comes to a halt. 

---

Let us consider the application of the simplex method to our quadratic function,/ = + 2y ... 

The relationship between output variables, called the response, and the input variables is called the response function and is associated with a response surface. When the precise mathematical model of the response surface is not known, it is still possible to use sequential procedures to optimize the system. One of the most popular algorithms for this purpose is the simplex method and its many variations (63,64). 

There are two basic types of unconstrained optimization algorithms (I) those reqmring function derivatives and (2) those that do not. 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 ac tual process measurement (such as yield) can be the objec tive function, and no mathematical model for the process is required. Methods that do not reqmre derivatives are called direc t methods and include sequential simplex (Nelder-Meade) and Powell s method. The sequential simplex method is quite satisfac tory 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. 

Ok) function is sought by repeatedly determining the direction of steepest descent (maximum change in for any change in the coefficients a,), and taking a step to establish a new vertex. A numerical example is found in Table 1.26. An example of how the simplex method is used in optimization work is given in Ref. 143. 

Cimpoiu et al. [72] made a comparative study of the use of the Simplex and PRISMA methods for optimization of the mobile phase used for the separation of a group of drugs (1,4-benzodiazepines). They showed that the optimum mobile phase compositions by using the two methods were very similar, and in the case of polar compounds the composition of the mobile phase could be modified more precisely with the Simplex method than with the PRISMA. 

Procedures used vary from trial-and-error methods to more sophisticated approaches including the window diagram, the simplex method, the PRISMA method, chemometric method, or computer-assisted methods. Many of these procedures were originally developed for HPLC and were apphed to TLC with appropriate changes in methodology. In the majority of the procedures, a set of solvents is selected as components of the mobile phase and one of the mentioned procedures is then used to optimize their relative proportions. Chemometric methods make possible to choose the minimum number of chromatographic systems needed to perform the best separation. 

It can be shown that this can be generalized to the case of more than two variables. The standard solution of a linear programming problem is then to define the comer points of the convex set and to select the one that yields the best value for the objective function. This is called the Simplex method. 

The standard (four-parameter logistic) curve was prepared by the simplex method using absorbance values collected from each participating laboratory. 

The Simplex algorithm and that of Powell s are examples of derivative-free methods (Edgar and Himmelblau, 1988 Seber and Wild, 1989, Powell, 1965). In this chapter only two algorithms will be presented (1) the LJ optimization procedure and (2) the simplex method. The well known golden section and Fibonacci methods for minimizing a function along a line will not be presented. Kowalik and Osborne (1968) and Press et al. (1992) among others discuss these methods in detail. 

The Sequential Simplex or simply Simplex method relies on geometry to create a heuristic rule for finding the minimum of a function. It is noted that the Simplex method of linear programming is a different method. 

In general, for a function of N variables the Simplex method proceeds as follows ... 

It is noted that Press et al. (1992) give a subroutine that implements the simplex method of Nelder and Mead. They also recommend to restart the minimization routine at a point where it claims to have found a minimum... 

Kumiawan noticed that the first vertex was the same in both optimizations. This was due to the fact that in both cases the worse vertex was the same. Kumiawan also noticed that the search for the optimal conditions was more effective when two responses were optimized. Finally, she noticed that for the Simplex method to perform well, the initial vertices should define extreme ranges of the factors. 

The techniques most widely used for optimization may be divided into two general categories one in which experimentation continues as the optimization study proceeds, and another in which the experimentation is completed before the optimization takes place. The first type is represented by evolutionary operations and the simplex method, and the second by the more classic mathematical and search methods. (Each of these is discussed in Sec. V.)... 

For pharmaceutical formulations, the simplex method was used by Shek et al. [10] to search for an optimum capsule formula. This report also describes the necessary techniques of reflection, expansion, and contraction for the appropriate geometric figures. The same laboratories applied this method to study a solubility problem involving butoconazole nitrate in a multicomponent system [11],... 

Bindschaedler and Gurny [12] published an adaptation of the simplex technique to a TI-59 calculator and applied it successfully to a direct compression tablet of acetaminophen (paracetamol). Janeczek [13] applied the approach to a liquid system (a pharmaceutical solution) and was able to optimize physical stability. In a later article, again related to analytical techniques, Deming points out that when complete knowledge of the response is not initially available, the simplex method is probably the most appropriate type [14]. Although not presented here, there are sets of rules for the selection of the sequential vertices in the procedure, and the reader planning to carry out this type of procedure should consult appropriate references. 

The root-mean-square error in the kinetic fit was an acceptable 2.83% and was minimized by the SIMPLEX method discussed elsewhere (8). An... 

The LP problems were solved by the simplex method. This algorithm solves a linear program by progressing from one extreme point of the feasible polyhedron to an adjacent one. 

Reflection to a new point in the simplex method. At point l,/(x) is greater than/at points 2 or 3. 

Nelder and Mead (1965) described a more efficient (but more complex) version of the simplex method that permitted the geometric figures to expand and contract continuously during the search. Their method minimized a function of n variables using (n + 1) vertices of a flexible polyhedron. Details of the method together with a computer code to execute the algorithm can be found in Avriel (1976). 

Progression to the vicinity of the optimum and oscillation around the optimum using the simplex method of search. The original vertices are x , x , and x . The next point (vertex) is Xq. Succeeding new vertices are numbered starting with 1 and continuing to 13 at which point a cycle starts to repeat. The size of the simplex is reduced to the triangle determined by points 7, 14, and 15, and then the procedure is continued (not shown). 

Carry out the four stages of the simplex method to minimize the function... 

Cite two circumstances in which the use of the simplex method of multivariate unconstrained optimization might be a better choice than a quasi-Newton method. 

Start at xT = [0 0]. Show all equations and intermediate calculations you use. For the simplex method, carry out only five stages of the minimization. 

The fact that the extremum of a linear program always occurs at a vertex of the feasible region is the single most important property of linear programs. It is true for any number of variables (i.e., more than two dimensions) and forms the basis for the simplex method for solving linear programs (not to be confused with the simplex method discussed in Section 6.1.4). 

In the following discussion we assume that, in the system of Equations (7.6)-(7.8), all lower bounds lj = 0, and all upper bounds Uj = +< >, that is, that the bounds become 0. This simplifies the exposition. The simplex method is readily extended to general bounds [see Dantzig (1998)]. Assume that the first m columns of the linear system (7.7) form a basis matrix B. Multiplying each column of (7.7) by B-1 yields a transformed (but equivalent) system in which the coefficients of the variables ( x,. . . , xm) are an identity matrix. Such a system is called canonical and has the form shown in Table 7.1. 

The simplex method is a two-phase procedure for finding an optimal solution to LP problems. Phase 1 finds an initial basic feasible solution if one exists or gives the information that one does not exist (in which case the constraints are inconsistent and the problem has no solution). Phase 2 uses this solution as a starting point and either (1) finds a minimizing solution or (2) yields the information that the minimum is unbounded (i.e., —oo). Both phases use the simplex algorithm described here. 

This solution reduces/from 28 to —8. The immediate objective is to see if it is optimal. This can be done if the system can be placed into feasible canonical form with x5, 3, —/ as basic variables. That is, 3 must replace xx as a basic variable. One reason that the simplex method is efficient is that this replacement can be accomplished by doing one pivot transformation. 

The simplex algorithm requires a basic feasible solution as a starting point. Such a starting point is not always easy to find and, in fact, none exists if the constraints are inconsistent. Phase 1 of the simplex method finds an initial basic feasible solution or yields the information that none exists. Phase 2 then proceeds from this starting... 

---