Hooke-Jeeves Derivative-Free Minimization R (working for MPFR)

Description

An implementation of the Hooke-Jeeves algorithm for derivative-free optimization.

This is a slight adaption hjk() from package dfoptim

Usage

hjkMpfr(par, fn, control = list(), ...)

Arguments

Details

Argument control is a list specifing changes to default values of algorithm control parameters. Note that parameter names may be abbreviated as long as they are unique.

The list items are as follows:

tol

Convergence tolerance. Iteration is terminated when the step length of the main loop becomes smaller than tol. This does not imply that the optimum is found with the same accuracy. Default is 1.e-06.

maxfeval

Maximum number of objective function evaluations allowed. Default is Inf, that is no restriction at all.

maximize

A logical indicating whether the objective function is to be maximized (TRUE) or minimized (FALSE). Default is FALSE.

target

A real number restricting the absolute function value. The procedure stops if this value is exceeded. Default is Inf, that is no restriction.

info

A logical variable indicating whether the step number, number of function calls, best function value, and the first component of the solution vector will be printed to the console. Default is FALSE.

If the minimization process threatens to go into an infinite loop, set either maxfeval or target.

Value

A list with the following components:

Note

This algorithm is based on the Matlab code of Prof. C. T. Kelley, given in his book “Iterative methods for optimization”. It has been implemented for package dfoptim with the permission of Prof. Kelley.

This version does not (yet) implement a cache for storing function values that have already been computed as searching the cache makes it slower.

Author(s)

Hans W Borchers hwborchers@googlemail.com; for Rmpfr: John Nash, June 2012. Modifications by Martin Maechler.

References

C.T. Kelley (1999), Iterative Methods for Optimization, SIAM.

Quarteroni, Sacco, and Saleri (2007), Numerical Mathematics, Springer.

See Also

Standard R's optim; optimizeR provides one-dimensional minimization methods that work with mpfr-class numbers.

Examples

## simple smooth example:
ff <- function(x) sum((x - c(2:4))^2)
str(rr <- hjkMpfr(rep(mpfr(0,128), 3), ff, control=list(info=TRUE)))


## Hooke-Jeeves solves high-dim. Rosenbrock function  {but slowly!}
rosenbrock <- function(x) {
    n <- length(x)
    sum (100*((x1 <- x[1:(n-1)])^2 - x[2:n])^2 + (x1 - 1)^2)
}

par0 <- rep(0, 10)
str(rb.db <- hjkMpfr(rep(0, 10), rosenbrock, control=list(info=TRUE)))

## rosenbrook() is quite slow with mpfr-numbers:
str(rb.M. <- hjkMpfr(mpfr(numeric(10), prec=128), rosenbrock,
                     control = list(tol = 1e-8, info=TRUE)))





##  Hooke-Jeeves does not work well on non-smooth functions
nsf <- function(x) {
  f1 <- x[1]^2 + x[2]^2
  f2 <- x[1]^2 + x[2]^2 + 10 * (-4*x[1] - x[2] + 4)
  f3 <- x[1]^2 + x[2]^2 + 10 * (-x[1] - 2*x[2] + 6)
  max(f1, f2, f3)
}
par0 <- c(1, 1) # true min 7.2 at (1.2, 2.4)
h.d <- hjkMpfr(par0,            nsf) # fmin=8 at xmin=(2,2)

## and this is not at all better (but slower!)
h.M <- hjkMpfr(mpfr(c(1,1), 128), nsf, control = list(tol = 1e-15))


## --> demo(hjkMpfr) # -> Fletcher's chebyquad function m = n -- residuals

Results

R version 3.3.1 (2016-06-21) -- "Bug in Your Hair"
Copyright (C) 2016 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> library(Rmpfr)
Loading required package: gmp

Attaching package: 'gmp'

The following objects are masked from 'package:base':

    %*%, apply, crossprod, matrix, tcrossprod

C code of R package 'Rmpfr': GMP using 64 bits per limb


Attaching package: 'Rmpfr'

The following objects are masked from 'package:stats':

    dbinom, dnorm, dpois, pnorm

The following objects are masked from 'package:base':

    cbind, pmax, pmin, rbind

> png(filename="/home/ddbj/snapshot/RGM3/R_CC/result/Rmpfr/hjkMpfr.Rd_%03d_medium.png", width=480, height=480)
> ### Name: hjkMpfr
> ### Title: Hooke-Jeeves Derivative-Free Minimization R (working for MPFR)
> ### Aliases: hjkMpfr
> ### Keywords: optimize
> 
> ### ** Examples
> 
> ## simple smooth example:
> ff <- function(x) sum((x - c(2:4))^2)
> str(rr <- hjkMpfr(rep(mpfr(0,128), 3), ff, control=list(info=TRUE)))
step  nofc fmin         |                 xpar
   1    31 0            | 2                    3                    ....
   2    38 0            | 2                    3                    ....
   3    45 0            | 2                    3                    ....
   4    52 0            | 2                    3                    ....
   5    59 0            | 2                    3                    ....
   6    66 0            | 2                    3                    ....
   7    73 0            | 2                    3                    ....
   8    80 0            | 2                    3                    ....
   9    87 0            | 2                    3                    ....
  10    94 0            | 2                    3                    ....
  11   101 0            | 2                    3                    ....
  12   108 0            | 2                    3                    ....
  13   115 0            | 2                    3                    ....
  14   122 0            | 2                    3                    ....
  15   129 0            | 2                    3                    ....
  16   136 0            | 2                    3                    ....
  17   143 0            | 2                    3                    ....
  18   150 0            | 2                    3                    ....
  19   157 0            | 2                    3                    ....
List of 5
 $ par        :Class 'mpfr' [package "Rmpfr"] of length 3 and precision 128
 .. 2 3 4 
 $ value      :Class 'mpfr' [package "Rmpfr"] of length 1 and precision 128
 .. 0 
 $ convergence: logi TRUE
 $ feval      : num 157
 $ niter      : num 19
> 
> 
> ## Hooke-Jeeves solves high-dim. Rosenbrock function  {but slowly!}
> rosenbrock <- function(x) {
+     n <- length(x)
+     sum (100*((x1 <- x[1:(n-1)])^2 - x[2:n])^2 + (x1 - 1)^2)
+ }
> 
> par0 <- rep(0, 10)
> str(rb.db <- hjkMpfr(rep(0, 10), rosenbrock, control=list(info=TRUE)))
step  nofc fmin         |                 xpar
   1    22 9            | 0                    0                    ....
   2    43 9            | 0                    0                    ....
   3   141 7.65625      | 0.75                 0.5                  ....
   4   201 7.446289     | 0.75                 0.5                  ....
   5   279 6.52887      | 0.8125               0.625                ....
   6   376 6.237591     | 0.78125              0.625                ....
   7   468 6.077345     | 0.796875             0.640625             ....
   8  1382 0.5853327    | 0.9921875            0.9921875            ....
   9  1975 0.1764144    | 1                    0.99609375           ....
  10  2555 0.06922601   | 1                    0.998046875          ....
  11  3162 0.001337998  | 1                    1                    ....
  12  3261 0.001148635  | 1                    1                    ....
  13  3321 0.001105398  | 1                    0.999755859375       ....
  14  3936 0.0005209727 | 1                    0.9998779296875      ....
  15  4798 2.332914e-06 | 1                    1                    ....
  16  4859 1.790248e-06 | 1                    1                    ....
  17  4920 1.654661e-06 | 1                    1                    ....
  18  4981 1.620775e-06 | 1                    0.999992370605469    ....
  19  5042 1.610849e-06 | 0.999996185302734    0.999992370605469    ....
List of 5
 $ par        : num [1:10] 1 1 1 1 1 ...
 $ value      : num 1.61e-06
 $ convergence: logi TRUE
 $ feval      : num 5042
 $ niter      : num 19
> ## No test: 
> ## rosenbrook() is quite slow with mpfr-numbers:
> str(rb.M. <- hjkMpfr(mpfr(numeric(10), prec=128), rosenbrock,
+                      control = list(tol = 1e-8, info=TRUE)))
step  nofc fmin         |                 xpar
   1    22 9            | 0                    0                    ....
   2    43 9            | 0                    0                    ....
   3   141 7.65625      | 0.75                 0.5                  ....
   4   201 7.446289     | 0.75                 0.5                  ....
   5   262 6.865356     | 0.6875               0.5                  ....
   6   322 6.799595     | 0.71875              0.5                  ....
   7   376 6.709261     | 0.703125             0.5                  ....
   8  2097 0.08706208   | 0.9921875            0.9921875            ....
   9  2272 0.07033731   | 1                    1                    ....
  10  2332 0.06740037   | 1                    0.998046875          ....
  11  2831 0.0228433    | 1                    0.9990234375         ....
  12  3621 0.0002009786 | 1                    1                    ....
  13  3777 0.0001152431 | 1                    1                    ....
  14  3837 0.0001061342 | 1                    1                    ....
  15  3898 0.0001037863 | 1                    0.99993896484375     ....
  16  4945 4.070839e-06 | 1                    1                    ....
  17  5004 3.836163e-06 | 1                    0.999984741210938    ....
  18  5063 3.771177e-06 | 0.999992370605469    0.999984741210938    ....
  19  5914 2.458292e-07 | 1                    1                    ....
  20  6201 2.276681e-07 | 1                    0.999998092651367    ....
  21  7591 9.303874e-10 | 1                    1                    ....
  22  7650 7.137228e-10 | 1                    1                    ....
  23  7709 6.595538e-10 | 1                    0.999999761581421    ....
  24  7768 6.445901e-10 | 0.99999988079071     0.999999761581421    ....
  25  8793 1.901377e-10 | 0.999999940395355    0.99999988079071     ....
  26  9579 8.970602e-14 | 1                    1                    ....
List of 5
 $ par        :Class 'mpfr' [package "Rmpfr"] of length 10 and precision 128
 .. 1 1 1 1 ...
 $ value      :Class 'mpfr' [package "Rmpfr"] of length 1 and precision 128
 .. 8.97e-14 
 $ convergence: logi TRUE
 $ feval      : num 9579
 $ niter      : num 26
> ## End(No test)
> 
> 
> ##  Hooke-Jeeves does not work well on non-smooth functions
> nsf <- function(x) {
+   f1 <- x[1]^2 + x[2]^2
+   f2 <- x[1]^2 + x[2]^2 + 10 * (-4*x[1] - x[2] + 4)
+   f3 <- x[1]^2 + x[2]^2 + 10 * (-x[1] - 2*x[2] + 6)
+   max(f1, f2, f3)
+ }
> par0 <- c(1, 1) # true min 7.2 at (1.2, 2.4)
> h.d <- hjkMpfr(par0,            nsf) # fmin=8 at xmin=(2,2)
> ## No test: 
> ## and this is not at all better (but slower!)
> h.M <- hjkMpfr(mpfr(c(1,1), 128), nsf, control = list(tol = 1e-15))
> ## End(No test)
> ## --> demo(hjkMpfr) # -> Fletcher's chebyquad function m = n -- residuals
> 
> 
> 
> 
> 
> dev.off()
null device 
          1 
>