nag_opt_bounds_no_deriv (e04jbc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_opt_bounds_no_deriv (e04jbc)

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_opt_bounds_no_deriv (e04jbc) is a comprehensive quasi-Newton algorithm for finding:
an unconstrained minimum of a function of several variables;
a minimum of a function of several variables subject to fixed upper and/or lower bounds on the variables.
No derivatives are required. nag_opt_bounds_no_deriv (e04jbc) is intended for objective functions which have continuous first and second derivatives (although it will usually work even if the derivatives have occasional discontinuities).

2  Specification

#include <nag.h>
#include <nage04.h>
void  nag_opt_bounds_no_deriv (Integer n,
void (*objfun)(Integer n, const double x[], double *objf, double g[], Nag_Comm *comm),
Nag_BoundType bound, double bl[], double bu[], double x[], double *objf, double g[], Nag_E04_Opt *options, Nag_Comm *comm, NagError *fail)

3  Description

nag_opt_bounds_no_deriv (e04jbc) is applicable to problems of the form:
Minimize   F x 1 , x 2 , , x n subject to   l j x j u j ,   j = 1 , 2 , , n .
Special provision is made for unconstrained minimization (i.e., problems which actually have no bounds on the x j ), problems which have only non-negativity bounds, and problems in which l 1 = l 2 = = l n  and u 1 = u 2 = = u n . It is possible to specify that a particular x j  should be held constant. You must supply a starting point and a function objfun to calculate the value of F x  at any point x .
A typical iteration starts at the current point x  where n z  (say) variables are free from both their bounds. The vector g z , whose elements are finite difference approximations to the derivatives of F x  with respect to the free variables, is known. A unit lower triangular matrix L  and a diagonal matrix D  (both of dimension n z ), such that LDLT  is a positive definite approximation to the matrix of second derivatives with respect to the free variables, are also stored. The equations
LDLT p z = - g z
are solved to give a search direction p z , which is expanded to an n -vector p  by the insertion of appropriate zero elements. Then α  is found such that F x + α p  is approximately a minimum (subject to the fixed bounds) with respect to α ; x  is replaced by x + α p , and the matrices L  and D  are updated so as to be consistent with the change produced in the estimated gradient by the step α p . If any variable actually reaches a bound during the search along p , it is fixed and n z  is reduced for the next iteration. Most iterations calculate g z  using forward differences, but central differences are used when they seem necessary.
There are two sets of convergence criteria – a weaker and a stronger. Whenever the weaker criteria are satisfied, the Lagrange-multipliers are estimated for all the active constraints. If any Lagrange-multiplier estimate is significantly negative, then one of the variables associated with a negative Lagrange-multiplier estimate is released from its bound and the next search direction is computed in the extended subspace (i.e., n z  is increased). Otherwise minimization continues in the current subspace provided that this is practicable. When it is not, or when the stronger convergence criteria is already satisfied, then, if one or more Lagrange-multiplier estimates are close to zero, a slight perturbation is made in the values of the corresponding variables in turn until a lower function value is obtained. The normal algorithm is then resumed from the perturbed point.
If a saddle point is suspected, a local search is carried out with a view to moving away from the saddle point. In addition, nag_opt_bounds_no_deriv (e04jbc) gives you the option of specifying that a local search should be performed when a point is found which is thought to be a constrained minimum.
If you specify that the problem is unconstrained, nag_opt_bounds_no_deriv (e04jbc) sets the l j  to - 10 10  and the u j  to 10 10 . Thus, provided that the problem has been sensibly scaled, no bounds will be encountered during the minimization process and nag_opt_bounds_no_deriv (e04jbc) will act as an unconstrained minimization algorithm. When the problem is unconstrained, the function values used for estimating the first derivatives will always be required in sets of n . nag_opt_bounds_no_deriv (e04jbc) enables you to take advantage (via the argument bound) of the fact that such sets can often be evaluated in less computer time than n  separate function evaluations would take in general.

4  References

Baker G A Jr and Graves–Morris P R (1981) Padé approximants, Part 1: Basic theory encyclopaedia of Mathematics and its Applications Addison–Wesley
Gill P E and Murray W (1972) Quasi-Newton methods for unconstrained optimization J. Inst. Math. Appl. 9 91–108
Gill P E and Murray W (1973) Safeguarded steplength algorithms for optimization using descent methods NPL Report NAC 37 National Physical Laboratory
Gill P E and Murray W (1976) Minimization subject to bounds on the variables NPL Report NAC 72 National Physical Laboratory

5  Arguments

1:     nIntegerInput
On entry: the number n  of independent variables.
Constraint: n1 .
2:     objfunfunction, supplied by the userExternal Function
objfun must evaluate the function F x  at any x . If nag_opt_bounds_no_deriv (e04jbc) is called with bound=Nag_NoBounds_One_Call, objfun must also be able to provide the set of n  function values used for estimating first derivatives. (However, if you do not wish to calculate F  at a particular x , there is the option of setting an argument to cause nag_opt_bounds_no_deriv (e04jbc) to terminate immediately.)
The specification of objfun is:
void  objfun (Integer n, const double x[], double *objf, double g[], Nag_Comm *comm)
1:     nIntegerInput
On entry: the number n  of variables.
2:     x[n]const doubleInput
On entry: the point x  at which the value of F  is required.
3:     objfdouble *Output
On exit: if commflag = 0  on entry, then objfun must set objf to the value of the objective function F  at the current point given in x. If it is not possible to evaluate F , then objfun should assign a negative value to commflag ; nag_opt_bounds_no_deriv (e04jbc) will then terminate.
4:     g[n]doubleInput/Output
On entry: if commflag = 3  then g contains a set of differencing intervals.
On exit: if commflag = 3  on entry, then objfun must reset g[j-1]  to F x c + g[j-1] × e j , for j=1,2,,n, where x c  is the point given in x and e j  is the j th coordinate direction. If it is not possible to evaluate the elements of g then objfun should assign a negative value to commflag ; nag_opt_bounds_no_deriv (e04jbc) will then terminate.
Thus, since the function values are required at n  points which each differ from x c  only in one coordinate, it may be possible to calculate some terms once but use them in the calculation of more than one function value. (If commflag = 0  on entry, objfun must not change the elements of g.)
5:     commNag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to objfun.
flagIntegerInput/Output
On entry: commflag will be set to 0 or 3. The value 0 indicates that a single function value is required. The value 3 (which will only occur if nag_opt_bounds_no_deriv (e04jbc) is called with bound=Nag_NoBounds_One_Call) indicates that a set of n  function values is required.
On exit: if objfun resets commflag to some negative number then nag_opt_bounds_no_deriv (e04jbc) will terminate immediately with the error indicator NE_USER_STOP. If fail is supplied to nag_opt_bounds_no_deriv (e04jbc), fail.errnum will be set to your setting of commflag.
firstNag_BooleanInput
On entry: will be set to Nag_TRUE on the first call to objfun and Nag_FALSE for all subsequent calls.
nfIntegerInput
On entry: the number of calculations of the objective function; this value will be equal to the number of calls made to objfun, including the current one, unless the argument bound=Nag_NoBounds_One_Call.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void * with a C compiler that defines void * and char * otherwise.
Before calling nag_opt_bounds_no_deriv (e04jbc) these pointers may be allocated memory and initialized with various quantities for use by objfun when called from nag_opt_bounds_no_deriv (e04jbc).
Note: objfun should be tested separately before being used in conjunction with nag_opt_bounds_no_deriv (e04jbc). The array x must not be changed by objfun.
3:     boundNag_BoundTypeInput
On entry: indicates whether the problem is unconstrained or bounded. If the problem is unconstrained, the value of bound can be used to indicate that you wish objfun to be called with commflag  set to 3 when a set of n  function values is required for making difference estimates of derivatives. If there are bounds on the variables, bound can be used to indicate whether the facility for dealing with bounds of special forms is to be used. bound should be set to one of the following values:
bound=Nag_Bounds
If the variables are bounded and you will be supplying all the l j  and u j  individually.
bound=Nag_NoBounds
If the problem is unconstrained and you wish objfun to be called n  times with commflag  set to 0 when a set of function values is required for making difference estimates.
bound=Nag_BoundsZero
If the variables are bounded, but all the bounds are of the form 0 x j .
bound=Nag_BoundsEqual
If all the variables are bounded, and l 1 = l 2 = = l n  and u 1 = u 2 = = u n .
bound=Nag_NoBounds_One_Call
If the problem is unconstrained and you wish a single call to be made to objfun with commflag = 3  when a set of function values are required for making difference estimates.
Constraint: bound=Nag_Bounds, Nag_NoBounds, Nag_BoundsZero, Nag_BoundsEqual or Nag_NoBounds_One_Call.
4:     bl[n]doubleInput/Output
On entry: the lower bounds l j .
If bound=Nag_Bounds, you must set bl[j-1]  to l j  , for j=1,2,,n. (If a lower bound is not required for any x j , the corresponding bl[j-1]  should be set to a large negative number, e.g., - 10 10 .)
If bound=Nag_BoundsEqual, you must set bl[0]  to l 1 ; nag_opt_bounds_no_deriv (e04jbc) will then set the remaining elements of bl equal to bl[0] .
If bound=Nag_NoBounds, Nag_BoundsZero or Nag_NoBounds_One_Call, bl will be initialized by nag_opt_bounds_no_deriv (e04jbc).
On exit: the lower bounds actually used by nag_opt_bounds_no_deriv (e04jbc), e.g., if bound=Nag_BoundsZero, bl[0] = bl[1] = = bl[n-1] = 0.0 .
5:     bu[n]doubleInput/Output
On entry: the upper bounds u j .
If bound=Nag_Bounds, you must set bu[j-1]  to u j , for j=1,2,,n. (If an upper bound is not required for any x j , the corresponding bu[j-1]  should be set to a large positive number, e.g., 10 10 .)
If bound=Nag_BoundsEqual, you must set bu[0]  to u 1 ; nag_opt_bounds_no_deriv (e04jbc) will then set the remaining elements of bu equal to bu[0] .
If bound=Nag_NoBounds, Nag_BoundsZero or Nag_NoBounds_One_Call, bu will be initialized by nag_opt_bounds_no_deriv (e04jbc).
On exit: the upper bounds actually used by nag_opt_bounds_no_deriv (e04jbc), e.g., if bound=Nag_BoundsZero, bu[0] = bu[1] = = bu[n-1] = 10 10 .
6:     x[n]doubleInput/Output
On entry: x[j-1]  must be set to a guess at the j th component of the position of the minimum, for j=1,2,,n.
On exit: the final point x * . Thus, if fail.code=NE_NOERROR  on exit, x[j-1]  is the j th component of the estimated position of the minimum.
7:     objfdouble *Input/Output
On entry: if options.init_state=Nag_Init_None or Nag_Init_H_S, you need not initialize objf.
If options.init_state=Nag_Init_All, objf must be set on entry to the value of F x  at the initial point supplied in x.
On exit: the function value at the final point given in x.
8:     g[n]doubleInput/Output
On entry: if options.init_state=Nag_Init_All, g must be set on entry to an approximation to the first derivative vector at the initial x . This could be calculated by central differences.
If options.init_state=Nag_Init_None or Nag_Init_H_S, g need not be set.
On exit: a finite difference approximation to the first derivative vector. Note that the elements of g corresponding to free variables are updated every iteration, but the elements corresponding to fixed variables are only updated when it is necessary to test the Lagrange-multiplier estimates (see Section 3). So, in the printout from nag_opt_bounds_no_deriv (e04jbc) (see Section 5 and Section 11.3) and on exit from nag_opt_bounds_no_deriv (e04jbc), the elements of g corresponding to fixed variables may be out of date. The elements of g corresponding to free variables should normally be close to zero on exit from nag_opt_bounds_no_deriv (e04jbc).
9:     optionsNag_E04_Opt *Input/Output
On entry/exit: a pointer to a structure of type Nag_E04_Opt whose members are optional arguments for nag_opt_bounds_no_deriv (e04jbc). These structure members offer the means of adjusting some of the argument values of the algorithm and on output will supply further details of the results. A description of the members of options is given below in Section 11. Some of the results returned in options can be used by nag_opt_bounds_no_deriv (e04jbc) to perform a ‘warm start’ if it is re-entered (see the member options.init_state in Section 11.2).
If any of these optional arguments are required then the structure options should be declared and initialized by a call to nag_opt_init (e04xxc) and supplied as an argument to nag_opt_bounds_no_deriv (e04jbc). However, if the optional arguments are not required the NAG defined null pointer, E04_DEFAULT, can be used in the function call.
10:   commNag_Comm *Input/Output
Note: comm is a NAG defined type (see Section 3.2.1.1 in the Essential Introduction).
On entry/exit: structure containing pointers for communication with user-supplied functions; see the above description of objfun for details. If you do not need to make use of this communication feature the null pointer NAGCOMM_NULL may be used in the call to nag_opt_bounds_no_deriv (e04jbc); comm will then be declared internally for use in calls to user-supplied functions.
11:   failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

5.1  Description of Printed Output

Intermediate and final results are printed out by default. The level of printed output can be controlled with the structure member options.print_level (see Section 11.2). The default, options.print_level=Nag_Soln_Iter, provides a single line of output at each iteration and the final result. This section describes the default printout produced by nag_opt_bounds_no_deriv (e04jbc).
The following line of output is produced at each iteration. In all cases the values of the quantities printed are those in effect on completion of the given iteration.
Itn the iteration count, k .
Nfun the cumulative number of calls made to objfun.
Objective the value of the objective function, F x k
Norm g the Euclidean norm of the projected gradient vector, g z x k .
Norm x the Euclidean norm of x k .
Norm(x(k-1)-x(k)) the Euclidean norm of x k-1 - x k .
Step the step α k  taken along the computed search direction p k .
Cond H the ratio of the largest to the smallest element of the diagonal factor D  of the projected Hessian matrix. This quantity is usually a good estimate of the condition number of the projected Hessian matrix. (If no variables are currently free, this value will be zero.)
The printout of the final result consists of:
x the final point, x * .
g the final estimate of the projected gradient vector, g z x * .
Status the final state of the variable with respect to its bound.

6  Error Indicators and Warnings

When one of NE_USER_STOPNE_INT_ARG_LTNE_BOUNDNE_OPT_NOT_INITNE_BAD_PARAMNE_2_REAL_ARG_LTNE_INVALID_INT_RANGE_1NE_INVALID_REAL_RANGE_EFNE_INVALID_REAL_RANGE_FFNE_NO_MEMNE_FD_INTNE_HESD or NE_ALLOC_FAIL occurs, no values will have been assigned by nag_opt_bounds_no_deriv (e04jbc) to objf or to the elements of g, options.hesl, or options.hesd.
An exit of fail.code=NW_TOO_MANY_ITER, NW_COND_MIN and NW_LOCAL_SEARCH may also be caused by mistakes in objfun, by the formulation of the problem or by an awkward function. If there are no such mistakes, it is worth restarting the calculations from a different starting point (not the point at which the failure occurred) in order to avoid the region which caused the failure.
NE_2_REAL_ARG_LT
On entry, options.step_max=value  while options.optim_tol=value . These arguments must satisfy options.step_maxoptions.optim_tol .
NE_ALLOC_FAIL
Dynamic memory allocation failed.
NE_BAD_PARAM
On entry, argument bound had an illegal value.
On entry, argument options.init_state had an illegal value.
On entry, argument options.print_level had an illegal value.
NE_BOUND
The lower bound for variable value (array element bl[value] ) is greater than the upper bound.
NE_CANCEL_ERR
The overall relative cancellation error in the gradient estimate, g, or the expected search direction, p, is larger than 0.1. You should attempt to select another starting point.
NE_CHOLESKY_OVERFLOW
An overflow would have occurred during the updating of the Cholesky factors if the calculations had been allowed to continue. Restart from the current point with options.init_state=Nag_Init_None.
NE_FD_INT
Finite difference interval for variable value (array element options.delta[value] ) is negative or so small that x +  interval =x .
NE_HESD
The initial values of the supplied options.hesd has some value(s) which is negative or too small or the ratio of the largest element of options.hesd to the smallest is too large.
NE_INT_ARG_LT
On entry, n=value.
Constraint: n1.
NE_INVALID_INT_RANGE_1
Value value given to options.max_iter is not valid. Correct range is options.max_iter0 .
NE_INVALID_REAL_RANGE_EF
Value value given to options.optim_tol is not valid. Correct range is ε options.optim_tol < 1.0 .
NE_INVALID_REAL_RANGE_FF
Value value given to options.linesearch_tol is not valid. Correct range is 0.0 options.linesearch_tol < 1.0 .
NE_NO_MEM
Option options.init_state = string  but at least one of the pointers string  in the option structure has not been allocated memory.
NE_NOT_APPEND_FILE
Cannot open file string  for appending.
NE_NOT_CLOSE_FILE
Cannot close file string .
NE_OPT_NOT_INIT
Options structure not initialized.
NE_USER_STOP
User requested termination, user flag value =value . This exit occurs if you set commflag  to a negative value in objfun. If fail is supplied the value of fail.errnum will be the same as your setting of commflag .
NE_WRITE_ERROR
Error occurred when writing to file string .
NW_COND_MIN
The conditions for a minimum have not all been satisfied, but a lower point could not be found. Provided that, on exit, the estimated first derivatives of F x  with respect to the free variables are sufficiently small, and that the estimated condition number of the second derivative matrix is not too large, this error exit may simply mean that, although it has not been possible to satisfy the specified requirements, the algorithm has in fact found the minimum as far as the accuracy of the machine permits. This could be because options.optim_tol has been set so small that rounding the error in objfun makes attainment of the convergence conditions impossible. If the estimated condition number of the approximate Hessian matrix at the final point is large, it could be that the final point is a minimum but that the smallest eigenvalue of the second derivative matrix is so close to zero that it is not possible to recognize the point as a minimum.
The local search has failed to find a feasible point which gives a significant change of function value. If the problem is a genuinely unconstrained one, this type of exit indicates that the problem is extremely ill conditioned or that the function has no minimum. If the problem has bounds which may be close to the minimum, it may just indicate that steps in the subspace of free variables happened to meet a bound before they changed the function value.
NW_TOO_MANY_ITER
The maximum number of iterations, value, have been performed. If steady reductions in F x , were monitored up to the point where this exit occurred, then the exit probably occurred simply because options.max_iter was set too small, so the calculations should be restarted from the final point held in x. This exit may also indicate that F x  has no minimum.

7  Accuracy

A successful exit fail.code=NE_NOERROR  is made from nag_opt_bounds_no_deriv (e04jbc) when (B1, B2 and B3) or B4 hold, and the local search (if used) confirms a minimum, where
(Quantities with superscript k  are the values at the k th iteration of the quantities mentioned in Section 3; ε  is the machine precision, .  denotes the Euclidean norm and options.optim_tol is described in Section 11.)
If fail.code=NE_NOERROR , then the vector in x on exit, x sol , is almost certainly an estimate of the position of the minimum, x true , to the accuracy specified by options.optim_tol.
If fail.code=NW_COND_MIN  or NW_LOCAL_SEARCH, x sol  may still be a good estimate of x true , but the following checks should be made. Let the largest of the first n z  elements of options.hesd be options.hesd[b] , let the smallest be options.hesd[s] , and define k = options.hesd[b]/ options.hesd[s] . The scalar k  is usually a good estimate of the condition number of the projected Hessian matrix at x sol . If
(a) the sequence F x k  converges to F x sol  at a superlinear or a fast linear rate,
(b) g z x sol 2 < 10.0 × ε , and
(c) k < 1.0 / g z x sol ,
then it is almost certain that x sol  is a close approximation to the position of a minimum. When (b) is true, then usually F x sol  is a close approximation to F x true . The quantities needed for these checks are all available in the results printout from nag_opt_bounds_no_deriv (e04jbc); in particular the final value of Cond H gives k .
Further suggestions about confirmation of a computed solution are given in the e04 Chapter Introduction.

8  Parallelism and Performance

Not applicable.

9  Further Comments

9.1  Timing

The number of iterations required depends on the number of variables, the behaviour of F x , the accuracy demanded and the distance of the starting point from the solution. The number of multiplications performed in an iteration of nag_opt_bounds_no_deriv (e04jbc) is roughly proportional to n z 2 . In addition, each iteration makes at least n z + 1  function evaluations. So, unless F x  can be evaluated very quickly, the run time will be dominated by the time spent in objfun.

9.2  Scaling

Ideally, the problem should be scaled so that, at the solution, F x  and the corresponding values of the x j  are each in the range -1 , +1 , and so that at points one unit away from the solution, F x  differs from its value at the solution by approximately one unit. This will usually imply that the Hessian matrix at the solution is well conditioned. It is unlikely that you will be able to follow these recommendations very closely, but it is worth trying (by guesswork), as sensible scaling will reduce the difficulty of the minimization problem, so that nag_opt_bounds_no_deriv (e04jbc) will take less computer time.

9.3  Unconstrained Minimization

If a problem is genuinely unconstrained and has been scaled sensibly, the following points apply:
(a) n z  will always be n ,
(b) if options.init_state=Nag_Init_All or Nag_Init_H_S on entry, options.state[j-1]  has simply to be set to j , for j=1,2,,n,
(c) options.hesl and options.hesd will be factors of the full approximate second derivative matrix with elements stored in the natural order,
(d) the elements of g should all be close to zero at the final point,
(e) the Status values given in the printout from nag_opt_bounds_no_deriv (e04jbc) and in options.state on exit are unlikely to be of interest (unless they are negative, which would indicate that the modulus of one of the x j  has reached 10 10  for some reason),
(f) Norm g simply gives the norm of the estimated first derivative vector.

10  Example

This example minimizes the function
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 the bounds
-1x13 -2x20 -1x43
starting from the initial guess 3,-1,0,1T .
The example program also shows the use of certain optional arguments. It shows option values being assigned directly within the program text and by reading values from a data file. The options structure is declared and initialized by nag_opt_init (e04xxc). Values are then assigned directly to options.outfile and options.optim_tol and three further options are read from the data file by use of nag_opt_read (e04xyc). The memory freeing function nag_opt_free (e04xzc) is used to free the memory assigned to the pointers in the option structure. You must not use the standard C function free() for this purpose.

10.1  Program Text

Program Text (e04jbce.c)

10.2  Program Data

Program Options (e04jbce.opt)

10.3  Program Results

Program Results (e04jbce.r)

11  Optional Arguments

A number of optional input and output arguments to nag_opt_bounds_no_deriv (e04jbc) are available through the structure argument options, type Nag_E04_Opt. An argument may be selected by assigning an appropriate value to the relevant structure member; those arguments not selected will be assigned default values. If no use is to be made of any of the optional arguments you should use the NAG defined null pointer, E04_DEFAULT, in place of options when calling nag_opt_bounds_no_deriv (e04jbc); the default settings will then be used for all arguments.
Before assigning values to options directly the structure must be initialized by a call to the function nag_opt_init (e04xxc). Values may then be assigned to the structure members in the normal C manner.
Option settings may also be read from a text file using the function nag_opt_read (e04xyc) in which case initialization of the options structure will be performed automatically if not already done. Any subsequent direct assignment to the options structure must not be preceded by initialization.
If assignment of functions and memory to pointers in the options structure is required, then this must be done directly in the calling program; they cannot be assigned using nag_opt_read (e04xyc).

11.1  Optional Argument Checklist and Default Values

For easy reference, the following list shows the members of options which are valid for nag_opt_bounds_no_deriv (e04jbc) together with their default values where relevant. The number ε  is a generic notation for machine precision (see nag_machine_precision (X02AJC)).
Boolean list Nag_TRUE
Nag_PrintType print_level Nag_Soln_Iter
char outfile[80] stdout
void (*print_fun)() NULL
Nag_InitType init_state Nag_Init_None
Integer max_iter 50n
double optim_tol 10 ε
double linesearch_tol 0.5 (0.0 if n=1 )
double step_max 100000.0
double f_est  
Boolean local_search Nag_TRUE
double *delta size n
Integer *state size n
double *hesl size max n[n-1] / 2 , 1
double *hesd size n
Integer iter
Integer nf

11.2  Description of the Optional Arguments

list – Nag_BooleanDefault =Nag_TRUE
On entry: if options.list=Nag_TRUE  the argument settings in the call to nag_opt_bounds_no_deriv (e04jbc) will be printed.
print_level – Nag_PrintTypeDefault =Nag_Soln_Iter
On entry: the level of results printout produced by nag_opt_bounds_no_deriv (e04jbc). The following values are available:
Nag_NoPrint No output.
Nag_Soln The final solution.
Nag_Iter One line of output for each iteration.
Nag_Soln_Iter The final solution and one line of output for each iteration.
Nag_Soln_Iter_Full The final solution and detailed printout at each iteration.
Details of each level of results printout are described in Section 11.3.
Constraint: options.print_level=Nag_NoPrint, Nag_Soln, Nag_Iter, Nag_Soln_Iter or Nag_Soln_Iter_Full.
outfile – const char[80]Default = stdout
On entry: the name of the file to which results should be printed. If options.outfile[0] = ' \0 '  then the stdout stream is used.
print_fun – pointer to functionDefault =  NULL
On entry: printing function defined by you; the prototype of options.print_fun is
void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);
See Section 11.3.1 below for further details.
init_state – Nag_InitTypeDefault =Nag_Init_None
On entry: options.init_state specifies which of the arguments objf, g, options.hesl, options.hesd and options.state are actually being initialized. Such information will generally reduce the time taken by nag_opt_bounds_no_deriv (e04jbc).
options.init_state=Nag_Init_None
No values are assumed to have been set in any of objf, g, options.hesl, options.hesd or options.state. (nag_opt_bounds_no_deriv (e04jbc) will use the unit matrix as the initial estimate of the Hessian matrix.)
options.init_state=Nag_Init_All
The arguments objf and g must contain the value of F x  and estimates of its first derivatives at the starting point. All n  elements of options.state must have been set to indicate which variables are on their bounds and which are free. The pointer options.delta must give the n  finite difference intervals. options.hesl and options.hesd must contain the Cholesky factors of a positive definite approximation to the n z  by n z  Hessian matrix for the subspace of free variables. (This option is useful for restarting the minimization process if options.max_iter is reached.)
options.init_state=Nag_Init_H_S
No values are assumed to have been set in objf or g, but options.hesl, options.hesd, options.state and options.delta must have been set as for options.init_state=Nag_Init_All. (This option is useful for starting off a minimization run using second derivative information from a previous, similar, run.)
Constraint: options.init_state=Nag_Init_None, Nag_Init_All or Nag_Init_H_S.
max_iter – IntegerDefault = 50 n
On entry: the limit on the number of iterations allowed before termination.
Constraint: options.max_iter0 .
optim_tol – doubleDefault = 10 ε
On entry: the accuracy in x  to which the solution is required. If x true  is the true value of x  at the minimum, then x sol , the estimated position prior to a normal exit, is such that
x sol - x true < options.optim_tol × 1.0 + x true ,
where y = j=1 n y j 2 1/2 . For example, if the elements of x sol  are not much larger than 1.0 in modulus and if options.optim_tol is set to 10 -5 , then x sol  is usually accurate to about 5 decimal places. (For further details see Section 9.) If the problem is scaled roughly as described in Section 9 and ε  is the machine precision, then ε  is probably the smallest reasonable choice for options.optim_tol. (This is because, normally, to machine accuracy, F x + ε e j = F x  where e j  is any column of the identity matrix.)
Constraint: ε options.optim_tol < 1.0 .
linesearch_tol – doubleDefault =0.5 . (If n=1 , default =0.0 .)
On entry: every iteration of nag_opt_bounds_no_deriv (e04jbc) involves a linear minimization (i.e., minimization of F x + α p  with respect to α ). options.linesearch_tol specifies how accurately these linear minimizations are to be performed. The minimum with respect to α  will be located more accurately for small values of options.linesearch_tol (say 0.01) than for large values (say 0.9).
Although accurate linear minimizations will generally reduce the number of iterations performed by nag_opt_bounds_no_deriv (e04jbc), they will increase the number of function evaluations required for each iteration. On balance, it is usually more efficient to perform a low accuracy linear minimization.
A smaller value such as 0.01 may be worthwhile:
(a) if F x  can be evaluated unusually quickly (since it may be worth using extra function evaluations to reduce the number of iterations and associated matrix calculations);
(b) if F x  is a penalty or barrier function arising from a constrained minimization problem (since such problems are very difficult to solve).
If n=1 , the default for options.linesearch_tol=0.0  (if the problem is effectively one-dimensional then options.linesearch_tol should be set to 0.0 even though n>1 ; i.e., if for all except one of the variables the lower and upper bounds are equal).
Constraint: 0.0 options.linesearch_tol < 1.0 .
step_max – doubleDefault =100000.0
On entry: an estimate of the Euclidean distance between the solution and the starting point supplied. (For maximum efficiency a slight overestimate is preferable.) nag_opt_bounds_no_deriv (e04jbc) will ensure that, for each iteration,
j=1 n x j k - x j k-1 2 1/2 options.step_max ,
where k  is the iteration number. Thus, if the problem has more than one solution, nag_opt_bounds_no_deriv (e04jbc) is most likely to find the one nearest the starting point. On difficult problems, a realistic choice can prevent the sequence of x k  entering a region where the problem is ill-behaved and can also help to avoid possible overflow in the evaluation of F x . However an underestimate of options.step_max can lead to inefficiency.
Constraint: options.step_maxoptions.optim_tol .
f_est – double
On entry: an estimate of the function value at the minimum. This estimate is just used for calculating suitable step lengths for starting linear minimizations off, so the choice is not too critical. However, it is better for options.f_est to be set to an underestimate rather than to an overestimate. If no value is supplied then an initial step length of 1.0  is used, though this may be reduced to ensure that the bounds are not overstepped.
Default =Nag_TRUE
On entry: options.local_search must specify whether or not you wish a ‘local search’ to be performed when a point is found which is thought to be a constrained minimum.
If options.local_search=Nag_TRUE  and either the quasi-Newton direction of search fails to produce a lower function value or the convergence criteria are satisfied, then a local search will be performed. This may move the search away from a saddle point or confirm that the final point is a minimum.
If options.local_search=Nag_FALSE  there will be no local search when a point is found which is thought to be a minimum.
The amount of work involved in a local search is comparable to twice that required in a normal iteration to minimize F x + α p  with respect to α . For most problems this will be small (relative to the total time required for the minimization). options.local_search could be set Nag_FALSE if:
it is known from the physical properties of a problem that a stationary point will be the required minimum;
a point which is not a minimum could be easily recognized, for example if the value of F x  at the minimum is known.
delta – double *Default memory =n
On entry: suitable step lengths for making difference approximations to the partial derivatives of F x .
If options.delta is not allocated memory and options.init_state=Nag_Init_None then nag_opt_bounds_no_deriv (e04jbc) will allocate memory to options.delta and assign a suitable set of difference intervals.
If options.delta is allocated memory, i.e., options.delta is not NULL, and options.init_state=Nag_Init_None then difference intervals are assumed to be supplied by options.delta.
When options.init_stateNag_Init_None then options.delta must hold the finite difference intervals; these may be the values output from a previous call to nag_opt_bounds_no_deriv (e04jbc).
If you wish to supply difference intervals then the following advice can be given. When the problem is scaled roughly as described in Section 9 and ε  is the machine precision, values in the range ε  to ε 2/3  may be suitable. Otherwise, you must choose suitable settings, bearing in mind that, when forward differences are used, the approximation is
F xj = F x + options.delta[j] × e j - F x options.delta[j]
where e j  is the j th coordinate direction, for j=1,2,,n.
On exit: the n finite difference intervals used by nag_opt_bounds_no_deriv (e04jbc). If options.delta is NULL on entry and options.init_state=Nag_Init_None then memory will have been automatically allocated to options.delta and suitable values assigned.
Constraint: options.delta[j] 0.0 , ​ x[j] + options.delta[j] x[j] .
state – Integer *Default memory =n
On entry: options.state need not be set if the default option of options.init_state=Nag_Init_None is used as n values of memory will be automatically allocated by nag_opt_bounds_no_deriv (e04jbc).
If the option options.init_state=Nag_Init_All or Nag_Init_H_S has been chosen, options.state must point to a minimum of n elements of memory. This memory will already be available if the calling program has used the options structure in a previous call to nag_opt_bounds_no_deriv (e04jbc) with options.init_state=Nag_Init_None and the same value of n. If a previous call has not been made, you must allocate sufficient memory.
When options.init_state=Nag_Init_All or Nag_Init_H_S then options.state must specify information about which variables are currently on their bounds and which are free. If x j  is:
(a) fixed on its upper bound, options.state[j-1]  is -1
(b) fixed on its lower bound, options.state[j-1]  is -2
(c) effectively a constant (i.e., l j = u j ), options.state[j-1]  is -3
(d) free, options.state[j-1]  gives its position in the sequence of free variables.
If options.init_state=Nag_Init_None, options.state will be initialized by nag_opt_bounds_no_deriv (e04jbc).
If options.init_state=Nag_Init_All or Nag_Init_H_S, options.state must be initialized before nag_opt_bounds_no_deriv (e04jbc) is called.
On exit: options.state gives information as above about the final point given in n.
hesl – double *Default memory = max n[n-1] / 2 , 1
hesd – double *Default memory =n
On entry: options.hesl and options.hesd need not be set if the default of options.init_state=Nag_Init_None is used as sufficient memory will be automatically allocated by nag_opt_bounds_no_deriv (e04jbc).
If options.init_state=Nag_Init_All or options.init_state=Nag_Init_H_S has been set then options.hesl must point to a minimum of max n[n-1] / 2 , 1  elements of memory.
options.hesd must point to at least n elements of memory if options.init_state=Nag_Init_All or Nag_Init_H_S has been chosen.
The appropriate amount of memory will already be available for options.hesl and options.hesd if the calling program has used the options structure in a previous call to nag_opt_bounds_no_deriv (e04jbc) with options.init_state=Nag_Init_None and the same value of n. If a previous call has not been made, you must allocate sufficient memory.
options.hesl and options.hesd are used to store the factors L  and D  of the current approximation to the matrix of second derivatives with respect to the free variables (see Section 3). (The elements of the matrix are assumed to be ordered according to the permutation specified by the positive elements of options.state, see above.) options.hesl holds the lower triangle of L , omitting the unit diagonal, stored by rows. options.hesd stores the diagonal elements of D . Thus if n z  elements of options.state are positive, the strict lower triangle of L  will be held in the first n z n z - 1 / 2  elements of options.hesl and the diagonal elements of D  in the first n z  elements of options.hesd.
If options.init_state=Nag_Init_None (the default), options.hesl and options.hesd will be initialized within nag_opt_bounds_no_deriv (e04jbc) to the factors of the unit matrix.
If you set options.init_state=Nag_Init_All or Nag_Init_H_S, options.hesl and options.hesd must contain on entry the Cholesky factors of a positive definite approximation to the n z  by n z  matrix of second derivatives for the subspace of free variables as specified by your setting of options.state.
On exit: options.hesl and options.hesd hold the factors L  and D  corresponding to the final point given in x. The elements of options.hesd are useful for deciding whether to accept the result produced by nag_opt_bounds_no_deriv (e04jbc) (see Section 9).
iter – Integer 
On exit: the number of iterations which have been performed in nag_opt_bounds_no_deriv (e04jbc).
nf – Integer 
On exit: the number of times the residuals have been evaluated.

11.3  Description of Printed Output

The level of printed output can be controlled with the structure members options.list and options.print_level (see Section 11.2). If options.list=Nag_TRUE  then the argument values to nag_opt_bounds_no_deriv (e04jbc) are listed, whereas the printout of results is governed by the value of options.print_level. The default of options.print_level=Nag_Soln_Iter provides a single line of output at each iteration and the final result. This section describes all of the possible levels of printout available from nag_opt_bounds_no_deriv (e04jbc).
When options.print_level=Nag_Iter or Nag_Soln_Iter a single line of output is produced on completion of each iteration, this gives the following values:
Itn the iteration count, k.
Nfun the cumulative number of objective function evaluations.
Objective the value of the objective function, F x k
Norm g the Euclidean norm of the projected gradient vector, g z x k .
Norm x the Euclidean norm of x k .
Norm(x(k-1)-x(k)) the Euclidean norm of x k-1 - x k .
Step the step α k  taken along the computed search direction p k .
Cond H the ratio of the largest to the smallest element of the diagonal factor D  of the projected Hessian matrix. This quantity is usually a good estimate of the condition number of the projected Hessian matrix. (If no variables are currently free, this value will be zero.)
When options.print_level=Nag_Soln_Iter_Full more detailed results are given at each iteration. Additional values output are:
x the current point x k .
g the current estimate of the projected gradient vector, g z x k .
Status the current state of the variable with respect to its bound(s).
If options.print_level=Nag_Soln, Nag_Soln_Iter or Nag_Soln_Iter_Full the final result is printed out. This consists of:
x the final point, x * .
g the final estimate of the projected gradient vector, g z x * .
Status the final state of the variable with respect to its bound(s).
If options.print_level=Nag_NoPrint then printout will be suppressed; you can print the final solution when nag_opt_bounds_no_deriv (e04jbc) returns to the calling program.

11.3.1  Output of results via a user-defined printing function

You may also specify your own print function for output of iteration results and the final solution by use of the options.print_fun function pointer, which has prototype
void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);
The rest of this section can be skipped if the default printing facilities provide the required functionality.
When a user-defined function is assigned to options.print_fun this will be called in preference to the internal print function of nag_opt_bounds_no_deriv (e04jbc). Calls to the user-defined function are again controlled by means of the options.print_level member. Information is provided through st and comm, the two structure arguments to options.print_fun.
The results contained in the members of st are those on completion of the last iteration or those after a local search. (An iteration may be followed by a local search (see options.local_search, Section 11.2) in which case options.print_fun is called with the results of the last iteration ( stlocal_search = Nag_FALSE) and then again when the local search has been completed ( stlocal_search = Nag_TRUE).)
If commit_prt = Nag_TRUE then the results on completion of an iteration of nag_opt_bounds_no_deriv (e04jbc) are contained in the members of st. If commsol_prt = Nag_TRUE then the final results from nag_opt_bounds_no_deriv (e04jbc), including details of the final iteration, are contained in the members of st. In both cases, the same members of st are set, as follows:
iterInteger
The current iteration count, k , if commit_prt = Nag_TRUE; the final iteration count, k , if commsol_prt = Nag_TRUE.
nInteger
The number of variables.
xdouble *
The coordinates of the point x k .
fdouble *
The value of the current objective function.
gdouble *
The estimated value of F xj  at x k  , for j=1,2,,n.
gpj_normdouble
The Euclidean norm of the current estimate of the projected gradient g z .
stepdouble
The step α k  taken along the search direction p k .
conddouble
The estimate of the condition number of the Hessian matrix.
xk_normdouble
The Euclidean norm of x k-1 - x k .
stateInteger *
The status of variables x j , j = 1 , 2 , , n , with respect to their bounds. See Section 3 for a description of the possible status values.
Nag_TRUE if a local search has been performed.
nfInteger
The cumulative number of objective function evaluations.
The relevant members of the structure comm are:
it_prtNag_Boolean
Will be Nag_TRUE when the print function is called with the results of the current iteration.
sol_prtNag_Boolean
Will be Nag_TRUE when the print function is called with the final result.
userdouble *
iuserInteger *
pPointer 
Pointers for communication of user information. If used they must be allocated memory either before entry to nag_opt_bounds_no_deriv (e04jbc) or during a call to objfun or options.print_fun. The type Pointer will be void * with a C compiler that defines void * and char * otherwise.

nag_opt_bounds_no_deriv (e04jbc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

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