The Basic simplex method

To permit a more rapid convergence towards an optimum, several modified simplex methods have been suggested.[2] By these modified methods, the step-length of the next move is adjusted depending on the degree of improvement. If a new vertex should give a considerable improvement, it is rather natural to try to move further in that direction. One such modified simplex method is given in detail below, after a presentation of the basic simplex method. 

In the Basic simplex method, each vertex is at equal distance to other vertices, the simplex is regular. In two dimensions it is an equilateral triangle in three dimensions it is a regular tetrahedron. Each move will therefore have a fixed step-length due to this constraint. The method is defined by a set of rules ... 

J. Example Optimization of a Friedel-Crafts alkylation by the Basic simplex method... 

The method is described by a set of rules (as for the Basic simplex method). The principles are illustrated by a simplex in two variables. The formulae for computations are gereral and can be used for any number of variables. Vector notations are used to describe the method. It is assumed that a maximum response is desired. If a minimum is to be found, all relations greater than (>) and less than (<) should be reversed in the following rules. 

The Basic simplex method is good when the experimental domain is not too large. 

In the basic simplex method, the simplex thus can only be reflected to obtain the next experiment, and the simplex size remains the same throughout the procedure. In the modified simplex method, suggested by Nelder and Mead (100), the simplex can be reflected, expanded, or contracted to define the next experiment. Thus, in case the simplex is expanded or contracted, the simplex size changes. More information about the simplex procedures can be found in References 7,9,10, and 98-102. 

Optimization of Electrolyte Properties by Simplex Exemplified for Conductivity of Lithium Battery Electrolytes, Fig. 1 The basic simplex method is based on simple reflections (R) of the simplex (shown in the lower right). The optimization begins at starting simplex (Xi,Yi,ZilX2,Y2,Z2lX3,Y3,Z3), soUd line. A new set of... 

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. 

For readers with no prior knowledge of optimization methods In the textbook of Box et.al. [14] the basic principles of optimization are also explained. The sequential simplex method is presented in Walters et.al. [20]. Multi-criteria optimization is presented in Chapter 4 on an introductory level. For those readers who want to know more about multicriteria optimization, see the references given in Section 1.3.4 and Chapter 4. 

It will not always be possible to make expansion movements because as we move closer to the optimum we must reduce the size of the simplex in order to locate the optimum accurately. This basic idea of adapting the size of the simplex to each movement is the one that sustains the modified simplex method proposed by Nelder and Mead [17]. Figure 2.15 displays the four possibilities to modify the size of the simplex and Table 2.32 gives their respective expressions for each factor. 

In Figure 2.13, an example is given of the basic simplex procedure. Consider the imaginary response surface of a method, representing the response as a function of two factors (xi and X2) and shown as contour plot (dotted lines). Suppose the highest response value is considered to be the optimum. 

There exist several simplex methods. In this chapter, we will discuss three of them, in increasing order of complexity the basic simplex, the modified simplex and the super-modified simplex. The more sophisticated methods are able to adapt themselves better to the response surface studied. However, their construction requires a larger number of experiments. In spite of this, the modified and super-modified simplexes normally are able to come closer to the maximum (or minimum if this were of interest) with a total number of experiments that is smaller than would be necessary for the basic simplex. In this chapter, we will see examples with only two or three variables, so that we can graphically visualize the simplex evolution for instructive purposes. However, the efficiency of the simplex, in comparison with univariate optimization methods, increases with the number of factors. 

In the modified algorithm (Nelder and Mead, 1965), the simplex can change its size and form, and consequently adapt itself more efficiently to the response surface. This flexibility permits a more precise determination of the optimum point, because the simplex can shrink in its proximity. Besides this desirable characteristic, the modified method, compared to the basic simplex, can reduce the number of runs necessary to find the optimum, because it can stretch itself when it is far from the desired point, usually on a planar portion of the response surface. For this reason it approaches the experimental region of interest more rapidly. 

The basic simplex optimization method, first described by Spendley and co-workers in 1962 [ 11 ], is a sequential search technique that is based on the principle of stepwise movement toward the set goal with simultaneous change of several variables. Nelder and Mead [12] presented their modified simplex method, introducing the concepts of contraction and expansion, resulting in a variable size simplex which is more convenient for chromatography optimization. 

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... 

If dof(x) = n — act(x) = d > 0, then there are more problem variables than active constraints at x, so the (n-d) active constraints can be solved for n — d dependent or basic variables, each of which depends on the remaining d independent or nonbasic variables. Generalized reduced gradient (GRG) algorithms use the active constraints at a point to solve for an equal number of dependent or basic variables in terms of the remaining independent ones, as does the simplex method for LPs. 

In addition to the basic methods such as SIMPLEX, other key methods for value chain management are the response surface methodology (RSM) to find a global optimum in a multi-dimensional simulation result surface (Merkuryeva 2005) or simulated annealing applied in the chemical production to find optima e.g. for reaction temperatures (Faber et al. 2005). 

In 1983, Sasaki et al. obtained rough first approximations of the mid-infrared spectra of o-xylene, p-xylene and m-xylene from multi-component mixtures using entropy minimization [83-85] However, in order to do so, an a priori estimate of the number S of observable species present was again needed. The basic idea behind the approach was (i) the determination of the basis functions/eigenvectors V,xv associated with the data (three solutions were prepared) and (ii) the transformation of basis vectors into pure component spectral estimates by determining the elements of a transformation matrix TsXs- The simplex optimization method was used to optimize the nine elements of Tixi to achieve entropy minimization, and the normalized second derivative of the spectra was used as a measure of the probability distribution. 

After completing the first phase we have a feasible basic solution. The second phase is nothing else but the simplex method applied to the normal form. The following module strictly follows the algorithmic steps described. 

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 ... 

Step 3 to improve the response, the basic rule of the simplex method is reflect the rejected vertex (usually W) through the centroid (G) of the other f vertices (they are said to be retained ), obtaining the reflected vertex (R). Its experimental conditions are given by the following two expressions (apply them to each experimental factor) ... 

Let us analyze the previous case by taking into account the third factor X,. The outcomes of FUFE 23 and the results of application of method of steepest ascent are given in Table 2.216. Thirteen trials were necessary to reach the maximal yield of 85.2%. The outcomes of the simplex method are in Table 2.217. Maximal yield after 14 trials is 85.0%. Approximately the same number of trials has been necessary by both methods to reach the optimum. It should be stressed once again that FUFE requires replications, so that to reach optimum by the method of steepest ascent, we need at least twice as many trials. Evidently, a half-replica instead of FUFE in the basic experiment may reduce the number of trials. However, there is a possibility of wrong direction of the movement to optimum due to the possible effects of interactions. 

---