Simplex optimization methods

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. 

Morita et al. [69] optimized the mobile phase composition using the PRISMA model for rapid and economic determination of synthetic red pigments in cosmetics and medicines. The PRISMA model has been effective in combination with a super modihed simplex method for fadhtating optimization of the mobile phase in high performance thin layer chromatography (HPTLC). 

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. 

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. 

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

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. 

Because this proceeding is relatively expensive, an effective semi-quantitative method is widely used in optimization, the sequential simplex optimization. Simplex optimization is done without estimation of gradients and setting step widths. Instead of this, the progress of the optimization... 

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. 

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. 

If you allow the simplex method to continue, it finds the improved solution shown in Figure 7.7, with a cost of 3200, which is optimal (all reduced costs are nonnegative). It recognizes that it can save 20 by shifting ten Dallas units from S. Carolina to Tennessee, if it frees up ten units of supply at Tennessee by supplying Chicago from Arizona (which costs only 10 more). Supplies at Arizona and Tennessee are completely used, but South Carolina has ten units of excess supply. 

This transportation problem is an example of an important class of LPs called network flow problems Find a set of values for the flow of a single commodity on the arcs of a graph (or network) that satisfies both flow conservation constraints at each node (i.e., flow in equals flow out) and upper and lower limits on each flow, and maximize or minimize a linear objective (say, total cost). There are specified supplies of the commodity at some nodes and demands at others. Such problems have the important special property that, if all supplies, demands, and flow bounds are integers, then an optimal solution exists in which all flows are integers. In addition, special versions of the simplex method have been developed to solve network flow problems with hundreds of thousands of nodes and arcs very quickly, at least ten times faster than a general LP of comparable size. See Glover et al. (1992) for further information. 

Chapter 1 presents some examples of the constraints that occur in optimization problems. Constraints are classified as being inequality constraints or equality constraints, and as linear or nonlinear. Chapter 7 described the simplex method for solving problems with linear objective functions subject to linear constraints. This chapter treats more difficult problems involving minimization (or maximization) of a nonlinear objective function subject to linear or nonlinear constraints ... 

The separation of synthetic red pigments has been optimized for HPTLC separation. The structures of the pigments are listed in Table 3.1. Separations were carried out on silica HPTLC plates in presaturated chambers. Three initial mobile-phase systems were applied for the optimization A = n-butanol-formic acid (100+1) B = ethyl acetate C = THF-water (9+1). The optimal ratios of mobile phases were 5.0 A, 5.0 B and 9.0 for the prisma model and 5.0 A, 7.2 B and 10.3 C for the simplex model. The parameters of equations describing the linear and nonlinear dependence of the retention on the composition of the mobile phase are compiled in Table 3.2. It was concluded from the results that both the prisma model and the simplex method are suitable for the optimization of the separation of these red pigments. Multivariate regression analysis indicated that the components of the mobile phase interact with each other [79],... 

K. Morita, S. Koike and T. Aishima, Optimization of the mobile phase by the prisma and simplex methods for the HPTLC of synthetic red pigments. J. Planar Chromatogr.-Mod. TEC, 11 (1998) 94-99. 

There are methods that deliberately avoid the use of gradient and Hessian information. Such approaches typically require many more iterations but can nevertheless save overall on computation. Some popular ones are the Simplex Method, Genetic Algorithms, Simulated Annealing, Particle Swarm and Ant Colony Optimization, and variants thereof. 

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

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. 

Fig. 12. The progress of the modified Simplex method for optimization. From P. J. Golden and S. N. Deming, Laboratory Microcomputer, i, 44 (1984). Reproduced by permission of Science Technology Letters, England...

Already in 1955, Box mentioned that an evolutionary operation (EVOP) type method could be made automatic. Although the Simplex method has been critisized at many occasions, because it cannot handle situations with multiple optima or with excessive noise, its unique suitability for unattended and automatic optimization of analytical systems, explains the great effort by Chemometricians to make the method work. 

Tao BY. Optimization via the simplex method. Chem Eng 1988 95(2) 85. Lewis E. Gates, Jerry R. Morton, Phillip L. Fondy. Selecting agitator system to suspend solids in liquid. Chem Eng 1976 144-150. 

---