mxComputeNelderMead {OpenMx}R Documentation

Optimize parameters using a variation of the Nelder-Mead algorithm.

Description

OpenMx includes a flexible, options-rich implementation of the Nelder-Mead algorithm.

Usage

mxComputeNelderMead(
	freeSet=NA_character_, fitfunction="fitfunction", verbose=0L, 
	nudgeZeroStarts=mxOption(NULL,"Nudge zero starts"), 
	maxIter=NULL,	...,
	alpha=1, betao=0.5, betai=0.5, gamma=2, sigma=0.5, bignum=1e35, 
	iniSimplexType=c("regular","right","smartRight","random"),
	iniSimplexEdge=1, iniSimplexMat=NULL, greedyMinimize=FALSE, 
	altContraction=FALSE, degenLimit=0, stagnCtrl=c(-1L,-1L),
	validationRestart=TRUE,
	xTolProx=1e-8, fTolProx=1e-8,
	doPseudoHessian=FALSE,
	ineqConstraintMthd=c("soft","eqMthd"), 
	eqConstraintMthd=c("soft","backtrack","l1p"),
	backtrackCtrl=c(0.5,5))

Arguments

freeSet

Character-string names of MxMatrices containing free parameters.

fitfunction

Character-string name of the fitfunction; defaults to 'fitfunction'.

verbose

Integer level of reporting printed to terminal at runtime; defaults to 0.

nudgeZeroStarts

Should free parameters with start values of zero be "nudged" to 0.1 at runtime? Defaults to the current global value of mxOption "Nudge zero starts". May be a logical value, or one of character strings "Yes" or "No".

maxIter

Integer maximum number of iterations. Value of NULL is accepted, in which case the value used at runtime will be 10 times the number of iterations specified by the effective value of mxOption "Major iterations".

...

Not used. Forces remaining arguments to be specified by name.

alpha

Numeric reflection coefficient. Must be positive. Defaults to 1.0.

betao, betai

Numeric outside- and inside-contraction coefficients, respectively. Both must be within unit interval (0,1). Both default to 0.5.

gamma

Numeric expansion coefficient. If positive, must be greater than alpha. If non-positive, expansion transformations will not be carried out. Defaults to 2.0.

sigma

Numeric shrink coefficient. Cannot exceed 1.0. If non-positive, shrink coefficients will not be carried out, and failed contractions will instead be followed by a simplex restart. Defaults to 0.5.

bignum

Numeric value with which the fitfunction value is to be replaced if the fit is non-finite or is evaluated at infeasible parameter values. Defaults to 1e35.

iniSimplexType

Character string naming the method by which to construct the initial simplex from the free-parameter start values. Defaults to "regular".

iniSimplexEdge

Numeric edge-length of the initial simplex. Defaults to 1.0.

iniSimplexMat

Optional numeric matrix providing the vertices of the initial simplex. The matrix must have as many columns as there are free parameters in the MxModel. The matrix's number of rows must be no less than the number of free parameters minus the number of degrees-of-freedom gained from equality MxConstraints, if any. If a non-NULL value is provided, argument iniSimplexEdge is ignored, and argument iniSimplexType is only used in the case of a restart.

greedyMinimize

Logical; should the optimizer use "greedy minimization?" Defaults to FALSE. See below for details.

altContraction

Logical; should the optimizer use an "alternate contraction" transformation? Defaults to FALSE. See below for details.

degenLimit

Numeric "degeneracy limit;" defaults to 0. If positive, the simplex will be restarted if the measure of the angle between any two of its edges is within 0 or pi by less than degenLimit.

stagnCtrl

"Stagnation control;" integer vector of length 2; defaults to c(-1L,-1L). See below for details.

validationRestart

Logical; defaults to TRUE.

xTolProx

Numeric "domain-convergence" criterion; defaults to 1e-8. See below for details.

fTolProx

Numeric "range-convergence" criterion; defaults to 1e-8. See below for details.

doPseudoHessian

Logical; defaults to FALSE.

ineqConstraintMthd

"Inequality constraint method;" character string. Defaults to "soft".

eqConstraintMthd

"Equality constraint method;" character string. Defaults to "soft".

backtrackCtrl

Numeric vector of length two. See below for details.

Details

The state of a Nelder-Mead optimization problem is represented by a simplex (polytope) of n+1 vertices in the space of the free parameters, where n is the number of free parameters minus the number of degrees-of-freedom gained from equality MxConstraints. An iteration of the algorithm first sorts the n+1 vertices by their corresponding fitfunction values (i.e., the values of the fitfunction when evaluated at each vertex), in ascending order (i.e., from "best" fit to "worst" fit). Then, the "subcentroid," which is the centroid of the "best" n vertices, is calculated. Then, the algorithm attempts to improve upon the worst fit by transforming the simplex; see Singer & Nelder (2009) for details.

Argument iniSimplexType dictates how the initial simplex will be constructed from the start values if argument iniSimplexMat is NULL, and how the simplex will be re-initialized in the case of a restart. In all four cases, the vector of start values constitutes the "starting vertex" of the inital simplex. If iniSimplexType="regular", the initial simplex is merely a regular simplex with edge length equal to iniSimplexEdge. A "right" simplex is constructed by incrementing each free parameter by iniSimplexEdge from its starting value; thus, all the edges that intersect at the starting vertex do so at right angles. A "smartRight" simplex is constructed similarly, except that each free parameter is both incremented and decremented by iniSimplexEdge, and of those two points the one with the smaller fitfunction value is retained as a vertex. A "random" simplex is constructed by randomly perturbing the start values, in a manner similar to the default for mxTryHard(), to generate the coordinates of the other vertices. The user is advised that bounds on the free parameters may keep the initial simplex from having the requested regularity or edge-length, and that iniSimplexType is at best a suggestion in the presence of equality MxConstraints.

Note that if argument iniSimplexMat has nonzero length, the actual start values of the MxModel's free parameters are not used as a vertex of the initial simplex (unless one of the rows of iniSimplexMat happens to contain those start values).

If the simplex is restarted, a new simplex is constructed per argument iniSimplexType, with edge length equal to the distance between the current best and second-best vertices, and with the current best vertex used as a starting vertex.

If greedyMinimize=FALSE, "greedy expansion" (Singer & Singer, 2004) is used: if the expansion point and reflection point both have smaller fitfunction values than the best vertex, the expansion point is accepted. If greedyMinimize=TRUE, "greedy minimization" (Singer & Singer, 2004) is used: if the expansion point and the reflection point both have smaller fitfunction values than the best vertex, the better of the two new points is accepted.

If argument altContraction=TRUE, the "modified contraction step" of Gill et al. (1982, Chapter 4) is used, and the candidate point is contracted toward the best vertex instead of toward the subcentroid.

If positive, the first element of argument stagnCtrl sets a threshold for the number of successive iterations in which the best vertex of the simplex does not change, after which the algorithm is said to be "stagnant" (in a sense similar to that of Kelley, 1999). To attempt to remedy the stagnation, the simplex is restarted. If positive, the second element of argument stagnCtrl sets threshold for the number of restarts conducted, beyond which stagnation no longer triggers a restart. The rationale for the second element is that when the optimizer is close to convergence, the best vertex may not change, but restarting may be counterproductive, and in any event requires many function evaluations.

If argument validationRestart=TRUE, then when the optimizer has successfully converged, it will restart the simplex and attempt to improve upon the tentative solution it already found. This validation restart (Gill et al., 1982, Chapter 4) always re-initializes the simplex as a regular simplex, with edge-length equal to the distance between the best and worst vertices of the tentative solution. Optimization proceeds until convergence to a solution with a better fit value, or 2n iterations have elapsed.

The Nelder-Mead optimizer is considered to have successfully converged if (1) the largest l-infinity norm of the vector-differences between the best vertex and the other vertices is less than argument xTolProx, or (2) if the largest absolute difference in fit value between the best vertex and the other vertices is less than fTolProx.

If argument doPseudoHessian=TRUE and there are no equality MxConstraints, OpenMx will attempt to calculate the "pseudo-Hessian" or "curvature" matrix as described in the appendix to Nelder & Mead (1965). If successful, this matrix will be stored in the 'output' slot of the post-run MxComputeNelderMead object. Although crude, its inverse can be used as an estimate of the repeated-sampling covariance matrix of the free parameters when the usual finite-differences Hessian is unreliable.

OpenMx's implementation of Nelder-Mead can handle nonlinear inequality MxConstraints reasonably well. Its default method for doing so, with argument ineqConstraintMthd="soft", imposes a "soft" feasibility constraint by assigning a fitfunction value of bignum to points that violate the constraints by more than mxOption 'Feasibility tolerance'. Alternately, with argument ineqConstraintMthd="eqMthd", inequality MxConstraints can be handled by the same method provided to argument eqConstraintMthd, whether or not equality MxConstraints are present.

OpenMx's implementation of Nelder-Mead respects equality MxConstraints, but as of this writing handles them rather poorly, unless all vertices of the initial simplex are feasible. Its default method for equalities is the same as that for inequalities, i.e. a "soft" feasibility constraint. If argument eqConstraintMthd="backtrack", then the optimizer attempts to backtrack from an infeasible point to a feasible point in a manner similar to that of Ghiasi et al. (2008), except that it used with all new points, and not just those encountered via reflection, expansion and contraction. In this case, the displacement from the prior point to the candidate point is reduced by the proportion provided as the first element of argument backtrackCtrl, and thus a new candidate point is considered. This process is repeated until feasibility of the candidate point is restored, or the number of attempts exceeds the second element of argument backtrackCtrl. If argument eqConstraintMthd="l1p", Nelder-Mead is used as part of an l_1-penalty algorithm, which as of this writing is experimental and subject to change in future releases of OpenMx.

Value

Returns an object of class 'MxComputeNelderMead'.

References

Ghiasi, H., Pasini, D., & Lessard, L. (2008). Constrained globalized Nelder-Mead method for simultaneous structural and manufacturing optimization of a composite bracket. Journal of Composite Materials, 42(7), p. 717-736. doi: 10.1177/0021998307088592

Gill, P. E., Murray, W., & Wright, M. H. (1982). Practical Optimization. Bingley, UK: Emerald Group Publishing Ltd.

Kelley, C. T. (1999). Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition. SIAM Journal of Optimization 10(1), p. 43-55.

Nelder, J. A., & Mead, R. (1965) . A simplex method for function minimization. The Computer Journal, 7, p. 308-313.

Singer, S., & Nelder, J. (2009). Nelder-Mead algorithm. Scholarpedia, 4(7):2928., revision #91557. http://www.scholarpedia.org/article/Nelder-Mead_algorithm .

Singer, S., & Singer, S. (2004). Efficient implementation of the Nelder-Mead search algorithm. Applied Numerical Analysis & Computational Mathematics Journal, 1(2), p. 524-534. doi: 10.1002/anac.200410015

Examples

foo <- mxComputeNelderMead()
str(foo)

[Package OpenMx version 2.7.9 Index]