nag_opt_bounds_qa_no_deriv (e04jcc) (PDF version)

e04 Chapter Contents

e04 Chapter Introduction

NAG Library ManualKeyword Search:

NAG Library Function Document

nag_opt_bounds_qa_no_deriv (e04jcc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

▸▿ 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

1

Purpose

nag_opt_bounds_qa_no_deriv (e04jcc) is an easy-to-use algorithm that uses methods of quadratic approximation to find a minimum of an objective function

F

over

x \in R^{n}

, subject to fixed lower and upper bounds on the independent variables

x_{1}, x_{2}, \dots, x_{n}

. Derivatives of

F

are not required.

The function is intended for functions that are continuous and that have continuous first and second derivatives (although it will usually work even if the derivatives have occasional discontinuities). Efficiency is maintained for large

n

.

2

Specification

#include <nag.h>

#include <nage04.h>

void

nag_opt_bounds_qa_no_deriv (

void	(objfun)(Integer n, const double x[], double f, Nag_Comm comm, Integer inform),

Integer n, Integer npt, double x[], const double bl[], const double bu[], double rhobeg, double rhoend,

void	(monfun)(Integer n, Integer nf, const double x[], double f, double rho, Nag_Comm comm, Integer *inform),

Integer maxcal, double *f, Integer *nf, Nag_Comm *comm, NagError *fail)

3

Description

nag_opt_bounds_qa_no_deriv (e04jcc) is applicable to problems of the form:

\underset{x \in R^{n}}{minimize} F (x) subject to ℓ \leq x \leq u and ℓ \leq u,

where

F

is a nonlinear scalar function whose derivatives may be unavailable, and where the bound vectors are elements of

R^{n}

. Relational operators between vectors are interpreted elementwise.

Fixing variables (that is, setting

ℓ_{i} = u_{i}

for some

i

) is allowed in nag_opt_bounds_qa_no_deriv (e04jcc).

You must supply a function to calculate the value of

F

at any given point

x

.

The method used by nag_opt_bounds_qa_no_deriv (e04jcc) is based on BOBYQA, the method of Bound Optimization BY Quadratic Approximation described in Powell (2009). In particular, each iteration of nag_opt_bounds_qa_no_deriv (e04jcc) generates a quadratic approximation

Q

to

F

that agrees with

F

at

m

automatically chosen interpolation points. The value of

m

is a constant prescribed by you. Updates to the independent variables mostly occur from approximate solutions to trust region subproblems, using the current quadratic model.

4

References

Powell M J D (2009) The BOBYQA algorithm for bound constrained optimization without derivatives Report DAMTP 2009/NA06 University of Cambridge http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf

5

Arguments

1: $objfun$ – function, supplied by the userExternal Function

objfun must evaluate the objective function

F

at a specified vector

x

.

The specification of objfun is:

void	objfun (Integer n, const double x[], double f, Nag_Comm comm, Integer *inform)

1: $n$ – IntegerInput

On entry:

n

, the number of independent variables.

2: $x [n]$ – const doubleInput

On entry:

x

, the vector at which the objective function is to be evaluated.

3: $f$ – double *Output

On exit: must be set to the value of the objective function at

x

, unless you have specified termination of the current problem using inform.

4: $comm$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to objfun.

user – double *
iuser – Integer *
p – Pointer: The type Pointer will be void *. Before calling nag_opt_bounds_qa_no_deriv (e04jcc) you may allocate memory and initialize these pointers with various quantities for use by objfun when called from nag_opt_bounds_qa_no_deriv (e04jcc) (see Section 3.3.1.1 in How to Use the NAG Library and its Documentation).

5: $inform$ – Integer *Output

On exit: must be set to a value describing the action to be taken by the solver on return from objfun. Specifically, if the value is negative the solution of the current problem will terminate immediately; otherwise, computations will continue.

Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by nag_opt_bounds_qa_no_deriv (e04jcc). If your code inadvertently does return any NaNs or infinities, nag_opt_bounds_qa_no_deriv (e04jcc) is likely to produce unexpected results.

2: $n$ – IntegerInput

On entry:

n

, the number of independent variables.

Constraint:

n \geq 2

and

n_{r} \geq 2

, where

n_{r}

denotes the number of non-fixed variables.

3: $npt$ – IntegerInput

On entry:

m

, the number of interpolation conditions imposed on the quadratic approximation at each iteration.

Suggested value:

npt = 2 \times n_{r} + 1

, where

n_{r}

denotes the number of non-fixed variables.

Constraint:

n_{r} + 2 \leq npt \leq \frac{(n_{r} + 1) \times (n_{r} + 2)}{2}

, where

n_{r}

denotes the number of non-fixed variables.

4: $x [n]$ – doubleInput/Output

On entry: an estimate of the position of the minimum. If any component is out-of-bounds it is replaced internally by the bound it violates.

On exit: the lowest point found during the calculations. Thus, if

fail . code =

NE_NOERROR on exit, x is the position of the minimum.

5: $bl [n]$ – const doubleInput

6: $bu [n]$ – const doubleInput

On entry: the fixed vectors of bounds: the lower bounds

ℓ

and the upper bounds

u

, respectively. To signify that a variable is unbounded you should choose a large scalar

r

appropriate to your problem, then set the lower bound on that variable to

- r

and the upper bound to

r

. For well-scaled problems

r = r_{\max}^{\frac{1}{4}}

may be suitable, where

r_{\max}

denotes the largest positive model number (see nag_real_largest_number (X02ALC)).

Constraints:

if $x [i - 1]$ is to be fixed at $bl [i - 1]$ , then $bl [i - 1] = bu [i - 1]$ ;
otherwise $bu [i - 1] - bl [i - 1] \geq 2.0 \times rhobeg$ , for $i = 1, 2, \dots, n$ .

7: $rhobeg$ – doubleInput

On entry: an initial lower bound on the value of the trust region radius.

Suggested value: rhobeg should be about one tenth of the greatest expected overall change to a variable: the initial quadratic model will be constructed by taking steps from the initial x of length rhobeg along each coordinate direction.

Constraints:

$rhobeg > 0.0$ ;
$rhobeg \geq rhoend$ .

8: $rhoend$ – doubleInput

On entry: a final lower bound on the value of the trust region radius.

Suggested value: rhoend should indicate the absolute accuracy that is required in the final values of the variables.

Constraint:

rhoend \geq macheps

, where

macheps = nag_machine_precision

, the machine precision..

9: $monfun$ – function, supplied by the userExternal Function

monfun may be used to monitor the optimization process. It is invoked every time a new trust region radius is chosen.

If no monitoring is required, monfun may be specified as NULLFN.

The specification of monfun is:

void	monfun (Integer n, Integer nf, const double x[], double f, double rho, Nag_Comm comm, Integer inform)

1: $n$ – IntegerInput

On entry:

n

, the number of independent variables.

2: $nf$ – IntegerInput

On entry: the cumulative number of calls made to objfun.

3: $x [n]$ – const doubleInput

On entry: the current best point.

4: $f$ – doubleInput

On entry: the value of objfun at x.

5: $rho$ – doubleInput

On entry: a lower bound on the current trust region radius.

6: $comm$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to monfun.

user – double *
iuser – Integer *
p – Pointer: The type Pointer will be void *. Before calling nag_opt_bounds_qa_no_deriv (e04jcc) you may allocate memory and initialize these pointers with various quantities for use by monfun when called from nag_opt_bounds_qa_no_deriv (e04jcc) (see Section 3.3.1.1 in How to Use the NAG Library and its Documentation).

7: $inform$ – Integer *Output

On exit: must be set to a value describing the action to be taken by the solver on return from monfun. Specifically, if the value is negative the solution of the current problem will terminate immediately; otherwise, computations will continue.

10: $maxcal$ – IntegerInput

On entry: the maximum permitted number of calls to objfun.

Constraint:

maxcal \geq 1

.

11: $f$ – double *Output

On exit: the function value at the lowest point found (x).

12: $nf$ – Integer *Output

On exit: unless

fail . code =

NE_RESCUE_FAILED, NE_TOO_MANY_FEVALS, NE_TR_STEP_FAILED or NE_USER_STOP on exit, the total number of calls made to objfun.

13: $comm$ – Nag_Comm *

The NAG communication argument (see Section 3.3.1.1 in How to Use the NAG Library and its Documentation).

14: $fail$ – NagError *Input/Output

The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

nag_opt_bounds_qa_no_deriv (e04jcc) returns with

fail . code =

NE_NOERROR if the final trust region radius has reached its lower bound rhoend.

6

Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 2.3.1.2 in How to Use the NAG Library and its Documentation for further information.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_BOUND: On entry, $rhobeg = 〈value〉$ , $bl [i - 1] = 〈value〉$ , $bu [i - 1] = 〈value〉$ and $i = 〈value〉$ .
Constraint: if $bl [i - 1] \neq bu [i - 1]$ in coordinate $i$ , $bu [i - 1] - bl [i - 1] \geq 2 \times rhobeg$ .
NE_INT: On entry, $maxcal = 〈value〉$ .
Constraint: $maxcal \geq 1$ .

There were $n_{r} = 〈value〉$ unequal bounds.
Constraint: $n_{r} \geq 2$ .

There were $n_{r} = 〈value〉$ unequal bounds and $npt = 〈value〉$ on entry.
Constraint: $n_{r} + 2 \leq npt \leq \frac{(n_{r} + 1) \times (n_{r} + 2)}{2}$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 2.7.6 in How to Use the NAG Library and its Documentation for further information.
NE_NO_LICENCE: Your licence key may have expired or may not have been installed correctly.
See Section 2.7.5 in How to Use the NAG Library and its Documentation for further information.
NE_REAL: On entry, $rhobeg = 〈value〉$ .
Constraint: $rhobeg > 0.0$ .

On entry, $rhoend = 〈value〉$ .
Constraint: $rhoend \geq macheps$ , where $macheps = nag_machine_precision$ , the machine precision.
NE_REAL_2: On entry, $rhobeg = 〈value〉$ and $rhoend = 〈value〉$ .
Constraint: $rhoend \leq rhobeg$ .
NE_RESCUE_FAILED: A rescue procedure has been called in order to correct damage from rounding errors when computing an update to a quadratic approximation of $F$ , but no further progess could be made. Check your specification of objfun and whether the function needs rescaling. Try a different initial x.
NE_TOO_MANY_FEVALS: The function evaluations limit was reached: objfun has been called maxcal times.
NE_TR_STEP_FAILED: The predicted reduction in a trust region step was non-positive. Check your specification of objfun and whether the function needs rescaling. Try a different initial x.
NE_USER_STOP: User-supplied monitoring function requested termination.

User-supplied objective function requested termination.

7

Accuracy

Experience shows that, in many cases, on successful termination the

\infty

-norm distance from the best point

x

to a local minimum of

F

is less than

10 \times rhoend

, unless rhoend is so small that such accuracy is unattainable.

8

Parallelism and Performance

nag_opt_bounds_qa_no_deriv (e04jcc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

Please consult the x06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9

Further Comments

For each invocation of nag_opt_bounds_qa_no_deriv (e04jcc), local workspace arrays of fixed length are allocated internally. The total size of these arrays amounts to

(npt + 6) \times (npt + n_{r}) + \frac{n_{r} \times (3 n_{r} + 21)}{2}

double elements and

n_{r}

Integer elements, where

n_{r}

denotes the number of non-fixed variables; that is, the total size is

O (n_{r}^{4})

. If you follow the recommendation for the choice of npt on entry, this total size reduces to

O (n_{r}^{2})

.

Usually the total number of function evaluations (nf) is substantially less than

O (n_{r}^{2})

, and often, if

npt = 2 \times n_{r} + 1

on entry, nf is only of magnitude

n_{r}

or less.

10

Example

This example involves the minimization of

F = {(x_{1} + 10 x_{2})}^{2} + 5 {(x_{3} - x_{4})}^{2} + {(x_{2} - 2 x_{3})}^{4} + 10 {(x_{1} - x_{4})}^{4}

subject to

\begin{matrix} 1 \leq x_{1} \leq 3 \\ - 2 \leq x_{2} \leq 0 \\ 1 \leq x_{4} \leq 3, \end{matrix}

starting from the initial guess

(3, - 1, 0, 1)

.

10.1

Program Text

Program Text (e04jcce.c)

10.2

Program Data

None.

10.3

Program Results

Program Results (e04jcce.r)

nag_opt_bounds_qa_no_deriv (e04jcc) (PDF version)

e04 Chapter Contents

e04 Chapter Introduction

NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2017