NonMonotone spectral approach for Solving LargeScale Nonlinear Systems of Equations
1 2 3 
fn 
a function that takes a real vector as argument and returns a real vector of same length (see details). 
par 
A real vector argument to 
method 
An integer (1, 2, or 3) specifying which BarzilaiBorwein steplength to use. The default is 2. See *Details*. 
control 
A list of control parameters. See *Details*. 
quiet 
A logical variable (TRUE/FALSE). If 
alertConvergence 
A logical variable. With the default 
... 
Additional arguments passed to 
The function sane
implements a nonmonotone spectral residual method
for finding a root of nonlinear systems. It stands for "spectral approach
for nonlinear equations".
It differs from the function dfsane
in that it requires an
approximation of a directional derivative at every iteration of the merit
function F(x)^t F(x).
R adaptation, with significant modifications, by Ravi Varadhan, Johns Hopkins University (March 25, 2008), from the original FORTRAN code of La Cruz and Raydan (2003).
A major modification in our R adaptation of the original FORTRAN code is the
availability of 3 different options for BarzilaiBorwein (BB) steplengths:
method = 1
is the BB
steplength used in LaCruz and Raydan (2003); method = 2
is equivalent to
the other steplength proposed in Barzilai and Borwein's (1988) original paper.
Finally, method = 3
, is a new steplength, which is equivalent to that
first proposed in Varadhan and Roland (2008) for accelerating the EM algorithm.
In fact, Varadhan and Roland (2008) considered 3 equivalent steplength schemes
in their EM acceleration work. Here, we have chosen method = 2
as the "default" method, as it generally performed better than the other
schemes in our numerical experiments.
Argument control
is a list specifing any changes to default values of
algorithm control parameters. Note that the names of these must be
specified completely. Partial matching will not work.
Argument control
has the following components:
A positive integer, typically between 520, that controls the
monotonicity of the algorithm. M=1
would enforce strict monotonicity
in the reduction of L2norm of fn
, whereas larger values allow for
more nonmonotonicity. Global convergence under nonmonotonicity is ensured
by enforcing the GrippoLamparielloLucidi condition (Grippo et al. 1986) in a
nonmonotone linesearch algorithm. Values of M
between 5 to 20 are
generally good, although some problems may require a much larger M.
The default is M = 10
.
The maximum number of iterations. The default is
maxit = 1500
.
The absolute convergence tolerance on the residual L2norm
of fn
. Convergence is declared
when sqrt(sum(F(x)^2) / npar) < tol.
Default is tol = 1.e07
.
A logical variable (TRUE/FALSE). If TRUE
, information on
the progress of solving the system is produced.
Default is trace = TRUE
.
An integer that controls the frequency of tracing
when trace=TRUE
. Default is triter=10
, which means that
the L2norm of fn
is printed at every 10th iteration.
An integer. Algorithm is terminated when no progress has been
made in reducing the merit function for noimp
consecutive iterations.
Default is noimp=100
.
A logical variable that dictates whether the NelderMead algorithm
in optim
will be called upon to improve userspecified starting value.
Default is NM=FALSE
.
A logical variable that dictates whether the lowmemory LBFGSB
algorithm in optim
will be called after certain types of unsuccessful
termination of sane
. Default is BFGS=FALSE
.
A list with the following components:
par 
The best set of parameters that solves the nonlinear system. 
residual 
L2norm of the function evaluated at 
fn.reduction 
Reduction in the L2norm of the function from the initial L2norm. 
feval 
Number of times 
iter 
Number of iterations taken by the algorithm. 
convergence 
An integer code indicating type of convergence.

message 
A text message explaining which termination criterion was used. 
J Barzilai, and JM Borwein (1988), Twopoint step size gradient methods, IMA J Numerical Analysis, 8, 141148.
L Grippo, F Lampariello, and S Lucidi (1986), A nonmonotone line search technique for Newton's method, SIAM J on Numerical Analysis, 23, 707716.
W LaCruz, and M Raydan (2003), Nonmonotone spectral methods for largescale nonlinear systems, Optimization Methods and Software, 18, 583599.
R Varadhan and C Roland (2008), Simple and globallyconvergent methods for accelerating the convergence of any EM algorithm, Scandinavian J Statistics.
R Varadhan and PD Gilbert (2009), BB: An R Package for Solving a Large System of Nonlinear Equations and for Optimizing a HighDimensional Nonlinear Objective Function, J. Statistical Software, 32:4, http://www.jstatsoft.org/v32/i04/
BBsolve
,
dfsane
,
spg
,
grad
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30  trigexp < function(x) {
# Test function No. 12 in the Appendix of LaCruz and Raydan (2003)
n < length(x)
F < rep(NA, n)
F[1] < 3*x[1]^2 + 2*x[2]  5 + sin(x[1]  x[2]) * sin(x[1] + x[2])
tn1 < 2:(n1)
F[tn1] < x[tn11] * exp(x[tn11]  x[tn1]) + x[tn1] * ( 4 + 3*x[tn1]^2) +
2 * x[tn1 + 1] + sin(x[tn1]  x[tn1 + 1]) * sin(x[tn1] + x[tn1 + 1])  8
F[n] < x[n1] * exp(x[n1]  x[n]) + 4*x[n]  3
F
}
p0 < rnorm(50)
sane(par=p0, fn=trigexp)
sane(par=p0, fn=trigexp, method=1)
######################################
brent < function(x) {
n < length(x)
tnm1 < 2:(n1)
F < rep(NA, n)
F[1] < 3 * x[1] * (x[2]  2*x[1]) + (x[2]^2)/4
F[tnm1] < 3 * x[tnm1] * (x[tnm1+1]  2 * x[tnm1] + x[tnm11]) +
((x[tnm1+1]  x[tnm11])^2) / 4
F[n] < 3 * x[n] * (20  2 * x[n] + x[n1]) + ((20  x[n1])^2) / 4
F
}
p0 < sort(runif(50, 0, 10))
sane(par=p0, fn=brent, control=list(trace=FALSE))
sane(par=p0, fn=brent, control=list(M=200, trace=FALSE))

Questions? Problems? Suggestions? Tweet to @rdrrHQ or email at ian@mutexlabs.com.
All documentation is copyright its authors; we didn't write any of that.