Description Usage Arguments Details Value References See Also Examples

Derivative-Free Spectral Approach for solving 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 Barzilai-Borwein 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 `dfsane`

is another algorithm for implementing non-monotone
spectral residual method for finding a root of nonlinear systems, by working
without gradient information.
It stands for "derivative-free spectral approach for nonlinear equations".
It differs from the function `sane`

in that `sane`

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, Martinez, and Raydan (2006).

A major modification in our R adaptation of the original FORTRAN code is the availability of 3 different options for Barzilai-Borwein (BB) steplengths: `method = 1`

is the BB
steplength used in LaCruz, Martinez and Raydan (2006); `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 similar steplength schemes in their EM acceleration work. Here, we have chosen `method = 2`

as the "default" method, since it generally performe 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 does not work.

- M
A positive integer, typically between 5-20, that controls the monotonicity of the algorithm.

`M=1`

would enforce strict monotonicity in the reduction of L2-norm of`fn`

, whereas larger values allow for more non-monotonicity. Global convergence under non-monotonicity is ensured by enforcing the Grippo-Lampariello-Lucidi condition (Grippo et al. 1986) in a non-monotone line-search 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`

.- maxit
The maximum number of iterations. The default is

`maxit = 1500`

.- tol
The absolute convergence tolerance on the residual L2-norm of

`fn`

. Convergence is declared when*sqrt(sum(F(x)^2) / npar) < tol*. Default is`tol = 1.e-07`

.- trace
A logical variable (TRUE/FALSE). If

`TRUE`

, information on the progress of solving the system is produced. Default is`trace = !quiet`

.- triter
An integer that controls the frequency of tracing when

`trace=TRUE`

. Default is`triter=10`

, which means that the L2-norm of`fn`

is printed at every 10-th iteration.- noimp
An integer. Algorithm is terminated when no progress has been made in reducing the merit function for

`noimp`

consecutive iterations. Default is`noimp=100`

.- NM
A logical variable that dictates whether the Nelder-Mead algorithm in

`optim`

will be called upon to improve user-specified starting value. Default is`NM=FALSE`

.- BFGS
A logical variable that dictates whether the low-memory L-BFGS-B algorithm in

`optim`

will be called after certain types of unsuccessful termination of`dfsane`

. Default is`BFGS=FALSE`

.

A list with the following components:

`par` |
The best set of parameters that solves the nonlinear system. |

`residual` |
L2-norm of the function at convergence,
divided by |

`fn.reduction` |
Reduction in the L2-norm of the function from the initial L2-norm. |

`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), Two-point step size gradient methods, *IMA J Numerical Analysis*, 8, 141-148.

L Grippo, F Lampariello, and S Lucidi (1986), A nonmonotone line search technique for Newton's method, *SIAM J on Numerical Analysis*, 23, 707-716.

W LaCruz, JM Martinez, and M Raydan (2006), Spectral residual mathod without gradient information for solving large-scale nonlinear systems of equations, *Mathematics of Computation*, 75, 1429-1448.

R Varadhan and C Roland (2008), Simple and globally-convergent 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 High-Dimensional Nonlinear Objective Function, *J. Statistical Software*, 32:4, http://www.jstatsoft.org/v32/i04/

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 31 32 | ```
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:(n-1)
F[tn1] <- -x[tn1-1] * exp(x[tn1-1] - 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[n-1] * exp(x[n-1] - x[n]) + 4*x[n] - 3
F
}
p0 <- rnorm(50)
dfsane(par=p0, fn=trigexp) # default is method=2
dfsane(par=p0, fn=trigexp, method=1)
dfsane(par=p0, fn=trigexp, method=3)
dfsane(par=p0, fn=trigexp, control=list(triter=5, M=5))
######################################
brent <- function(x) {
n <- length(x)
tnm1 <- 2:(n-1)
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[tnm1-1]) +
((x[tnm1+1] - x[tnm1-1])^2) / 4
F[n] <- 3 * x[n] * (20 - 2 * x[n] + x[n-1]) + ((20 - x[n-1])^2) / 4
F
}
p0 <- sort(runif(50, 0, 20))
dfsane(par=p0, fn=brent, control=list(trace=FALSE))
dfsane(par=p0, fn=brent, control=list(M=200, trace=FALSE))
``` |

```
Iteration: 0 ||F(x0)||: 24.39815
iteration: 10 ||F(xn)|| = 0.08345766
iteration: 20 ||F(xn)|| = 3.273322e-05
$par
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[39] 1 1 1 1 1 1 1 1 1 1 1 1
$residual
[1] 2.574418e-08
$fn.reduction
[1] 172.521
$feval
[1] 29
$iter
[1] 28
$convergence
[1] 0
$message
[1] "Successful convergence"
Iteration: 0 ||F(x0)||: 24.39815
iteration: 10 ||F(xn)|| = 0.05324743
iteration: 20 ||F(xn)|| = 3.033682e-05
$par
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[39] 1 1 1 1 1 1 1 1 1 1 1 1
$residual
[1] 9.925221e-08
$fn.reduction
[1] 172.521
$feval
[1] 28
$iter
[1] 27
$convergence
[1] 0
$message
[1] "Successful convergence"
Iteration: 0 ||F(x0)||: 24.39815
iteration: 10 ||F(xn)|| = 0.06064557
iteration: 20 ||F(xn)|| = 3.628221e-05
$par
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[39] 1 1 1 1 1 1 1 1 1 1 1 1
$residual
[1] 8.088025e-08
$fn.reduction
[1] 172.521
$feval
[1] 28
$iter
[1] 27
$convergence
[1] 0
$message
[1] "Successful convergence"
Iteration: 0 ||F(x0)||: 24.39815
iteration: 5 ||F(xn)|| = 10.27982
iteration: 10 ||F(xn)|| = 0.08345766
iteration: 15 ||F(xn)|| = 0.001896207
iteration: 20 ||F(xn)|| = 3.273322e-05
iteration: 25 ||F(xn)|| = 2.955506e-06
$par
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[39] 1 1 1 1 1 1 1 1 1 1 1 1
$residual
[1] 2.574418e-08
$fn.reduction
[1] 172.521
$feval
[1] 29
$iter
[1] 28
$convergence
[1] 0
$message
[1] "Successful convergence"
$par
[1] 0.9697796 1.6932028 2.3260889 2.9062576 3.4501938 3.9669557
[7] 4.4622031 4.9397765 5.4024364 5.8522530 6.2908312 6.7194474
[13] 7.1391390 7.5507637 7.9550415 8.3525844 8.7439183 9.1294998
[19] 9.5097280 9.8849551 10.2554936 10.6216224 10.9835920 11.3416284
[25] 11.6959364 12.0467024 12.3940965 12.7382750 13.0793812 13.4175477
[31] 13.7528968 14.0855421 14.4155892 14.7431365 15.0682760 15.3910935
[37] 15.7116697 16.0300803 16.3463966 16.6606855 16.9730105 17.2834315
[43] 17.5920050 17.8987849 18.2038220 18.5071647 18.8088591 19.1089490
[49] 19.4074761 19.7044805
$residual
[1] 9.493634e-08
$fn.reduction
[1] 111.6675
$feval
[1] 1288
$iter
[1] 934
$convergence
[1] 0
$message
[1] "Successful convergence"
$par
[1] 0.9697798 1.6932032 2.3260894 2.9062582 3.4501945 3.9669565
[7] 4.4622040 4.9397775 5.4024374 5.8522541 6.2908323 6.7194485
[13] 7.1391401 7.5507649 7.9550427 8.3525856 8.7439196 9.1295010
[19] 9.5097292 9.8849563 10.2554948 10.6216236 10.9835932 11.3416296
[25] 11.6959375 12.0467035 12.3940976 12.7382761 13.0793823 13.4175487
[31] 13.7528977 14.0855430 14.4155901 14.7431374 15.0682768 15.3910943
[37] 15.7116705 16.0300810 16.3463972 16.6606861 16.9730111 17.2834320
[43] 17.5920055 17.8987852 18.2038223 18.5071649 18.8088593 19.1089491
[49] 19.4074762 19.7044805
$residual
[1] 9.102383e-08
$fn.reduction
[1] 111.6675
$feval
[1] 457
$iter
[1] 453
$convergence
[1] 0
$message
[1] "Successful convergence"
```

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.