NAG CL Interface
e04lbc (bounds_mod_deriv2_comp)
1
Purpose
e04lbc is a comprehensive modifiedNewton 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 and second derivatives are required. e04lbc 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 
e04lbc (Integer n,
void 
(*objfun)(Integer n,
const double x[],
double *objf,
double g[],
Nag_Comm *comm),


void 
(*hessfun)(Integer n,
const double x[],
double h[],
double hd[],
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: e04lbc, nag_opt_bounds_mod_deriv2_comp or nag_opt_bounds_2nd_deriv.
3
Description
e04lbc is applicable to problems of the form:
Special provision is made for unconstrained minimization (i.e., problems which actually have no bounds on the
${x}_{j}$), problems which have only nonnegativity bounds, and problems in which
${l}_{1}={l}_{2}=\cdots ={l}_{n}$ and
${u}_{1}={u}_{2}=\cdots ={u}_{n}$. It is possible to specify that a particular
${x}_{j}$ should be held constant. You must supply a starting point, a function
objfun to calculate the value of
$F\left(x\right)$ and its first derivatives
$\frac{\partial F}{\partial {x}_{j}}$ at any point
$x$, and a function
hessfun to calculate the second derivatives
$\frac{{\partial}^{2}F}{\partial {x}_{i}\partial {x}_{j}}$.
A typical iteration starts at the current point
$x$ where
${n}_{z}$ (say) variables are free from both their bounds. The vector of first derivatives of
$F\left(x\right)$ with respect to the free variables,
${g}_{z}$, and the matrix of second derivatives with respect to the free variables,
$H$, are obtained. (These both have dimension
${n}_{z}$.) The equations
are solved to give a search direction
${p}_{z}$. (The matrix
$E$ is chosen so that
$H+E$ is positive definite.)
${p}_{z}$ is then expanded to an
$n$vector
$p$ by the insertion of appropriate zero elements;
$\alpha $ is found such that
$F\left(x+\alpha p\right)$ is approximately a minimum (subject to the fixed bounds) with respect to
$\alpha $, and
$x$ is replaced by
$x+\alpha p$. (If a saddle point is found, a special search is carried out so as to move away from the saddle point.) If any variable actually reaches a bound, it is fixed and
${n}_{z}$ 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 Lagrangemultipliers are estimated for all active constraints. If any Lagrangemultiplier estimate is significantly negative, then one of the variables associated with a negative Lagrangemultiplier 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 until the stronger criteria are satisfied. If at this point there are no negative or nearzero Lagrangemultiplier estimates, the process is terminated.
If you specify that the problem is unconstrained, e04lbc 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 e04lbc will act as an unconstrained minimization algorithm.
4
References
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 (1974) Newtontype methods for unconstrained and linearly constrained optimization Math. Programming 7 311–350
Gill P E and Murray W (1976) Minimization subject to bounds on the variables NPL Report NAC 72 National Physical Laboratory
5
Arguments

1:
$\mathbf{n}$ – Integer
Input

On entry: the number $n$ of independent variables.
Constraint:
${\mathbf{n}}\ge 1$.

2:
$\mathbf{objfun}$ – function, supplied by the user
External Function

objfun must evaluate the function
$F\left(x\right)$ and its first derivatives
$\frac{\partial F}{\partial {x}_{j}}$ at any point
$x$. (However, if you do not wish to calculate
$F\left(x\right)$ or its first derivatives at a particular
$x$, there is the option of setting an argument to cause
e04lbc to terminate immediately.)
The specification of
objfun is:
void 
objfun (Integer n,
const double x[],
double *objf,
double g[],
Nag_Comm *comm)



1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.

2:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the point $x$ at which the value of $F$, or $F$ and $\frac{\partial F}{\partial {x}_{j}}$, are required.

3:
$\mathbf{objf}$ – double *
Output

On exit:
objfun must set
objf to the value of the objective function
$F$ at the current point
$x$. If it is not possible to evaluate
$F$ then
objfun should assign a negative value to
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$;
e04lbc will then terminate.

4:
$\mathbf{g}\left[{\mathbf{n}}\right]$ – double
Output

On exit:
objfun must set
${\mathbf{g}}\left[\mathit{j}1\right]$ to the value of the first derivative
$\frac{\partial F}{\partial {x}_{\mathit{j}}}$ at the current point
$x$, for
$\mathit{j}=1,2,\dots ,n$. If it is not possible to evaluate the first derivatives then
objfun should assign a negative value to
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$;
e04lbc will then terminate.

5:
$\mathbf{comm}$ – Nag_Comm *

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

On exit: if
objfun resets
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$ to some negative number then
e04lbc will terminate immediately with the error indicator
NE_USER_STOP. If
fail is supplied to
e04lbc,
${\mathbf{fail}}\mathbf{.}\mathbf{errnum}$ will be set to your setting of
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$.
 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 evaluations 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
e04lbc these pointers may be allocated memory and initialized with various quantities for use by
objfun when called from
e04lbc.
Note: objfun should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
e04lbc. If your code inadvertently
does return any NaNs or infinities,
e04lbc is likely to produce unexpected results.
Note: objfun should be tested separately before being used in conjunction with
e04lbc. The array
x must
not be changed by
objfun.

3:
$\mathbf{hessfun}$ – function, supplied by the user
External Function

hessfun must calculate the second derivatives of
$F\left(x\right)$ at any point
$x$. (As with
objfun there is the option of causing
e04lbc to terminate immediately.)
The specification of
hessfun is:
void 
hessfun (Integer n,
const double x[],
double h[],
double hd[],
Nag_Comm *comm)



1:
$\mathbf{n}$ – Integer
Input

On entry: the number $n$ of variables.

2:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the point $x$ at which the second derivatives of $F$ are required.

3:
$\mathbf{h}\left[{\mathbf{n}}\times \left({\mathbf{n}}1\right)/2\right]$ – double
Output

On exit:
hessfun must place the strict lower triangle of the second derivative matrix of
$F$ (evaluated at the point
$x$) in
h, stored by rows, i.e., set
 ${\mathbf{h}}\left[\left(i1\right)\left(i2\right)/2+j1\right]=\frac{{\partial}^{2}F}{\partial {x}_{i}\partial {x}_{j}}{\mid}_{{\mathbf{x}}}\text{, \hspace{1em} for}i=2,3,\dots ,n\text{ and}j=1,2,\dots ,i1\text{.}$
(The upper triangle is not required because the matrix is symmetric.) If it is not possible to evaluate the elements of
h then
hessfun should assign a negative value to
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$;
e04lbc will then terminate.

4:
$\mathbf{hd}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry: the value of $\frac{\partial F}{\partial {x}_{\mathit{j}}}$ at the point $x$, for $\mathit{j}=1,2,\dots ,n$. These values may be useful in the evaluation of the second derivatives.
On exit: unless
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$ is reset to a negative number
hessfun must place the diagonal elements of the second derivative matrix of
$F$ (evaluated at the point
$x$) in
hd, i.e., set
 ${\mathbf{hd}}\left[j1\right]=\frac{{\partial}^{2}F}{{\partial {x}_{j}}^{2}}{\mid}_{{\mathbf{x}}}\text{, \hspace{1em} for \hspace{1em}}j=1,2,\dots ,n\text{.}$
If it is not possible to evaluate the elements of
hd then
hessfun should assign a negative value to
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$;
e04lbc will then terminate.

5:
$\mathbf{comm}$ – Nag_Comm *

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

On exit: if
hessfun resets
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$ to some negative number then
e04lbc will terminate immediately with the error indicator
NE_USER_STOP. If
fail is supplied to
e04lbc ${\mathbf{fail}}\mathbf{.}\mathbf{errnum}$ will be set to your setting of
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$.
 first – Nag_BooleanInput

On entry: will be set to Nag_TRUE on the first call to
hessfun 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
hessfun 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
e04lbc these pointers may be allocated memory and initialized with various quantities for use by
hessfun when called from
e04lbc.
Note: hessfun should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
e04lbc. If your code inadvertently
does return any NaNs or infinities,
e04lbc is likely to produce unexpected results.
Note: hessfun should be tested separately before being used in conjunction with
e04lbc. The array
x must
not be changed by
hessfun.

4:
$\mathbf{bound}$ – 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:
 ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$
 If the variables are bounded and you will be supplying all the ${l}_{j}$ and ${u}_{j}$ individually.
 ${\mathbf{bound}}=\mathrm{Nag\_NoBounds}$
 If the problem is unconstrained.
 ${\mathbf{bound}}=\mathrm{Nag\_BoundsZero}$
 If the variables are bounded, but all the bounds are of the form $0\le {x}_{j}$.
 ${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$
 If all the variables are bounded, and ${l}_{1}={l}_{2}=\cdots ={l}_{n}$ and ${u}_{1}={u}_{2}=\cdots ={u}_{n}$.
Constraint:
${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, $\mathrm{Nag\_NoBounds}$, $\mathrm{Nag\_BoundsZero}$ or $\mathrm{Nag\_BoundsEqual}$.

5:
$\mathbf{bl}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry: the lower bounds
${l}_{j}$.
If ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, you must set ${\mathbf{bl}}\left[\mathit{j}1\right]$ to ${l}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$. (If a lower bound is not required for any ${x}_{j}$, the corresponding ${\mathbf{bl}}\left[j1\right]$ should be set to a large negative number, e.g., ${10}^{10}$.)
If
${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$, you must set
${\mathbf{bl}}\left[0\right]$ to
${l}_{1}$;
e04lbc will then set the remaining elements of
bl equal to
${\mathbf{bl}}\left[0\right]$.
If
${\mathbf{bound}}=\mathrm{Nag\_NoBounds}$ or
$\mathrm{Nag\_BoundsZero}$,
bl will be initialized by
e04lbc.
On exit: the lower bounds actually used by e04lbc, e.g., if ${\mathbf{bound}}=\mathrm{Nag\_BoundsZero}$, ${\mathbf{bl}}\left[0\right]={\mathbf{bl}}\left[1\right]=\cdots ={\mathbf{bl}}\left[n1\right]=0.0$.

6:
$\mathbf{bu}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry: the upper bounds
${u}_{j}$.
If ${\mathbf{bound}}=\mathrm{Nag\_Bounds}$, you must set ${\mathbf{bu}}\left[\mathit{j}1\right]$ to ${u}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$. (If an upper bound is not required for any ${x}_{\mathit{j}}$, the corresponding ${\mathbf{bu}}\left[j1\right]$ should be set to a large positive number, e.g., ${10}^{10}$.)
If
${\mathbf{bound}}=\mathrm{Nag\_BoundsEqual}$, you must set
${\mathbf{bu}}\left[0\right]$ to
${u}_{1}$;
e04lbc will then set the remaining elements of
bu equal to
${\mathbf{bu}}\left[0\right]$.
If
${\mathbf{bound}}=\mathrm{Nag\_NoBounds}$ or
$\mathrm{Nag\_BoundsZero}$,
bu will be initialized by
e04lbc.
On exit: the upper bounds actually used by e04lbc, e.g., if ${\mathbf{bound}}=\mathrm{Nag\_BoundsZero}$, ${\mathbf{bu}}\left[0\right]={\mathbf{bu}}\left[1\right]=\cdots ={\mathbf{bu}}\left[n1\right]={10}^{10}$.

7:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry: ${\mathbf{x}}\left[\mathit{j}1\right]$ must be set to a guess at the $\mathit{j}$th component of the position of the minimum, for $\mathit{j}=1,2,\dots ,n$.
On exit: the final point ${x}^{*}$. Thus, if ${\mathbf{fail}}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}$ on exit, ${\mathbf{x}}\left[j1\right]$ is the $j$th component of the estimated position of the minimum.

8:
$\mathbf{objf}$ – double *
Output

On exit: the function value at the final point given in
x.

9:
$\mathbf{g}\left[{\mathbf{n}}\right]$ – double
Output

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.

10:
$\mathbf{options}$ – Nag_E04_Opt *
Input/Output

On entry/exit: a pointer to a structure of type Nag_E04_Opt whose members are optional parameters for
e04lbc. 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.
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
e04lbc. However, if the optional parameters are not required the NAG defined null pointer,
E04_DEFAULT, can be used in the function call.

11:
$\mathbf{comm}$ – 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 to usersupplied functions; see the description of
objfun and
hessfun 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
e04lbc;
comm will then be declared internally for use in calls to usersupplied functions.

12:
$\mathbf{fail}$ – 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 and NE_ALLOC_FAIL occurs, no values will have been assigned by e04lbc to objf or to the elements of g, ${\mathbf{options}}\mathbf{.}{\mathbf{state}}$, ${\mathbf{options}}\mathbf{.}{\mathbf{hesl}}$, or ${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$.
 An exit of ${\mathbf{fail}}\mathbf{.}\mathbf{code}=\text{}$NW_TOO_MANY_ITER, NW_LAGRANGE_MULT_ZERO and NW_COND_MIN 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, ${\mathbf{options}}\mathbf{.}{\mathbf{step\_max}}=\u2329\mathit{\text{value}}\u232a$ while ${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}=\u2329\mathit{\text{value}}\u232a$. These arguments must satisfy ${\mathbf{options}}\mathbf{.}{\mathbf{step\_max}}\ge {\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$.
 NE_ALLOC_FAIL

Dynamic memory allocation failed.
 NE_BAD_PARAM

On entry, argument
bound had an illegal value.
On entry, argument ${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}$ had an illegal value.
 NE_BOUND

The lower bound for variable $\u2329\mathit{\text{value}}\u232a$ (array element ${\mathbf{bl}}\left[\u2329\mathit{\text{value}}\u232a\right]$) is greater than the upper bound.
 NE_DERIV_ERRORS

Large errors were found in the derivatives of the objective function.
 NE_INT_ARG_LT

On entry,
n must not be less than 1:
${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
 NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
 NE_INVALID_INT_RANGE_1

Value $\u2329\mathit{\text{value}}\u232a$ given to ${\mathbf{options}}\mathbf{.}{\mathbf{max\_iter}}$ is not valid. Correct range is ${\mathbf{options}}\mathbf{.}{\mathbf{max\_iter}}\ge 0$.
 NE_INVALID_REAL_RANGE_EF

Value $\u2329\mathit{\text{value}}\u232a$ given to ${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$ is not valid. Correct range is $\epsilon \le {\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}<1.0$.
 NE_INVALID_REAL_RANGE_FF

Value $\u2329\mathit{\text{value}}\u232a$ given to ${\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}$ is not valid. Correct range is $0.0\le {\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}<1.0$.
 NE_NOT_APPEND_FILE

Cannot open file $\u2329\mathit{string}\u232a$ for appending.
 NE_NOT_CLOSE_FILE

Cannot close file $\u2329\mathit{string}\u232a$.
 NE_OPT_NOT_INIT

Options structure not initialized.
 NE_USER_STOP

User requested termination, user flag value $\text{}=\u2329\mathit{\text{value}}\u232a$.
This exit occurs if you set
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$ to a negative value in
objfun or
hessfun. If
fail is supplied, the value of
${\mathbf{fail}}\mathbf{.}\mathbf{errnum}$ will be the same as your setting of
$\mathbf{comm}\mathbf{\to}\mathbf{flag}$.
 NE_WRITE_ERROR

Error occurred when writing to file $\u2329\mathit{string}\u232a$.
 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
$F\left(x\right)$ 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
${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$ has been set so small that rounding error in
objfun makes attainment of the convergence conditions impossible.
If the estimated condition number of the second derivative 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_LAGRANGE_MULT_ZERO

All the Lagrangemultiplier estimates which are not indisputably positive lie close to zero.
However, it is impossible either to continue minimizing on the current subspace or to find a feasible lower point by releasing and perturbing any of the fixed variables. You should investigate as for
NW_COND_MIN.
 NW_TOO_MANY_ITER

The maximum number of iterations, $\u2329\mathit{\text{value}}\u232a$, have been performed.
If steady reductions in
$F\left(x\right)$, were monitored up to the point where this exit occurred, then the exit probably occurred simply because
${\mathbf{options}}\mathbf{.}{\mathbf{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\left(x\right)$ has no minimum.
7
Accuracy
A successful exit
$\left({\mathbf{fail}}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}\right)$ is made from
e04lbc when
${H}^{\left(k\right)}$ is positive definite and when (B1, B2 and B3) or B4 hold, where
 $\mathrm{B}1\equiv {\alpha}^{\left(k\right)}\times \Vert {p}^{\left(k\right)}\Vert <\left({\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}+\sqrt{\epsilon}\right)\times \left(1.0+\Vert {x}^{\left(k\right)}\Vert \right)$
 $\mathrm{B}2\equiv \left{F}^{\left(k\right)}{F}^{\left(k1\right)}\right<\left({{\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}}^{2}+\epsilon \right)\times \left(1.0+\left{F}^{\left(k\right)}\right\right)$
 $\mathrm{B}3\equiv \Vert {g}_{z}^{\left(k\right)}\Vert <\left({\epsilon}^{1/3}+{\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}\right)\times \left(1.0+\left{F}^{\left(k\right)}\right\right)$
 $\mathrm{B}4\equiv \Vert {g}_{z}^{\left(k\right)}\Vert <0.01\times \sqrt{\epsilon}$.
(Quantities with superscript
$k$ are the values at the
$k$th iteration of the quantities mentioned in
Section 3;
$\epsilon $ is the
machine precision,
$\text{.}$ denotes the Euclidean norm and
${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$ is described in
Section 11.)
If
${\mathbf{fail}}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}$, then the vector in
x on exit,
${x}_{\mathrm{sol}}$, is almost certainly an estimate of the position of the minimum,
${x}_{\mathrm{true}}$, to the accuracy specified by
${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$.
If
${\mathbf{fail}}\mathbf{.}\mathbf{code}={\mathbf{NW\_COND\_MIN}}$ or
NW_LAGRANGE_MULT_ZERO,
${x}_{\mathrm{sol}}$ may still be a good estimate of
${x}_{\mathrm{true}}$, but the following checks should be made. Let the largest of the first
${n}_{z}$ elements of the optional parameter
${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$ be
${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}\left[b\right]$, let the smallest be
${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}\left[s\right]$, and define
$\kappa ={\mathbf{options}}\mathbf{.}{\mathbf{hesd}}\left[b\right]/{\mathbf{options}}\mathbf{.}{\mathbf{hesd}}\left[s\right]$. The scalar
$\kappa $ is usually a good estimate of the condition number of the projected Hessian matrix at
${x}_{\mathrm{sol}}$. If

(a)the sequence $\left\{F\left({x}^{\left(k\right)}\right)\right\}$ converges to $F\left({x}_{\mathrm{sol}}\right)$ at a superlinear or fast linear rate,

(b)${\Vert {g}_{z}\left({x}_{\mathrm{sol}}\right)\Vert}^{2}<10.0\times \epsilon $, and

(c)$\kappa <1.0/\Vert {g}_{z}\left({x}_{\mathrm{sol}}\right)\Vert $,
then it is almost certain that
${x}_{\mathrm{sol}}$ is a close approximation to the position of a minimum. When
(b) is true, then usually
$F\left({x}_{\mathrm{sol}}\right)$ is a close approximation to
$F\left({x}_{\mathrm{true}}\right)$. The quantities needed for these checks are all available in the results printout from
e04lbc; in particular the final value of
Cond H gives
$\kappa $.
Further suggestions about confirmation of a computed solution are given in the
E04 Chapter Introduction.
8
Parallelism and Performance
e04lbc is not threaded in any implementation.
9.1
Timing
The number of iterations required depends on the number of variables, the behaviour of
$F\left(x\right)$, the accuracy demanded and the distance of the starting point from the solution. The number of multiplications performed in an iteration of
e04lbc is
${n}_{z}^{3}/6+O\left({n}_{z}^{2}\right)$. In addition, each iteration makes one call of
hessfun and at least one call of
objfun. So, unless
$F\left(x\right)$ and its derivatives 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\left(x\right)$ and the corresponding values of the ${x}_{j}$ are each in the range $\left(1,+1\right)$, and so that at points one unit away from the solution, $F\left(x\right)$ 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 e04lbc 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)the optional parameters ${\mathbf{options}}\mathbf{.}{\mathbf{hesl}}$ and ${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$ will be factors of the full approximate second derivative matrix with elements stored in the natural order,

(c)the elements of g should all be close to zero at the final point,

(d)the Status values given in the printout from e04lbc, and in the optional parameter ${\mathbf{options}}\mathbf{.}{\mathbf{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),

(e)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
${\left(1.46,0.82,0.57,1.21\right)}^{\mathrm{T}}$.
The
options structure is declared and initialized by
e04xxc. One option value is 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
e04lbc 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
e04lbc; 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
e04lbc, the
options structure may only be reused for future calls of
e04lbc if the dimensions of the new problem are the same. Otherwise, the structure must be cleared by a call of
e04xzc) and reinitialized 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
e04lbc together with their default values where relevant. The number
$\epsilon $ is a generic notation for
machine precision (see
X02AJC).
Boolean list 
Nag_TRUE 
Nag_PrintType print_level 
$\mathrm{Nag\_Soln\_Iter}$ 
char outfile[512] 
stdout 

void (*print_fun)() 
NULL 

Boolean deriv_check 
Nag_TRUE 
Integer max_iter 
50n 
double optim_tol 
$10\sqrt{\epsilon}$ 
double linesearch_tol 
$0.9$ ($0.0$ if ${\mathbf{n}}=1$) 
double step_max 
100000.0 
Integer *state 
size n 
double *hesl 
size $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}}\left({\mathbf{n}}1\right)/2,1\right)$ 
double *hesd 
size n 
Integer iter 

Integer nf 

11.2
Description of the Optional Parameters
list – Nag_Boolean   Default $\text{}=\mathrm{Nag\_TRUE}$ 
On entry: if ${\mathbf{options}}\mathbf{.}{\mathbf{list}}=\mathrm{Nag\_TRUE}$ the argument settings in the call to e04lbc will be printed.
print_level – Nag_PrintType   Default $\text{}=\mathrm{Nag\_Soln\_Iter}$ 
On entry: the level of results printout produced by
e04lbc. The following values are available:
$\mathrm{Nag\_NoPrint}$ 
No output. 
$\mathrm{Nag\_Soln}$ 
The final solution. 
$\mathrm{Nag\_Iter}$ 
One line of output for each iteration. 
$\mathrm{Nag\_Soln\_Iter}$ 
The final solution and one line of output for each iteration. 
$\mathrm{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:
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_NoPrint}$, $\mathrm{Nag\_Soln}$, $\mathrm{Nag\_Iter}$, $\mathrm{Nag\_Soln\_Iter}$ or $\mathrm{Nag\_Soln\_Iter\_Full}$.
outfile – const char[512]   Default $\text{}=\mathtt{stdout}$ 
On entry: the name of the file to which results should be printed. If ${\mathbf{options}}\mathbf{.}{\mathbf{outfile}}\left[0\right]=\text{'}\text{}\text{0}\text{}\text{'}$ then the stdout stream is used.
print_fun – pointer to function   Default $\text{}=\text{}$ NULL 
On entry: printing function defined by you; the prototype of
${\mathbf{options}}\mathbf{.}{\mathbf{print\_fun}}$ 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 $\text{}=\mathrm{Nag\_TRUE}$ 
On entry: if
${\mathbf{options}}\mathbf{.}{\mathbf{deriv\_check}}=\mathrm{Nag\_TRUE}$ a check of the derivatives defined by
objfun and
hessfun will be made at the starting point
x. A starting point of
$x=0$ or
$x=1$ should be avoided if this test is to be meaningful.
max_iter – Integer   Default $\text{}=50{\mathbf{n}}$ 
On entry: the limit on the number of iterations allowed before termination.
Constraint:
${\mathbf{options}}\mathbf{.}{\mathbf{max\_iter}}\ge 0$.
optim_tol – double   Default $\text{}=10\sqrt{\epsilon}$ 
On entry: the accuracy in
$x$ to which the solution is required. If
${x}_{\mathrm{true}}$ is the true value of
$x$ at the minimum, then
${x}_{\mathrm{sol}}$, the estimated position prior to a normal exit, is such that
 $\Vert {x}_{\mathrm{sol}}{x}_{\mathrm{true}}\Vert <{\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}\times \left(1.0+\Vert {x}_{\mathrm{true}}\Vert \right)$,
where
$\Vert y\Vert ={\left({\sum}_{j=1}^{n}{y}_{j}^{2}\right)}^{1/2}$. For example, if the elements of
${x}_{\mathrm{sol}}$ are not much larger than
$1.0$ in modulus and if
${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$ is set to
${10}^{5}$, then
${x}_{\mathrm{sol}}$ is usually accurate to about five decimal places. (For further details see
Section 9.) If the problem is scaled roughly as described in
Section 9 and
$\epsilon $ is the
machine precision, then
$\sqrt{\epsilon}$ is probably the smallest reasonable choice for
${\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$. (This is because, normally, to machine accuracy,
$F\left(x+\sqrt{\epsilon}{e}_{j}\right)=F\left(x\right)$ where
${e}_{j}$ is any column of the identity matrix.)
Constraint:
$\epsilon \le {\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}<1.0$.
linesearch_tol – double   Default $\text{}=0.9$ if ${\mathbf{n}}>1$, and $0.0$ otherwise 
On entry: every iteration of
e04lbc involves a linear minimization (i.e., minimization of
$F\left(x+\alpha p\right)$ with respect to
$\alpha $).
${\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}$ specifies how accurately these linear minimizations are to be performed. The minimum with respect to
$\alpha $ will be located more accurately for small values of
${\mathbf{options}}\mathbf{.}{\mathbf{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 e04lbc, 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 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 calls to hessfun are expensive compared with calls to objfun.

(c)if $F\left(x\right)$ is a penalty or barrier function arising from a constrained minimization problem (since such problems are very difficult to solve).
If ${\mathbf{n}}=1$, the default for ${\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}=0.0$ (if the problem is effectively onedimensional then ${\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}$ should be set to $0.0$ even though ${\mathbf{n}}>1$; i.e., if for all except one of the variables the lower and upper bounds are equal).
Constraint:
$0.0\le {\mathbf{options}}\mathbf{.}{\mathbf{linesearch\_tol}}<1.0$.
step_max – double   Default $\text{}=100000.0$ 
On entry: an estimate of the Euclidean distance between the solution and the starting point supplied by you. (For maximum efficiency a slight overestimate is preferable.)
e04lbc will ensure that, for each iteration,
 ${\left({\sum}_{j=1}^{n}{\left[{x}_{j}^{\left(k\right)}{x}_{j}^{\left(k1\right)}\right]}^{2}\right)}^{1/2}\le {\mathbf{options}}\mathbf{.}{\mathbf{step\_max}}$,
where
$k$ is the iteration number. Thus, if the problem has more than one solution,
e04lbc is most likely to find the one nearest the starting point. On difficult problems, a realistic choice can prevent the sequence of
${x}^{\left(k\right)}$ entering a region where the problem is illbehaved and can also help to avoid possible overflow in the evaluation of
$F\left(x\right)$. However, an underestimate of
${\mathbf{options}}\mathbf{.}{\mathbf{step\_max}}$ can lead to inefficiency.
Constraint:
${\mathbf{options}}\mathbf{.}{\mathbf{step\_max}}\ge {\mathbf{options}}\mathbf{.}{\mathbf{optim\_tol}}$.
state – Integer *   Default memory $\text{}={\mathbf{n}}$ 
On exit:
${\mathbf{options}}\mathbf{.}{\mathbf{state}}$ contains information about which variables are on their bounds and which are free at the final point given in
x. If
${x}_{j}$ is:

(a)fixed on its upper bound, ${\mathbf{options}}\mathbf{.}{\mathbf{state}}\left[j1\right]$ is $1$;

(b)fixed on its lower bound, ${\mathbf{options}}\mathbf{.}{\mathbf{state}}\left[j1\right]$ is $2$;

(c)effectively a constant (i.e., ${l}_{j}={u}_{j}$), ${\mathbf{options}}\mathbf{.}{\mathbf{state}}\left[j1\right]$ is $3$;

(d)free, ${\mathbf{options}}\mathbf{.}{\mathbf{state}}\left[j1\right]$ gives its position in the sequence of free variables.
hesl – double *   Default memory $\text{}=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}}\left({\mathbf{n}}1\right)/2,1\right)$ 
hesd – double *   Default memory $\text{}={\mathbf{n}}$ 
On exit: during the determination of a direction
${p}_{z}$ (see
Section 3),
$H+E$ is decomposed into the product
${LDL}^{\mathrm{T}}$, where
$L$ is a unit lower triangular matrix and D is a diagonal matrix. (The matrices
$H$,
$E$,
$L$ and
$D$ are all of dimension
${n}_{z}$, where
${n}_{z}$ is the number of variables free from their bounds.
$H$ consists of those rows and columns of the full second derivative matrix which relate to free variables.
$E$ is chosen so that
$H+E$ is positive definite.)
${\mathbf{options}}\mathbf{.}{\mathbf{hesl}}$ and ${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$ are used to store the factors $L$ and $D$. The elements of the strict lower triangle of $L$ are stored row by row in the first ${n}_{z}\left({n}_{z}1\right)/2$ positions of ${\mathbf{options}}\mathbf{.}{\mathbf{hesl}}$. The diagonal elements of $D$ are stored in the first ${n}_{z}$ positions of ${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$.
In the last factorization before a normal exit, the matrix
$E$ will be zero, so that
${\mathbf{options}}\mathbf{.}{\mathbf{hesl}}$ and
${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$ will contain, on exit, the factors of the final second derivative matrix
$H$. The elements of
${\mathbf{options}}\mathbf{.}{\mathbf{hesd}}$ are useful for deciding whether to accept the result produced by
e04lbc (see
Section 9).
On exit: the number of iterations which have been performed in e04lbc.
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
${\mathbf{options}}\mathbf{.}{\mathbf{list}}$ and
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}$ (see
Section 11.2). If
${\mathbf{options}}\mathbf{.}{\mathbf{list}}=\mathrm{Nag\_TRUE}$ then the argument values to
e04lbc are listed, whereas the printout of results is governed by the value of
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}$. The default of
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{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 results printout available from
e04lbc.
When
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_Iter}$ or
$\mathrm{Nag\_Soln\_Iter}$ the following line of output is produced on completion of each iteration.
Itn 
the iteration count, $k$. 
Nfun 
the cumulative number of calls made to objfun. 
Objective 
the value of the objective function, $F\left({x}^{\left(k\right)}\right)$ 
Norm g 
the Euclidean norm of the projected gradient vector, $\Vert {g}_{z}\left({x}^{\left(k\right)}\right)\Vert $. 
Norm x 
the Euclidean norm of ${x}^{\left(k\right)}$. 
Norm(x(k1)x(k)) 
the Euclidean norm of ${x}^{\left(k1\right)}{x}^{\left(k\right)}$. 
Step 
the step ${\alpha}^{\left(k\right)}$ taken along the computed search direction ${p}^{\left(k\right)}$. 
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.) 
PosDef 
indicates whether the second derivative matrix for the current subspace, $H$, is positive definite (Yes) or not (No). 
When ${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_Soln}$, $\mathrm{Nag\_Soln\_Iter}$ or $\mathrm{Nag\_Soln\_Full}$ this single line of output is also produced for the final solution.
When
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_Soln\_Iter\_Full}$ more detailed results are given at each iteration. Additional values output are
x 
the current point ${x}^{\left(k\right)}$. 
g 
the current projected gradient vector, ${g}_{z}\left({x}^{\left(k\right)}\right)$. 
Status 
the current state of the variable with respect to its bound(s). 
If
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_Soln}$,
$\mathrm{Nag\_Soln\_Iter}$ or
$\mathrm{Nag\_Soln\_Iter\_Full}$ the final result is printed out. This consists of:
x 
the final point, ${x}^{*}$. 
g 
the final projected gradient vector, ${g}_{z}\left({x}^{*}\right)$. 
Status 
the final state of the variable with respect to its bound(s). 
If ${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}=\mathrm{Nag\_NoPrint}$ then printout will be suppressed; you can print the final solution when e04lbc returns to the calling program.
11.3.1
Output of results via a userdefined printing function
You may also specify your own print function for output of iteration results and the final solution by use of the
${\mathbf{options}}\mathbf{.}{\mathbf{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 userdefined function is assigned to
${\mathbf{options}}\mathbf{.}{\mathbf{print\_fun}}$ this will be called in preference to the internal print function of
e04lbc. Calls to the userdefined function are again controlled by means of the
${\mathbf{options}}\mathbf{.}{\mathbf{print\_level}}$ member. Information is provided through
st and
comm, the two structure arguments to
${\mathbf{options}}\mathbf{.}{\mathbf{print\_fun}}$.
If $\mathbf{comm}\mathbf{\to}\mathbf{it\_prt}=\mathrm{Nag\_TRUE}$ then the results on completion of an iteration of e04lbc are contained in the members of st. If $\mathbf{comm}\mathbf{\to}\mathbf{sol\_prt}=\mathrm{Nag\_TRUE}$ then the final results from e04lbc, 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, $k$, if $\mathbf{comm}\mathbf{\to}\mathbf{it\_prt}=\mathrm{Nag\_TRUE}$; the final iteration count, $k$, if $\mathbf{comm}\mathbf{\to}\mathbf{sol\_prt}=\mathrm{Nag\_TRUE}$.
 n – Integer

The number of variables.
 x – double *

The coordinates of the point ${x}^{\left(k\right)}$.
 f – double *

The value of the objective function at ${x}^{\left(k\right)}$.
 g – double *

The value of $\frac{\partial F}{\partial {x}_{j}}$ at ${x}^{\left(k\right)}$, $j=1,2,\dots ,n$.
 gpj_norm – double

The Euclidean norm of the projected gradient ${g}_{z}$ at ${x}^{\left(k\right)}$.
 step – double

The step ${\alpha}^{\left(k\right)}$ taken along the search direction ${p}^{\left(k\right)}$.
 cond – double

The estimate of the condition number of the projected Hessian matrix, see
Section 11.3.
 xk_norm – double

The Euclidean norm of ${x}^{\left(k1\right)}{x}^{\left(k\right)}$.
 state – Integer *

The status of variables
${x}_{\mathit{j}}$, for
$\mathit{j}=1,2,\dots ,n$, with respect to their bounds. See
Section 11.2 for a description of the possible status values.
 posdef – Nag_Boolean

Will be Nag_TRUE if the second derivative matrix $H$ for the current subspace is positive definite, and Nag_FALSE otherwise.
 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
e04lbc or during a call to
objfun or
${\mathbf{options}}\mathbf{.}{\mathbf{print\_fun}}$. The type Pointer will be
void * with a C compiler that defines
void * and
char * otherwise.