'STEPIT' is a Fortran II subroutine for finding local minima of almost any real function (called CHISQ) of several variables (called X(I)). The X(I) might, for example, be parameters appearing nonlinearly in an expression which is to be fitted to data by minimizing chi-square. Other uses include the solution of systems of transcendental equations by minimizing the sum of squares of the residuals, the solution of nearly redundant systems of linear equations, Hartree- Fock wave function calculations, fitting of bubble-chamber events, etc., i.e. any problem for which some measure of the poorness of a trial solution is a continuous and reasonably well behaved real function of parameters in the solution. See the reference by Hook and Jeeves below. STEPIT uses only function values (no derivatives).
The function to be minimized must be smooth. That is, it must be a continuous function defined on a continuous domain, and all of its first derivatives must be continuous. For example, the function ABSF(X(1))+ABSF(X(2)) (an inverted pyramid) is not admissible because its first derivatives are not continuous at the edges of the pyramid.
Author... J.P. Chandler I.U. Physics Dept. Bloomington, Ind. All criticisms and suggestions will be welcomed. Subroutine Stepit is a copyrighted program (Copyright 1965 J. P. Chandler).
Stepit is available from the Quantum Chemistry Exchange (QCPE), Dept. of Chemistry, Indiana University, Bloomington, Indiana and various social media firms. It may be used by anyone so long as they include an acknowledgement in any publication of work in which it is used. Another minimization program (mentioned below), well suited to problems with complicated constraints, is also available.
BIBLIOGRAPHY...
Direct Search Solution of Numerical and Statistical Problems, Robert Hook and T.A. Jeeves, J, Assoc. For Computing Machinery 8, 212.
Non-Linear Estimation, IBM Mathematics and Applications Dept., Program Manual MA-3.
A Simplex Method For Function Minimization, J.A. Nedler and R. Mead, The Computer Journal 7, 308.
Notes On Statistics For Physicists, Jay Orear, Lawrence Radiation Lab. Report UCRL-8417 (U. of California).
Analysis of Experiments in Particle Physics, Frank T. Solmitz, Annual Review of Nuclear Science 14, 375.
USAGE....
The call statement is CALL STEPIT(FUNK) FUNK may be any name of a function computation subroutine, of which there may be any number. An 'external card' is required in the program calling STEPIT for each subroutine.
All program linkage is via labelled common. The common statement follows....
COMMON/STEP/ NV,NTRACE,MATRIX,CHISQ,MASK(100),X(100),XMAX(100)
& XMIN(100),DELTAX(100),DELMIN(100),ERR(100,15)
CHISQ is the value of the function to be minimized. The calculation of
CHISQ is the sole purpose of the subroutine named in the call to Stepit.
NV is the number of variables, X(I). With this common statement NV may be as large as 100. To increase the maximum number of variables it is only necessary to change NVMAX (an internal parameter of Stepit) and the dimension and common statements, provided storage does not become a problem. (Instructions are given below for handling larger cases.)
Nonzero NTRACE causes a trace map of the minimization process to be printed. Initial and final values are printed in any case.
A nonzero mask(I) causes X(I) to be fixed.
X and DELTAX contain the initial values of the variables and the step sizes, and the DELMIN the step size cutoffs. parameters are roughly the same. Cutting of step size continues until all of the step sizes are less than the corresponding DELMIN(I), for those DELMIN which are nonzero. Note well that the DELMIN(I) do not, repeat *not*, give the accuracy of the final values of the X(I). The DELMIN(I) should be much smaller than the desired accuracy of minimization, and may all be set equal to zero if maximum accuracy is desired and if no parameter has its optimum value at exactly zero.
XMAX(I) and XMIN(I) are limits on X(I). Generally they should be used only for excluding regions in which the final function is complex, discontinuous, or otherwise uncomputable (and not merely unreasonable). Their use can prevent the location of minima even in the acceptable region, if the valley leaves but re-enters the region, because the function is by definition positive infinite outside the boundaries and this can introduce new minima. If limits are used and the final position of the minimum is against one of them, any errors calculated will probably be meaningless. If equal or reversed, XMAX and XMIN will be ignored.
All reference below to error calculation assumes that CHISQ actually is chi-square (or, in general, twice the negative of the natural log of the likelihood function). It is further assumed that the problem is heteroscedastic, that is, that the errors in the data points are known and are used in the calculation of the chi-square. It is assumed that users running homoscedastic problems (unknown errors, assumed equal) know how to scale the errors correctly. This scaling cannot be done in Stepit because the number of degrees of freedom is not available internally. For definitions of chi-square and the likelihood function, see the references by Orear or Solmitz.
also see:
Chandler, J.P. Subroutine STEPIT - Finds local minima of a smooth function of several parameters., Behavioral Science, 1969, 14, 81-82.