newuoa_module Module

NEWUOA: NEW Unconstrained Optimization Algorithm

The purpose of NEWUOA is to seek the least value of a function F of several variables, when derivatives are not available. The main new feature of the method is that quadratic models are updated using only about NPT=2N+1 interpolation conditions, the remaining freedom being taken up by minimizing the Frobenius norm of the change to the second derivative matrix of the model.

The new software was developed from uobyqa, which also forms quadratic models from interpolation conditions. That method requires NPT=(N+1)(N+2)/2 conditions, however, because they have to define all the parameters of the model. The least Frobenius norm updating procedure with NPT=2N+1 is usually much more efficient when N is large, because the work of each iteration is much less than before, and in some experiments the number of calculations of the objective function seems to be only of magnitude N.

References

History

  • M.J.D. Powell, December 16th, 2004 : It is hoped that the software will be helpful to much future research and to many applications. There are no restrictions on or charges for its use.
  • Jacob Williams, July 2015 : refactoring of the code into modern Fortran.

Uses

  • module~~newuoa_module~~UsesGraph module~newuoa_module newuoa_module module~kind_module kind_module module~newuoa_module->module~kind_module iso_fortran_env iso_fortran_env module~kind_module->iso_fortran_env

Used by

  • module~~newuoa_module~~UsedByGraph module~newuoa_module newuoa_module module~powellopt powellopt module~powellopt->module~newuoa_module

Abstract Interfaces

abstract interface

  • private subroutine func(n, x, f)

    calfun interface

    Arguments

    Type IntentOptional Attributes Name
    integer :: n
    real(kind=wp) :: x(*)
    real(kind=wp) :: f

Subroutines

public subroutine newuoa(n, npt, x, rhobeg, rhoend, iprint, maxfun, calfun)

This subroutine seeks the least value of a function of many variables, by a trust region method that forms quadratic models by interpolation. There can be some freedom in the interpolation conditions, which is taken up by minimizing the Frobenius norm of the change to the second derivative of the quadratic model, beginning with a zero matrix.

Arguments

Type IntentOptional Attributes Name
integer, intent(in) :: n

the number of variables. must be at least 2.
integer, intent(in) :: npt

The number of interpolation conditions. Its value must be in the interval [N+2,(N+1)(N+2)/2].
real(kind=wp), intent(inout), dimension(*) :: x

Initial values of the variables must be set in X(1),X(2),...,X(N). They will be changed to the values that give the least calculated F.
real(kind=wp), intent(in) :: rhobeg

RHOBEG and RHOEND must be set to the initial and final values of a trust region radius, so both must be positive with RHOEND<=RHOBEG. Typically RHOBEG should be about one tenth of the greatest expected change to a variable, and RHOEND should indicate the accuracy that is required in the final values of the variables.
real(kind=wp), intent(in) :: rhoend

RHOBEG and RHOEND must be set to the initial and final values of a trust region radius, so both must be positive with RHOEND<=RHOBEG. Typically RHOBEG should be about one tenth of the greatest expected change to a variable, and RHOEND should indicate the accuracy that is required in the final values of the variables.

integer, intent(in) :: iprint

The value of IPRINT should be set to 0, 1, 2 or 3, which controls the amount of printing. Specifically, there is no output if IPRINT=0 and there is output only at the return if IPRINT=1. Otherwise, each new value of RHO is printed, with the best vector of variables so far and the corresponding value of the objective function. Further, each new value of F with its variables are output if IPRINT=3.
integer, intent(in) :: maxfun

an upper bound on the number of calls of CALFUN.
procedure(func) :: calfun

It must set F to the value of the objective function for the variables X(1),X(2),...,X(N).

private subroutine newuob(n, npt, x, rhobeg, rhoend, iprint, maxfun, xbase, xopt, xnew, xpt, fval, gq, hq, pq, bmat, zmat, ndim, d, vlag, w, calfun)

Arguments

Type IntentOptional Attributes Name
integer :: n
integer :: npt
real :: x
real :: rhobeg
real :: rhoend
integer :: iprint
integer :: maxfun
real :: xbase
real :: xopt
real :: xnew
real :: xpt
real :: fval
real :: gq
real :: hq
real :: pq
real :: bmat
real :: zmat
integer :: ndim
real :: d
real :: vlag
real :: w
procedure(func) :: calfun

private subroutine bigden(n, npt, xopt, xpt, bmat, zmat, idz, ndim, kopt, knew, d, w, vlag, beta, s, wvec, prod)

Arguments

Type IntentOptional Attributes Name
integer :: n
integer :: npt
real :: xopt
real :: xpt
real :: bmat
real :: zmat
integer :: idz
integer :: ndim
integer :: kopt
integer :: knew
real :: d
real :: w
real :: vlag
real :: beta
real :: s
real :: wvec
real :: prod

private subroutine biglag(n, npt, xopt, xpt, bmat, zmat, idz, ndim, knew, delta, d, alpha, hcol, gc, gd, s, w)

Arguments

Type IntentOptional Attributes Name
integer :: n
integer :: npt
real :: xopt
real :: xpt
real :: bmat
real :: zmat
integer :: idz
integer :: ndim
integer :: knew
real :: delta
real :: d
real :: alpha
real :: hcol
real :: gc
real :: gd
real :: s
real :: w

private subroutine trsapp(n, npt, xopt, xpt, gq, hq, pq, delta, step, d, g, hd, hs, crvmin)

Arguments

Type IntentOptional Attributes Name
integer :: n
integer :: npt
real :: xopt
real :: xpt
real :: gq
real :: hq
real :: pq
real :: delta
real :: step
real :: d
real :: g
real :: hd
real :: hs
real :: crvmin

private subroutine update(n, npt, bmat, zmat, idz, ndim, vlag, beta, knew, w)

Arguments

Type IntentOptional Attributes Name
integer :: n
integer :: npt
real :: bmat
real :: zmat
integer :: idz
integer :: ndim
real :: vlag
real :: beta
integer :: knew
real :: w

public subroutine newuoa_test()

The Chebyquad test problem (Fletcher, 1965) for N = 2,4,6 and 8, with NPT = 2N+1.

Arguments

None