NAG CL Interface
e04kbc (bounds_deriv)
1
Purpose
e04kbc 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. |
First derivatives are required. e04kbc 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
void |
e04kbc (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) |
|
The function may be called by the names: e04kbc or nag_opt_bounds_deriv.
3
Description
e04kbc is applicable to problems of the form:
Special provision is made for unconstrained minimization (i.e., problems which actually have no bounds on the
), problems which have only non-negativity bounds, and problems in which
and
. It is possible to specify that a particular
should be held constant. You must supply a starting point and a function
objfun to calculate the value of
and its first derivatives
at any point
.
A typical iteration starts at the current point
where
(say) variables are free from both their bounds. The vector
, whose elements are the derivatives of
with respect to the free variables, is known. A unit lower triangular matrix
and a diagonal matrix
(both of dimension
), such that
is a positive definite approximation to the matrix of second derivatives with respect to the free variables, are also stored. The equations
are solved to give a search direction
, which is expanded to an
-vector
by the insertion of appropriate zero elements. Then
is found such that
is approximately a minimum (subject to the fixed bounds) with respect to
;
is replaced by
, and the matrices
and
are updated so as to be consistent with the change produced in the gradient by the step
. If any variable actually reaches a bound during the search along
, it is fixed and
is reduced for the next iteration.
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., 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, e04kbc 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, e04kbc sets the to and the to . Thus, provided that the problem has been sensibly scaled, no bounds will be encountered during the minimization process and e04kbc will act as an unconstrained minimization algorithm.
4
References
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
Gill P E, Murray W and Pitfield R A (1972) The implementation of two revised quasi-Newton algorithms for unconstrained optimization NPL Report NAC 11 National Physical Laboratory
5
Arguments
-
1:
– Integer
Input
-
On entry: the number of independent variables.
Constraint:
.
-
2:
– function, supplied by the user
External Function
-
objfun must evaluate the function
and its first derivatives
at any point
. (However, if you do not wish to calculate
or its first derivatives at a particular
, there is the option of setting an argument to cause
e04kbc to terminate immediately.)
The specification of
objfun is:
void |
objfun (Integer n,
const double x[],
double *objf,
double g[],
Nag_Comm *comm)
|
|
-
1:
– Integer
Input
-
On entry: the number of variables.
-
2:
– const double
Input
-
On entry: the point at which the value of , or and , are required.
-
3:
– double *
Output
-
On exit:
objfun must set
objf to the value of the objective function
at the current point
. If it is not possible to evaluate
, then
objfun should assign a negative value to
;
e04kbc will then terminate.
-
4:
– double
Output
-
On exit: if
on entry, then
objfun must set
to the value of the first derivative
at the current point,
for
. If it is not possible to evaluate the first derivatives then
objfun should assign a negative value to
;
e04kbc will then terminate.
(If
on entry,
objfun must
not change the elements of
g.)
-
5:
– Nag_Comm *
-
Pointer to structure of type Nag_Comm; the following members are relevant to
objfun.
- flag – IntegerInput/Output
-
On entry: will be set to 0 or . The value 0 indicates that only itself needs to be evaluated. The value 2 indicates that both and its first derivatives must be calculated.
On exit: if
objfun resets
to some negative number then
e04kbc will terminate immediately with the error indicator
NE_USER_STOP. If
fail is supplied to
e04kbc,
will be set to your setting of
.
- first – Nag_BooleanInput
-
On entry: will be set to Nag_TRUE on the first call to
objfun and Nag_FALSE for all subsequent calls.
- nf – IntegerInput
-
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.
- user – double *
- iuser – Integer *
- p – Pointer
-
The type Pointer will be void * with a C compiler that defines void * and char * otherwise.
Before calling
e04kbc these pointers may be allocated memory and initialized with various quantities for use by
objfun when called from
e04kbc.
Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
e04kbc. If your code inadvertently
does return any NaNs or infinities,
e04kbc is likely to produce unexpected results.
Note: objfun should be tested separately before being used in conjunction with
e04kbc. The array
x must
not be changed by
objfun.
-
3:
– Nag_BoundType
Input
-
On entry: indicates whether the problem is unconstrained or bounded and, if it is bounded, whether the facility for dealing with bounds of special forms is to be used.
bound should be set to one of the following values:
- If the variables are bounded and you will be supplying all the and individually.
- If the problem is unconstrained.
- If the variables are bounded, but all the bounds are of the form .
- If all the variables are bounded, and and .
Constraint:
, , or .
-
4:
– double
Input/Output
-
On entry: the lower bounds
.
If , you must set to , for . (If a lower bound is not required for any , the corresponding should be set to a large negative number, e.g., .)
If
, you must set
to
;
e04kbc will then set the remaining elements of
bl equal to
.
If
or
,
bl will be initialized by
e04kbc.
On exit: the lower bounds actually used by e04kbc, e.g., if , .
-
5:
– double
Input/Output
-
On entry: the upper bounds
.
If , you must set to , for . (If an upper bound is not required for any , the corresponding should be set to a large positive number, e.g., .)
If
, you must set
to
;
e04kbc will then set the remaining elements of
bu equal to
.
If
or
,
bu will be initialized by
e04kbc.
On exit: the upper bounds actually used by e04kbc, e.g., if , .
-
6:
– double
Input/Output
-
On entry: must be set to a guess at the th component of the position of the minimum, for .
On exit: the final point . Thus, if on exit, is the th component of the estimated position of the minimum.
-
7:
– double *
Input/Output
-
On entry: if
or
, you need not initialize
objf.
If
or
,
objf must be set on entry to the value of
at the initial point supplied in
x.
On exit: the function value at the final point given in
x.
-
8:
– double
Input/Output
-
On entry:
- or
- g must be set on entry to the first derivative vector at the initial .
- or
- g need not be set.
On exit: the first derivative vector corresponding to the final point in
x. The elements of
g corresponding to free variables should normally be close to zero.
-
9:
– Nag_E04_Opt *
Input/Output
-
On entry/exit: a pointer to a structure of type Nag_E04_Opt whose members are optional parameters for
e04kbc. 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
e04kbc to perform a ‘warm start’ if it is re-entered (see the member
in
Section 11.2).
If any of these optional parameters are required then the structure
options should be declared and initialized by a call to
e04xxc and supplied as an argument to
e04kbc. However, if the optional parameters are not required the NAG defined null pointer,
E04_DEFAULT, can be used in the function call.
-
10:
– Nag_Comm *
Input/Output
-
Note: comm is a NAG defined type (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
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
e04kbc;
comm will then be declared internally for use in calls to user-supplied functions.
-
11:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- When one of NE_USER_STOP, NE_INT_ARG_LT, NE_BOUND, NE_DERIV_ERRORS, NE_OPT_NOT_INIT, NE_BAD_PARAM, NE_2_REAL_ARG_LT, NE_INVALID_INT_RANGE_1, NE_INVALID_REAL_RANGE_EF, NE_INVALID_REAL_RANGE_FF, NE_INIT_MEM, NE_NO_MEM, NE_HESD or NE_ALLOC_FAIL occurs, no values will have been assigned by e04kbc to objf or to the elements of g, , or .
- An exit of , 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, while . These arguments must satisfy .
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
- NE_BAD_PARAM
-
On entry, argument
bound had an illegal value.
On entry, argument had an illegal value.
On entry, argument had an illegal value.
- NE_BOUND
-
The lower bound for variable (array element ) is greater than the upper bound.
- 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 .
- NE_DERIV_ERRORS
-
Large errors were found in the derivatives of the objective function.
- NE_HESD
-
The initial values of the supplied has some value(s) which is negative or too small or the ratio of the largest element of to the smallest is too large.
- NE_INIT_MEM
-
Option but the pointer in the option structure has not been allocated memory.
- NE_INT_ARG_LT
-
On entry, .
Constraint: .
- NE_INVALID_INT_RANGE_1
-
Value given to is not valid. Correct range is .
- NE_INVALID_REAL_RANGE_EF
-
Value given to not valid. Correct range is .
- NE_INVALID_REAL_RANGE_FF
-
Value given to not valid. Correct range is .
- NE_NO_MEM
-
Option but at least one of the pointers in the option structure has not been allocated memory.
- NE_NOT_APPEND_FILE
-
Cannot open file for appending.
- NE_NOT_CLOSE_FILE
-
Cannot close file .
- NE_OPT_NOT_INIT
-
Options structure not initialized.
- NE_USER_STOP
-
User requested termination, user flag value .
This exit occurs if you set
to a negative value in
objfun. If
fail is supplied the value of
will be the same as your setting of
.
- NE_WRITE_ERROR
-
Error occurred when writing to file .
- 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 first derivatives of
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
has been set so small that rounding 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.
- NW_LOCAL_SEARCH
-
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, , have been performed.
If steady reductions in
, were monitored up to the point where this exit occurred, then the exit probably occurred simply because
was set too small, so the calculations should be restarted from the final point held in
x. This exit may also indicate that
has no minimum.
7
Accuracy
A successful exit
is made from
e04kbc when (B1, B2 and B3) or B4 hold, and the local search (if used) confirms a minimum, where
(Quantities with superscript
are the values at the
th iteration of the quantities mentioned in
Section 3;
is the
machine precision,
denotes the Euclidean norm and
is described in
Section 11.)
If
, then the vector in
x on exit,
, is almost certainly an estimate of the position of the minimum,
, to the accuracy specified by
.
If
or
NW_LOCAL_SEARCH,
may still be a good estimate of
, but the following checks should be made. Let the largest of the first
elements of
be
, let the smallest be
, and define
. The scalar
is usually a good estimate of the condition number of the projected Hessian matrix at
. If
-
(a)the sequence converges to at a superlinear or a fast linear rate,
-
(b), and
-
(c),
then it is almost certain that
is a close approximation to the position of a minimum. When
(b) is true, then usually
is a close approximation to
. The quantities needed for these checks are all available in the results printout from
e04kbc; in particular the final value of
Cond H gives
.
Further suggestions about confirmation of a computed solution are given in the
E04 Chapter Introduction.
8
Parallelism and Performance
e04kbc is not threaded in any implementation.
9.1
Timing
The number of iterations required depends on the number of variables, the behaviour of
, the accuracy demanded and the distance of the starting point from the solution. The number of multiplications performed in an iteration of
e04kbc is roughly proportional to
. In addition, each iteration makes at least one call of
objfun with
if
is used or one call of
objfun with
if
is chosen. So, unless
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, and the corresponding values of the are each in the range , and so that at points one unit away from the solution, 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 e04kbc 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) will always be ,
-
(b)if or on entry, has simply to be set to , for ,
-
(c) and 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 e04kbc and in on exit are unlikely to be of interest (unless they are negative, which would indicate that the modulus of one of the has reached for some reason),
-
(f)Norm g simply gives the norm of the first derivative vector.
10
Example
This example minimizes the function
subject to the bounds
starting from the initial guess
.
The
options structure is declared and initialized by
e04xxc. Four option values are read from a data file by use of
e04xyc. The memory freeing function
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
10.2
Program Data
10.3
Program Results
11
Optional Parameters
A number of optional input and output arguments to
e04kbc 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 parameters you should use the NAG defined null pointer,
E04_DEFAULT, in place of
options when calling
e04kbc; 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
e04xxc. Values may then be assigned to the structure members in the normal C manner.
After return from
e04kbc, the
options structure may only be re-used for future calls of
e04kbc if the dimensions of the new problem are the same. Otherwise, the structure must be cleared by a call of
e04xzc) and re-initialized by a call of
e04xxc before future calls. Failure to do this will result in unpredictable behaviour.
Option settings may also be read from a text file using the function
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
e04xyc.
11.1
Optional Parameter Checklist and Default Values
For easy reference, the following list shows the members of
options which are valid for
e04kbc together with their default values where relevant. The number
is a generic notation for
machine precision (see
X02AJC).
Boolean list |
Nag_TRUE |
Nag_PrintType print_level |
Nag_Soln_Iter |
char outfile[512] |
stdout |
void (*print_fun)() |
NULL |
Boolean deriv_check |
Nag_TRUE |
Nag_InitType init_state |
Nag_Init_None |
Integer max_iter |
|
double optim_tol |
|
Nag_LinFun minlin |
Nag_Lin_Deriv |
double linesearch_tol |
( if ) |
double step_max |
100000.0 |
double f_est |
|
Boolean local_search |
Nag_TRUE |
Integer *state |
size n |
double *hesl |
size |
double *hesd |
size n |
Integer iter |
Integer nf |
11.2
Description of the Optional Parameters
list – Nag_Boolean | | Default |
On entry: if the argument settings in the call to e04kbc will be printed.
print_level – Nag_PrintType | | Default |
On entry: the level of results printout produced by
e04kbc. The following values are available:
|
No output. |
|
The final solution. |
|
One line of output for each iteration. |
|
The final solution and one line of output for each iteration. |
|
The final solution and detailed printout at each iteration. |
Details of each level of results printout are described in
Section 11.3.
Constraint:
, , , or .
outfile – const char[512] | | Default |
On entry: the name of the file to which results should be printed. If then the stdout stream is used.
print_fun – pointer to function | | Default NULL |
On entry: printing function defined by you; the prototype of
is
void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);
See
Section 11.3.1 below for further details.
deriv_check – Nag_Boolean | | Default |
If then the default of is changed to Nag_FALSE.
On entry: if
a check of the derivatives defined by
objfun will be made at the starting point
x. The derivative check is carried out by a call to
e04hcc. If
is set to a value other than its default value (
) then the default of
will be Nag_FALSE. A starting point of
or
should be avoided if this test is to be meaningful, if either of these starting points is necessary then
e04hcc should be used to check
objfun at a different point prior to calling
e04kbc.
init_state – Nag_InitType | | Default |
On entry:
specifies which of the arguments
objf,
g,
,
and
are actually being initialized. Such information will generally reduce the time taken by
e04kbc.
- No values are assumed to have been set in any of objf, g, , or . (e04kbc will use the unit matrix as the initial estimate of the Hessian matrix.)
- The arguments objf and g must contain the value of and its first derivatives at the starting point. The elements must have been set to estimates of the derivatives at the starting point. No values are assumed to have been set in or .
- The arguments objf and g must contain the value of and its first derivatives at the starting point. All elements of must have been set to indicate which variables are on their bounds and which are free. and must contain the Cholesky factors of a positive definite approximation to the by Hessian matrix for the subspace of free variables. (This option is useful for restarting the minimization process if is reached.)
- No values are assumed to have been set in objf or g, but , and must have been set as for . (This option is useful for starting off a minimization run using second derivative information from a previous, similar, run.)
Constraint:
, , or .
max_iter – Integer | | Default |
On entry: the limit on the number of iterations allowed before termination.
Constraint:
.
optim_tol – double | | Default |
On entry: the accuracy in
to which the solution is required. If
is the true value of
at the minimum, then
, the estimated position prior to a normal exit, is such that
where
. For example, if the elements of
are not much larger than
in modulus and if
is set to
, then
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
. (This is because, normally, to machine accuracy,
where
is any column of the identity matrix.)
Constraint:
.
minlin – Nag_LinFun | | Default |
On entry:
specifies whether the linear minimizations (i.e., minimizations of
with respect to
) are to be performed by a function which just requires the evaluation of
,
, or by a function which also requires the first derivatives of
,
.
It will often be possible to evaluate the first derivatives of in about the same amount of computer time that is required for the evaluation of itself – if this is so then e04kbc should be called with set to . However, if the evaluation of the derivatives takes more than about 4 times as long as the evaluation of , then a setting of will usually be preferable. If in doubt, use the default setting as it is slightly more robust.
Constraint:
or .
linesearch_tol – double | | Default if , and otherwise |
If then the default value of will be changed from to if .
On entry: every iteration of
e04kbc involves a linear minimization (i.e., minimization of
with respect to
).
specifies how accurately these linear minimizations are to be performed. The minimum with respect to
will be located more accurately for small values of
(say 0.01) than for large values (say 0.9).
Although accurate linear minimizations will generally reduce the number of iterations performed by e04kbc, 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 may be worthwhile:
-
(a)if objfun takes so little computer time that it is worth using extra calls of objfun to reduce the number of iterations and associated matrix calculations
-
(b)if is a penalty or barrier function arising from a constrained minimization problem (since such problems are very difficult to solve)
-
(c)if and the calculation of first derivatives takes so much computer time (relative to the time taken to evaluate the function) that it is worth using extra function evaluations to reduce the number of derivative evaluations.
If , the default for (if the problem is effectively one-dimensional then should be set to even though ; i.e., if for all except one of the variables the lower and upper bounds are equal).
Constraint:
.
step_max – double | | Default |
On entry: an estimate of the Euclidean distance between the solution and the starting point supplied. (For maximum efficiency a slight overestimate is preferable.)
e04kbc will ensure that, for each iteration,
where
is the iteration number. Thus, if the problem has more than one solution,
e04kbc is most likely to find the one nearest the starting point. On difficult problems, a realistic choice can prevent the sequence of
entering a region where the problem is ill-behaved and can also help to avoid possible overflow in the evaluation of
. However an underestimate of
can lead to inefficiency.
Constraint:
.
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 to be set to an underestimate rather than to an overestimate. If no value is supplied then an initial step length of , subject to the variable bounds, will be used.
local_search – Nag_Boolean | | Default |
On entry:
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 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 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
with respect to
. For most problems this will be small (relative to the total time required for the minimization).
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 at the minimum is known. |
state – Integer * | | Default memory |
On entry:
need not be set if the default option of
is used as
n values of memory will be automatically allocated by
e04kbc.
If
or
has been chosen,
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
e04kbc with
and the same value of
n. If a previous call has not been made you must allocate sufficient memory.
When
or
then
must specify information about which variables are currently on their bounds and which are free. If
is:
-
(a)fixed on its upper bound, is ;
-
(b)fixed on its lower bound, is ;
-
(c)effectively a constant (i.e., ), is ;
-
(d)free, gives its position in the sequence of free variables.
If or , will be initialized by e04kbc.
If or , must be initialized before e04kbc is called.
On exit:
gives information as above about the final point given in
x.
hesl – double * | | Default memory |
hesd – double * | | Default memory |
On entry:
and
need not be set if the default of
is used as sufficient memory will be automatically allocated by
e04kbc.
If or has been set then must point to a minimum of elements of memory.
must point to at least
n elements of memory if
,
or
has been chosen.
The appropriate amount of memory will already be available for
and
if the calling program has used the
options structure in a previous call to
e04kbc with
and the same value of
n. If a previous call has not been made, you must allocate sufficient memory.
and
are used to store the factors
and
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
, see above.)
holds the lower triangle of
, omitting the unit diagonal, stored by rows.
stores the diagonal elements of
. Thus if
elements of
are positive, the strict lower triangle of
will be held in the first
elements of
and the diagonal elements of
in the first
elements of
.
If (the default), and will be initialized within e04kbc to the factors of the unit matrix.
If you set , must contain on entry an approximation to the second derivative with respect to , for . need not be set.
If or , and must contain on entry the Cholesky factors of a positive definite approximation to the by matrix of second derivatives for the subspace of free variables as specified by your setting of .
On exit:
and
hold the factors
and
corresponding to the final point given in
x. The elements of
are useful for deciding whether to accept the result produced by
e04kbc (see
Section 9).
On exit: the number of iterations which have been performed in e04kbc.
On exit: the number of times the residuals have been evaluated (i.e., number of calls of
objfun).
11.3
Description of Printed Output
The level of printed output can be controlled with the structure members
and
(see
Section 11.2). If
then the argument values to
e04kbc are listed, whereas the printout of results is governed by the value of
. The default of
provides a single line of output at each iteration and the final result. This section describes all of the possible levels of results printout available from
e04kbc.
When
or
a single line of output is produced on completion of each iteration, this gives the following values:
Itn |
the iteration count, . |
Nfun |
the cumulative number of calls to objfun. |
Objective |
the current value of the objective function, |
Norm g |
the Euclidean norm of the projected gradient vector, . |
Norm x |
the Euclidean norm of . |
Norm(x(k-1)-x(k)) |
the Euclidean norm of . |
Step |
the step taken along the computed search direction . |
Cond H |
the ratio of the largest to the smallest element of the diagonal factor 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 , or this single line of output is also produced for the final solution.
When
more detailed results are given at each iteration. Additional values output are:
x |
the current point . |
g |
the current projected gradient vector, . |
Status |
the current state of the variable with respect to its bound(s). |
If
,
or
the final result is printed out. This consists of:
x |
the final point, . |
g |
the final projected gradient vector, . |
Status |
the final state of the variable with respect to its bound(s). |
If then printout will be suppressed; you can print the final solution when e04kbc 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 function pointer, which has prototype
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
this will be called in preference to the internal print function of
e04kbc. Calls to the user-defined function are again controlled by means of the
member. Information is provided through
st and
comm, the two structure arguments to
.
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
,
Section 11.2) in which case
is called with the results of the last iteration (
) and then again when the local search has been completed (
).)
If then the results on completion of an iteration of e04kbc are contained in the members of st. If then the final results from e04kbc, 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:
- iter – Integer
-
The current iteration count, , if ; the final iteration count, , if .
- n – Integer
-
The number of variables.
- x – double *
-
The coordinates of the point .
- f – double *
-
The value of the current objective function.
- g – double *
-
Points to the
n memory locations holding the first derivatives of
at the current point
.
- gpj_norm – double *
-
The Euclidean norm of the current projected gradient .
- step – double *
-
The step taken along the search direction .
- cond – double *
-
The estimate of the condition number of the Hessian matrix.
- xk_norm – double *
-
The Euclidean norm of .
- state – Integer
-
The status of variables
,
, with respect to their bounds. See
Section 3 for a description of the possible status values.
- local_search – Nag_Boolean
-
Nag_TRUE if a local search has been performed.
- nf – Integer
-
The cumulative number of calls made to
objfun.
The relevant members of the structure
comm are:
- it_prt – Nag_Boolean
-
Will be Nag_TRUE when the print function is called with the results of the current iteration.
- sol_prt – Nag_Boolean
-
Will be Nag_TRUE when the print function is called with the final result.
- user – double *
- iuser – Integer *
- p – Pointer
-
Pointers for communication of user information. If used they must be allocated memory either before entry to
e04kbc or during a call to
objfun or
. The type Pointer will be
void * with a C compiler that defines
void * and
char * otherwise.