hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_opt_bounds_bobyqa_func (e04jc)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

nag_opt_bounds_bobyqa_func (e04jc) is an easy-to-use algorithm that uses methods of quadratic approximation to find a minimum of an objective function F over xRn, subject to fixed lower and upper bounds on the independent variables x1,x2,,xn. 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.

Syntax

[x, f, nf, user, ifail] = e04jc(objfun, npt, x, bl, bu, rhobeg, rhoend, monfun, maxcal, 'n', n, 'user', user)
[x, f, nf, user, ifail] = nag_opt_bounds_bobyqa_func(objfun, npt, x, bl, bu, rhobeg, rhoend, monfun, maxcal, 'n', n, 'user', user)

Description

nag_opt_bounds_bobyqa_func (e04jc) is applicable to problems of the form:
minimize xRn Fx   subject to   x u   and   u ,  
where F is a nonlinear scalar function whose derivatives may be unavailable, and where the bound vectors are elements of Rn. Relational operators between vectors are interpreted elementwise.
Fixing variables (that is, setting i=ui for some i) is allowed in nag_opt_bounds_bobyqa_func (e04jc).
You must supply a function to calculate the value of F at any given point x.
The method used by nag_opt_bounds_bobyqa_func (e04jc) is based on BOBYQA, the method of Bound Optimization BY Quadratic Approximation described in Powell (2009). In particular, each iteration of nag_opt_bounds_bobyqa_func (e04jc) 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.

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

Parameters

Compulsory Input Parameters

1:     objfun – function handle or string containing name of m-file
objfun must evaluate the objective function F at a specified vector x.
[f, user, inform] = objfun(n, x, user)

Input Parameters

1:     n int64int32nag_int scalar
n, the number of independent variables.
2:     xn – double array
x, the vector at which the objective function is to be evaluated.
3:     user – Any MATLAB object
objfun is called from nag_opt_bounds_bobyqa_func (e04jc) with the object supplied to nag_opt_bounds_bobyqa_func (e04jc).

Output Parameters

1:     f – double scalar
Must be set to the value of the objective function at x, unless you have specified termination of the current problem using inform.
2:     user – Any MATLAB object
3:     inform int64int32nag_int scalar
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.
2:     npt int64int32nag_int scalar
Suggested value: npt=2×nr+1, where nr denotes the number of non-fixed variables.
m, the number of interpolation conditions imposed on the quadratic approximation at each iteration.
Constraint: nr+2nptnr+1×nr+22, where nr denotes the number of non-fixed variables.
3:     xn – double array
An estimate of the position of the minimum. If any component is out-of-bounds it is replaced internally by the bound it violates.
4:     bln – double array
5:     bun – double array
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=rmax14 may be suitable, where rmax denotes the largest positive model number (see nag_machine_real_largest (x02al)).
Constraints:
  • if xi is to be fixed at bli, then bli=bui;
  • otherwise bui-bli2.0×rhobeg, for i=1,2,,n.
6:     rhobeg – double scalar
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.
An initial lower bound on the value of the trust-region radius.
Constraints:
  • rhobeg>0.0;
  • rhobegrhoend.
7:     rhoend – double scalar
Suggested value: rhoend should indicate the absolute accuracy that is required in the final values of the variables.
A final lower bound on the value of the trust-region radius.
Constraint: rhoend>0.0.
8:     monfun – function handle or string containing name of m-file
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 string nag_opt_bounds_bobyqa_func_dummy_monfun (e04jcp)
[user, inform] = monfun(n, nf, x, f, rho, user)

Input Parameters

1:     n int64int32nag_int scalar
n, the number of independent variables.
2:     nf int64int32nag_int scalar
The cumulative number of calls made to objfun.
3:     xn – double array
The current best point.
4:     f – double scalar
The value of objfun at x.
5:     rho – double scalar
A lower bound on the current trust-region radius.
6:     user – Any MATLAB object
monfun is called from nag_opt_bounds_bobyqa_func (e04jc) with the object supplied to nag_opt_bounds_bobyqa_func (e04jc).

Output Parameters

1:     user – Any MATLAB object
2:     inform int64int32nag_int scalar
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.
9:     maxcal int64int32nag_int scalar
The maximum permitted number of calls to objfun.
Constraint: maxcal1.

Optional Input Parameters

1:     n int64int32nag_int scalar
Default: the dimension of the arrays x, bl, bu. (An error is raised if these dimensions are not equal.)
n, the number of independent variables.
Constraint: n2 and nr2, where nr denotes the number of non-fixed variables.
2:     user – Any MATLAB object
user is not used by nag_opt_bounds_bobyqa_func (e04jc), but is passed to objfun and monfun. Note that for large objects it may be more efficient to use a global variable which is accessible from the m-files than to use user.

Output Parameters

1:     xn – double array
The lowest point found during the calculations. Thus, if ifail=0 on exit, x is the position of the minimum.
2:     f – double scalar
The function value at the lowest point found (x).
3:     nf int64int32nag_int scalar
Unless ifail=1 or -999 on exit, the total number of calls made to objfun.
4:     user – Any MATLAB object
5:     ifail int64int32nag_int scalar
ifail=0 unless the function detects an error (see Error Indicators and Warnings).
nag_opt_bounds_bobyqa_func (e04jc) returns with ifail=0 if the final trust-region radius has reached its lower bound rhoend.

Error Indicators and Warnings

Errors or warnings detected by the function:

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

   ifail=1
Constraint: if blibui in coordinate i, then bui-bli2×rhobeg.
Constraint: maxcal1.
Constraint: rhobeg>0.0.
Constraint: rhoend>0.0.
Constraint: rhoendrhobeg.
There were nr=_ unequal bounds and npt=_ on entry.
Constraint: nr+2nptnr+1×nr+22.
There were unequal bounds.
Constraint: nr2.
   ifail=2
The function evaluations limit was reached: objfun has been called maxcal times.
   ifail=3
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.
   ifail=4
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.
W  ifail=5
User-supplied monitoring function requested termination.
User-supplied objective function requested termination.
   ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
   ifail=-399
Your licence key may have expired or may not have been installed correctly.
   ifail=-999
Dynamic memory allocation failed.

Accuracy

Experience shows that, in many cases, on successful termination the -norm distance from the best point x to a local minimum of F is less than 10×rhoend, unless rhoend is so small that such accuracy is unattainable.

Further Comments

For each invocation of nag_opt_bounds_bobyqa_func (e04jc), local workspace arrays of fixed length are allocated internally. The total size of these arrays amounts to npt+6×npt+nr+nr×3nr+212 double elements and nr integer elements, where nr denotes the number of non-fixed variables; that is, the total size is Onr4. If you follow the recommendation for the choice of npt on entry, this total size reduces to Onr2.
Usually the total number of function evaluations (nf) is substantially less than Onr2, and often, if npt=2×nr+1 on entry, nf is only of magnitude nr or less.

Example

This example involves the minimization of
F = x1+10x2 2 +5 x3 - x4 2 + x2-2 x3 4 +10 x1 - x4 4  
subject to
-1x1 3, -2x2 0, -1x4 3,  
starting from the initial guess 3,-1,0,1 .
function e04jc_example


fprintf('e04jc example results\n\n');

maxcal = int64(500);
rhobeg = 0.1;
rhoend = 1.0e-6;
n = 4;
npt = int64(2*n + 1);

% x(3) is unconstrained, so we're going to set bl(3) to a large
% negative number and bu(3) to a large positive number.
infbnd = x02al^0.25;
bl = [1, -2, -infbnd, 1];
bu = [3, 0, infbnd, 3];
x  = [3, -1, 0, 1];

[x, f, nf, user, ifail] = ...
  e04jc( ...
         @objfun, npt, x, bl, bu, rhobeg, rhoend, @monfun, maxcal);

fprintf('\nFunction value at lowest point found =  %12.5e\n',f);
fprintf(' The corresponding X is:\n');
fprintf('%14.5e',x);
fprintf('\n');



function [f, user, inform] = objfun(n, x, user)
  inform = int64(0);

  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;

function [user, inform] = monfun(n, nf, x, f, rho, user)
  inform = int64(0);

  fprintf('\nNew rho = %13.5e, number of function evaluations = %d\n', rho, nf);
  fprintf('Current function value = %13.5e\n', f);
  fprintf('The corresponding X is:');
  fprintf(' %13.5e', x);
  fprintf('\n');
e04jc example results


New rho =   1.00000e-02, number of function evaluations = 25
Current function value =   4.09399e+00
The corresponding X is:   1.60106e+00  -1.03604e-01   4.51135e-01   1.02335e+00

New rho =   1.00000e-03, number of function evaluations = 67
Current function value =   2.43397e+00
The corresponding X is:   1.00000e+00  -8.59741e-02   4.06744e-01   1.00000e+00

New rho =   1.00000e-04, number of function evaluations = 77
Current function value =   2.43379e+00
The corresponding X is:   1.00000e+00  -8.52328e-02   4.09342e-01   1.00000e+00

New rho =   1.00000e-05, number of function evaluations = 81
Current function value =   2.43379e+00
The corresponding X is:   1.00000e+00  -8.52328e-02   4.09342e-01   1.00000e+00

New rho =   1.00000e-06, number of function evaluations = 93
Current function value =   2.43379e+00
The corresponding X is:   1.00000e+00  -8.52329e-02   4.09303e-01   1.00000e+00

Function value at lowest point found =   2.43379e+00
 The corresponding X is:
   1.00000e+00  -8.52326e-02   4.09303e-01   1.00000e+00

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015