SIMPLEX(1) SIMPLEX-1991 SIMPLEX(1) NNAAMMEE simplex-1991, simplex, simpfit - Nelder-Mead simplex minimization for parameter estimates with standard deviations SSYYNNOOPPSSIISS xxxxxxxxffiitt [ --ss {a | c | l | n} ] [ --dd {a | c | l | n} ] [ [ --ii ] input- file ] [ [ --oo ] diskfile ] DDEESSCCRRIIPPTTIIOONN SSiimmppffiitt minimizes a function by adjusting the variable parameters according to the value returned by a user-coded subroutine. There are no restrictions on the form of the function, except that a value must be computable given the input parameters. Derivatives are not calcu- lated. Singularities can be tolerated. Bounds tests can be incorpo- rated simply. The Nelder-Mead (1965) algorithm is a procedure for systematically shrinking or otherwise adjusting the shape of a polygon, the simplex. The simplex is constructed in parameter space, with vertices that are arbitrary except they describe a volume that includes the minimum point. Shrinking is carried out so that the function minimum remains within the simplex. Shrinking is continued until the vertices are so close together, satisfying an exit test, that the mean of the vertices defines with sufficient accuracy the parameter values of the function minimum. Sometimes the procedure can locate the minimum even if the starting simplex does not include it. If the function surface is suf- ficiently rough, the procedure fails through being trapped within a local minimum. The Nelder-Mead method appears to be more robust than gradient methods, but slower to converge when close to the minimum. Standard deviations of the parameters are calculated by fitting a quadratic to the function surface at the minimum and then using the properties of the quadratic to calculate the variance-covariance matrix. The strategy is given by Nelder and Mead. The quadratic approximation at the current simplex minimum can be used to define a better estimate of the minimum and to construct a new simplex based upon it. Alternation between iterations of simplex shrinking and quadratic approximation can lead to faster approach to the best esti- mate of the minimum. The Nelder-Mead algorithm can be used to fit a non-linear model to data. In this case, the function minimized is the least-squares test for quality of fit, the weighted sum of squares of the residuals. A model function explicitly relating a dependent variable to one or more independent variables and variable parameters is fit to a set of data points (observed values of dependent and independent variables). The simplex search locates the least squares minimum, giving estimates of the best-fit values of the parameters of the model function. Standard deviations of the parameters are estimated by quadratic approximation of the least squares surface near the minimum. CCOODDIINNGG Several routines have to be recoded for each new model function. Gen- erally only a few lines have to be rewritten, given a working template file (see Section FFIILLEESS, _l_i_n_e_f_i_t_._c or _l_d_h_f_i_t_._c). (1) ffuunncc(()) calculates for a simplex vertex (for the set of parameter values passed to it): (a) the value of the dependent variable for each data point and (b) the least squares function (the weighted sum of residuals squared) over all data points. Bounds on parameters can be implemented easily, by a test that on violation returns an excessively large least squares function value (e.g., 1.E38). Code should be efficient; most of the minimiza- tion is spent in ffuunncc(()).. (2) ffddaattpprriinntt(()) prints calculated and input values for the set of data points, may have to be recoded after change in the function or data. ffddaattpprriinntt(()) can be structured to call other functions,e.g., ffppooiinnttpprriinntt(()), to print additional customizable data- related output. (3) ffssppeecciiaall(()) controls a customizable and optional display printed after the standard display at the end of each iteration of the simplex minimization. The minimizer knows nothing about the data, except that it should read data in if told to, call ffuunncc(()) to give the test value (least-squares function) needed by the fitting procedure, and call ffddaattpprriinntt(()) or ffssppeecciiaall(()) to display results, when appropriate. You are on your own in designing these functions, beyond keeping the interface shown in the examples (templates). CCOOMMMMAANNDD LLIINNEE OOPPTTIIOONNSS --ss {a | c | l | n} -- control output to terminal; default is all pos- sible output ( aa ): aa = ALL possible output; information tracking each iteration of the simplex minimization is displayed. cc = summary output each CYCLE of perhaps 30 iterations; any output from a quadratic minimization is displayed at this point. ll = summary output on LAST cycle only; nn = NO output; --dd {a | c | l | n} -- control output to _d_i_s_k_f_i_l_e_, with options as for control of terminal output; default is summary output ( cc ): [ --ii ] _i_n_p_u_t_f_i_l_e -- specify input file; default is stdin. [ --oo ] _d_i_s_k_f_i_l_e -- specify output file; default is /dev/null, i.e., no output is saved unless requested. IINNPPUUTT AANNDD OOUUTTPPUUTT The input file has the following structure: one-line title, with no tabs or ctrl characters; lines following give control variables, the starting simplex, optionally lower and upper bounds on the parameters, and the data array; the order of entry is fixed by the order in rreeaadd__ddaattaa(());; see sam- ple data file for structure, and also the description in _i_n_p_u_t_._t_x_t_; the one-word descriptors must be present in the data file; the data format is otherwise free-form; comments at the end of the file are not read by the program Output is meant to be self-documenting. For details, please consult the documentation file _O_u_t_p_u_t_._t_x_t (see following), the source code, and the Nelder and Mead (1965) publication ( _n_e_l_d_e_r_-_m_e_a_d_-_p_a_p_e_r_._p_d_f; see following). FFIILLEESS _S_i_m_p_l_e_x_-_1_9_9_1_/_L_i_n_e_/_l_i_n_e_f_i_t_._c _S_i_m_p_l_e_x_-_1_9_9_1_/_L_d_h_/_l_d_h_f_i_t_._c Examples of coding for specific functions: _l_d_h_f_i_t_._c fits enzyme kinetic data for lactate dehydrogenase with an ordered ternary complex mechanism with abortive ternary complexes; _l_i_n_e_f_i_t_._c fits a set of manufactured data points with a straight line, for which comparison can be made to hand calculations of the best-fit parameters and standard deviations. _S_i_m_p_l_e_x_-_1_9_9_1_/_L_i_n_e_/_l_i_n_e_f_i_t_._d_a_t _S_i_m_p_l_e_x_-_1_9_9_1_/_L_d_h_/_l_d_h_f_i_t_._d_a_t Sample input files, with typical values of the control variables. There are several documentation files: _S_i_m_p_l_e_x_-_1_9_9_1_/_D_o_c_/_S_i_m_p_l_e_x_._t_x_t Description of the Nelder-Mead algorithm and of the quadratic fit. _S_i_m_p_l_e_x_-_1_9_9_1_/_D_o_c_/_O_u_t_p_u_t_._t_x_t Description of the full ( aa option) output for the minimization. _S_i_m_p_l_e_x_-_1_9_9_1_/_D_o_c_/_I_n_p_u_t_._t_x_t Template input file, showing the style of data entry, with com- ments. _S_i_m_p_l_e_x_-_1_9_9_1_/_D_o_c_/_D_a_t_a___r_e_d_n_._t_x_t Comments on data reduction and a description of the model coded in _l_d_h_f_i_t_._c_, for the lactate dehydrogenase reaction mechanism. _n_e_l_d_e_r_-_m_e_a_d_-_p_a_p_e_r_._p_d_f The classic Nelder-Mead paper describing the simplex algorithm used here for the fitting and the quadratic approximation for the region near the least-squares minimum. _S_i_m_p_l_e_x_-_1_9_9_1_/_L_i_b Directory - sources for the simplex fit library. _S_i_m_p_l_e_x_-_1_9_9_1_/_L_d_h Directory - sources, executable, and test files for llddhhffiitt.. _S_i_m_p_l_e_x_-_1_9_9_1_/_L_i_n_e Directory - sources, executable, and test files for lliinneeffiitt.. RREEFFEERREENNCCEE:: A simplex method for function minimization. J.A. Nelder and R. Mead (1965). _C_o_m_p_u_t_e_r J. 7, 308. AAUUTTHHOORR J. A. Rupley, Tucson, Arizona rupley!local@megaron.arizona.edu BBUUGGSS There are limits, set in _s_i_m_p_d_e_f_s_._h_, on the number of parameters, data points, and variables for each data point. SIMPLEX-1991 SIMPLEX(1)