SIMPLEX(1)                       SIMPLEX-1991                       SIMPLEX(1)



NNAAMMEE
       simplex-1991,  simplex,  simpfit - Nelder-Mead simplex minimization for
       parameter estimates with standard deviations

SSYYNNOOPPSSIISS
       xxxxxxxxffiitt [ --ss {a | c | l | n} ] [ --dd {a | c | l | n} ] [ [ --ii  ]  input-
       file ] [ [ --oo ] diskfile ]

DDEESSCCRRIIPPTTIIOONN
       SSiimmppffiitt  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.

   CCOODDIINNGG
       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 FFIILLEESS, _l_i_n_e_f_i_t_._c or _l_d_h_f_i_t_._c).  (1) ffuunncc(()) 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 ffuunncc(())..  (2) ffddaattpprriinntt(()) prints calculated  and  input
       values  for the set of data points, may have to be recoded after change
       in the function or data.  ffddaattpprriinntt(()) can be structured to  call  other
       functions,e.g.,  ffppooiinnttpprriinntt(()),  to print additional customizable data-
       related output.  (3) ffssppeecciiaall(()) 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 ffuunncc(()) to give the test value (least-squares
       function) needed by the fitting  procedure,  and  call  ffddaattpprriinntt(())  or
       ffssppeecciiaall(())  to  display results, when appropriate.  You are on your own
       in designing these functions, beyond keeping the interface shown in the
       examples (templates).

   CCOOMMMMAANNDD LLIINNEE OOPPTTIIOONNSS
       --ss {a | c | l | n}  --  control output to terminal; default is all pos-
       sible output ( aa ):

            aa = ALL possible output; information tracking  each  iteration  of
            the simplex minimization is displayed.

            cc = summary output each CYCLE of perhaps 30 iterations; any output
            from a quadratic minimization is displayed at this point.

            ll = summary output on LAST cycle only;

            nn = NO output;

       --dd {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 ( cc ):

       [ --ii ] _i_n_p_u_t_f_i_l_e --  specify input file; default is stdin.

       [ --oo ] _d_i_s_k_f_i_l_e --  specify output file; default is /dev/null, i.e., no
       output is saved unless requested.

   IINNPPUUTT AANNDD OOUUTTPPUUTT
       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 rreeaadd__ddaattaa(());; 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).

FFIILLEESS
       _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 ( aa 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 llddhhffiitt..
       _S_i_m_p_l_e_x_-_1_9_9_1_/_L_i_n_e
            Directory - sources, executable, and test files for lliinneeffiitt..

RREEFFEERREENNCCEE::
       A simplex method for function minimization.
       J.A. Nelder and R. Mead (1965). _C_o_m_p_u_t_e_r J. 7, 308.

AAUUTTHHOORR
       J. A. Rupley, Tucson, Arizona
       rupley!local@megaron.arizona.edu

BBUUGGSS
       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)
