Simplex method step size

A weakness with the standard mediod for simplex optimisation is a dependence on the initial step size, which is defined by the initial conditions. For example, in Figure 2.37 we set a very small step size for both variables this may be fine if we are sure we are near the optimum, but otherwise a bigger triangle would reach the optimum quicker, the problem being that the bigger step size may miss the optimum altogether. Another method is called the modified simplex algorithm and allows the step size to be altered, reduced as the optimum is reached, or increased when far from the optimum. 

When a point has been reached that is considered as optimal, the analyst can decide to stop the optimization, or try to fine-tune the method and to determine the real optimum more exactly. This can be done by starting in the provisional optimal point a new procedure with smaller simplexes (e.g. with step sizes that are 0.25 or 0.10 of the original ones). 

In the simplex procedures described above the step size was fixed. When the step size was taken too small it takes a large number of experiments to reach the optimum, and when it is taken too large the supposed optimum can be unacceptably far from the real one. To avoid this a so-called modified simplex method can be applied, in which the step size is variable throughout the procedure. The principles of the simplex method are maintained but rules for expansion or contraction of the simplexes are added. For a detailed description of these guidelines we refer to [27,831. 

A simplex is a convex geometric figure of k+1 non-planar vertices in k dimensional space, the number of dimensions corresponding to the number of independent factors. Thus, for two factors, it is a triangle, and for three factors, it is a tetrahedron. The method is sequential because the experiments are analyzed one by one as each is carried out. The basic method used a constant step size, allowing the region of experimentation to move at a constant rate toward the optimum. However, a modification that allows the simplex to expand and contract, proposed by Nelder and Mead in 1965, is more generally used. It has been reviewed recently by Waters. ... 

The Matlab Simulink Model was designed to represent the model stmctuie and mass balance equations for SSF and is shown in Fig. 6. Shaded boxes represent the reaction rates, which have been lumped into subsystems. To solve the system of ordinary differential equations (ODEs) and to estimate unknown parameters in the reaction rate equations, the inter ce parameter estimation was used. This program allows the user to decide which parameters to estimate and which type of ODE solver and optimization technique to use. The user imports observed data as it relates to the input, output, or state data of the SimuUnk model. With the imported data as reference, the user can select options for the ODE solver (fixed step/variable step, stiff/non-stiff, tolerance, step size) as well options for the optimization technique (nonlinear least squares/simplex, maximum number of iterations, and tolerance). With the selected solver and optimization method, the unknown independent, dependent, and/or initial state parameters in the model are determined within set ranges. For this study, nonlinear least squares regression was used with Matlab ode45, which is a Rimge-Kutta [3, 4] formula for non-stiff systems. The steps of nonlinear least squares regression are as follows ... 

A weakness with the standard method for simplex optimization is a dependence on the initial step-size. Another method is called the modified simplex algorithm and allows the step size to be altered, reduced as the optimum is reach, or increased far from the optimum. 

The resulting set of differential equations was solved numerically by means of an improved Euler method with variable step size control [9]. Parameter optimization was accomplished by a Mead Nelder simplex algorithm [10]. 

The sequential simplex method of optimization was proposed by Nelder and Mead. With a number of improvements and enhancements the simplex method has found great utility in real situations in analytical laboratory experiments and process control situations. The simplex method is a hill-climbing method that seeks to climb the response surface depending on the features of the response surface in its immediate neighborhood. Only one new experiment is done for each step in the optimization sequence, and the location of this new experiment on the response surface is completely determined by the previous few experiments. The method of Nelder and Mead using a variable-size simplex is the most commonly used. A complete description of how the simplex method works is beyond the scope of this review, since the information is contained elsewhere.Many applications of simplex optimization have appeared, and a few examples follow. 

The truly remarkable thing about the interior point method is that the number of iterations (Newton steps) is almost independent of problem size. For all models solved to date, the number of iterations has been less than 100, and is usually between 20 and 40. (Note, however, that one Newton step involves much more computation than one simplex step.) There are theoretictil and empirical reasons to believe that the number of iterations increases with the log of the number of variables, log( ). Indeed, Marsten et al. (1990) report a family of problems with from 35,000 to 2,000,000 variables for which a regression of iterations vs. log(n) gave an = 0.979. 

---