The Simplex Algorithm

The simplex algorithm is conceptually a very simple method. It is reasonably fast for small numbers of parameters, robust and reliable. For high dimensional tasks with many parameters, however, it quickly becomes painfully slow. Also, the simplex algorithm does not deliver any statistical information about the parameters, e.g. it is possible to fit parameters that are completely independent of the data. The algorithm delivers a value without indicating its uselessness. 

A simplex is a multidimensional geometrical object with n+1 vertices in an n dimensional space. In 2 dimensions the simplex is a triangle, in 3 dimensions it is a tetrahedron, etc. The simplex algorithm can be used for function minimisation as well as maximisation. We formulate the process for minimisation. At the beginning of the process, the functional values at all corners of the simplex have to be determined. Next the corner with the highest function value is determined. Then, this vertex is deleted and a new simplex is constructed by reflecting the old simplex at the face opposite the deleted comer. Importantly, only one new value has to be determined on the new simplex. The new simplex is treated in the same way the highest vertex is determined and the simplex reflected, etc. 

We do not design our own algorithm here but use the fin Insearch. m function supplied by Matlab. It is based on the original Nelder, Mead simplex algorithm. As an example, we re-analyse our exponential decay data Data Decay. m (see p. 106], this time fitting both parameters, the rate constant and the amplitude. Compare the results with those from the linearisation of the exponential curve, followed by a linear least-squares fit, as performed in Linearisation of Non-Linear Problems, (p.127). 

The arguments passed into fin insearch are the name of the function that delivers the function value for the parameters, initial guesses for the parameters to be fitted, an empty matrix (here specific minimisation arguments could be included, refer to the manual for more details), and the actual data t and y. fin insearch returns the optimal parameters. 

As the second example, we re-analyse the consecutive reaction A— Data ABC. m, where data were acquired at many wavelengths. 

---

Fig. 5.4 The three basic moves permitted to the simplex algorithm (reflection, and its close relation reflect-and-expmd contract in one dimension and contract around the lowest point). (Figure adapted from Press W H, B P Flannery,...

Fig. 5.5 The first few steps of the simplex algorithm with the function + 2i/. The initial simplex corresponds to the triangle 123. Point 2 has the largest value of the function and the next simplex is the triangle 134. The simplex for tire third step is 145.

The simplex algorithm, in a sense, prepares the problem before cal-... 

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 technique is useful where the problem is to decide the optimum utilisation of resources. Many oil companies use linear programming to determine the optimum schedule of products to be produced from the crude oils available. Algorithms have been developed for the efficient solution of linear programming problems and the SIMPLEX algorithm, Dantzig (1963), is the most commonly used. 

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. 

In initiating the simplex algorithm, we treat the objective function... 

If, at some iteration, the basic feasible solution is degenerate, the possibility exists that/can remain constant for some number of subsequent iterations. It is then possible for a given set of basic variables to be repeated. An endless loop is then set up, the optimum is never attained, and the simplex algorithm is said to have cycled. Examples of cycling have been constructed [see Dantzig (1998), Chapter 10]. 

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

Linear Programming (LP) for continuous variables based on the SIMPLEX algorithm... 

These models are nested the search starts with the simplest model and proceeds to the models of increasing degree of complexity (number of fitting parameters). An Ockham s razor principle is assumed here if more than one model is consistent with the data, the simplest model is preferred. For each model of motion, all parameters are determined from fitting, based on the simplex algorithm, to minimize the following target function ... 

First, and most general, is the case of an objective function that may or may not be smooth and may or may not allow for the computation of a gradient at every point. The nonlinear Simplex method [77] (not to be confused with the Simplex algorithm for linear programming) performs a pattern search on the basis of only function values, not derivatives. Because it makes little use ofthe objective function characteristics, it typically requires a great many iterations to find a solution that is even close to an optimum. 

The simplex algorithm (refs.7-8) is a way of organizing the above procedure much more efficiently. Starting with a feasible basic solution the procedure will move into another basic solution which is feasible, and the objective function will not decrease in any step. These advantages are due to the clever choice of the pivots. 

To describe one step of the simplex algorithm assume that the vectors present in the current basis are ,. .., a. Me need this indirect... 

SimSim performs a pressure match of measured and calculated reservoir or compartment pressures with an automatic, non-linear optimization technique, called the Nelder-Mead simplex algorithm3. During pressure matching SimSim s parameters (e.g. hydrocarbons in place, aquifer size and eigentime, etc.) are varied in a systematic manner according to the simplex algorithm to achieve pressure match. In mathematical terms the residuals sum of squares (least squares) between measured and calculated pressures is minimized. The parameters to be optimized can be freely selected by the user. 

Details on the simplex algorithm are available elsewhere (33,34,47-50). The advantages and disadvantages of the simplex method pertinent to chromatographic applications are summarized in Table II. 

General aspects of the simplex method. Although the simplex algorithm can in principle be employed for the optimization of any kind or number of parameters of a particular process, for chromatographic applications it appears to be better suited for certain types of a limited number of variables. 

The desire to restrict the number of variables when using the simplex algorithm introduces an interesting problem Of the variables listed in Table HI, how many should be included in the simplex procedure, and which ones Clearly, from our earlier discussion the variables in the second column of Table III can be excluded, but that still leaves 6 "ideal" parameters pressure (or density), temperature, modifier composition, and their respective gradients. How should one select from among these six parameters, since any of them may be important for a given sample ... 

Simplex Optimization Criteria. For chromatographic optimization, it is necessary to assign each chromatogram a numerical value, based on its quality, which can be used as a response for the simplex algorithm. Chromatographic response functions (CRFs), used for this purpose, have been the topics of many books and articles, and there are a wide variety of such CRFs available (33,34). The criteria employed by CRFs are typically functions of peak-valley ratio, fractional peak overlap, separation factor, or resolution. After an extensive (but not exhaustive) survey, we... 

Simplex Optimization Results. Of the 56 combinations of variables for use with the simplex in Table IV, only the 4 combinations highlighted with boxes have been utilized. Gearly the optimization of SFC separations via the simplex algorithm is still in its infancy, as are all other systematic methods of optimization for SFC. Nevertheless, as described below, the results provided by the simplex approach were quite good. The results of the 2 and 3-parameter simplexes are especially informative for the novice because their movement can be visualized in 3-dimensional space, in contrast to simplexes of four parameters and higher which cannot be depicted graphically. 

Future work. As mentioned earlier, use of the simplex algorithm for the systematic optimization of SFC separations is still in its early stages. The success already achieved, however, merits continued research along these lines. Research opportunities include (i) extension of the simplex method to less ideal variables and/or greater than 4 variables (ii) investigation of the benefits of the simplex method to packed columns and modified mobile phases and (iii) development of the capability to predict, for a given type of sample, the best combination of variables to optimize. 

---