NAG Library Routine Document

E04DGF/E04DGA

1  Purpose

2  Specification

2.1  Specification for E04DGF

2.2  Specification for E04DGA

3  Description

4  References

5  Parameters

1:     $\mathrm{N}$ – INTEGERInput

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

Constraint: $\mathbf{N}>0$.

2:     $\mathrm{OBJFUN}$ – SUBROUTINE, supplied by the user.External Procedure

OBJFUN must calculate the objective function $F\left(x\right)$ and possibly its gradient as well for a specified $n$-element vector $x$.

The specification of OBJFUN is:

SUBROUTINE OBJFUN ( MODE, N, X, OBJF, OBJGRD, NSTATE, IUSER, RUSER) INTEGER  MODE, N, NSTATE, IUSER(*) REAL (KIND=nag_wp)  X(N), OBJF, OBJGRD(N), RUSER(*)

1:     $\mathrm{MODE}$ – INTEGERInput/Output

On entry: indicates which values must be assigned during each call of OBJFUN. Only the following values need be assigned:

$\mathbf{MODE}=0$

OBJF.

$\mathbf{MODE}=2$

OBJF and OBJGRD.

On exit: may be set to a negative value if you wish to terminate the solution to the current problem, and in this case E04DGF/E04DGA will terminate with IFAIL set to MODE.

2:     $\mathrm{N}$ – INTEGERInput

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

3:     $\mathrm{X}\left(\mathbf{N}\right)$ – REAL (KIND=nag_wp) arrayInput

On entry: $x$, the vector of variables at which the objective function and its gradient are to be evaluated.

4:     $\mathrm{OBJF}$ – REAL (KIND=nag_wp)Output

On exit: the value of the objective function at $x$.

5:     $\mathrm{OBJGRD}\left(\mathbf{N}\right)$ – REAL (KIND=nag_wp) arrayOutput

On exit: if $\mathbf{MODE}=2$, $\mathbf{OBJGRD}\left(\mathit{i}\right)$ must contain the value of $\frac{\partial F}{\partial x_{\mathit{i}}}$ evaluated at $x$, for $\mathit{i}=1,2,\dots ,n$.

6:     $\mathrm{NSTATE}$ – INTEGERInput

On entry: will be $1$ on the first call of OBJFUN by E04DGF/E04DGA, and $0$ for all subsequent calls. Thus, you may wish to test, NSTATE within OBJFUN in order to perform certain calculations once only. For example, you may read data or initialize COMMON blocksglobal variables when $\mathbf{NSTATE}=1$.

7:     $\mathrm{IUSER}\left(*\right)$ – INTEGER arrayUser Workspace

8:     $\mathrm{RUSER}\left(*\right)$ – REAL (KIND=nag_wp) arrayUser Workspace

OBJFUN is called with the parameters IUSER and RUSER as supplied to E04DGF/E04DGA. You are free to use the arrays IUSER and RUSER to supply information to OBJFUN as an alternative to using COMMON global variables.

OBJFUN must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which E04DGF/E04DGA is called. Parameters denoted as Input must not be changed by this procedure.

Note:  OBJFUN should be tested separately before being used in conjunction with E04DGF/E04DGA. See also the description of the optional parameter Verify.

3:     $\mathrm{ITER}$ – INTEGEROutput

On exit: the total number of iterations performed.

4:     $\mathrm{OBJF}$ – REAL (KIND=nag_wp)Output

On exit: the value of the objective function at the final iterate.

5:     $\mathrm{OBJGRD}\left(\mathbf{N}\right)$ – REAL (KIND=nag_wp) arrayOutput

On exit: the gradient of the objective function at the final iterate (or its finite difference approximation).

6:     $\mathrm{X}\left(\mathbf{N}\right)$ – REAL (KIND=nag_wp) arrayInput/Output

On entry: an initial estimate of the solution.

On exit: the final estimate of the solution.

7:     $\mathrm{IWORK}\left(\mathbf{N}+1\right)$ – INTEGER arrayWorkspace

8:     $\mathrm{WORK}\left(13\times \mathbf{N}\right)$ – REAL (KIND=nag_wp) arrayWorkspace

9:     $\mathrm{IUSER}\left(*\right)$ – INTEGER arrayUser Workspace

10:   $\mathrm{RUSER}\left(*\right)$ – REAL (KIND=nag_wp) arrayUser Workspace

IUSER and RUSER are not used by E04DGF/E04DGA, but are passed directly to OBJFUN and may be used to pass information to this routine as an alternative to using COMMON global variables.

11:   $\mathrm{IFAIL}$ – INTEGERInput/Output

Note: for E04DGA, IFAIL does not occur in this position in the parameter list. See the additional parameters described below.

On entry: IFAIL must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, because for this routine the values of the output parameters may be useful even if $\mathbf{IFAIL}\ne \mathbf{0}$ on exit, the recommended value is $-1$. When the value $-\mathbf{1}\text{ or }1$ is used it is essential to test the value of IFAIL on exit.

On exit: $\mathbf{IFAIL}=\mathbf{0}$ unless the routine detects an error or a warning has been flagged (see Section 6).

E04DGF/E04DGA returns with $\mathbf{IFAIL}=\mathbf{0}$ if the following three conditions are satisfied:

(i)	$F_{k-1}-F_k<{\tau }_F\left(1+\left|F_k\right|\right)$
(ii)	$‖x_{k-1}-x_k‖<\sqrt{{\tau }_F}\left(1+‖x_k‖\right)$
(iii)	$‖g_k‖\le \sqrt[3]{{\tau }_F}\left(1+\left|F_k\right|\right)$ or $‖g_k‖<{\epsilon }_A$

where ${\tau }_F$ is the value of the optional parameter Optimality Tolerance ($\text{default value}={\epsilon }^{0.8}$) and ${\epsilon }_A$ is the absolute error associated with computing the objective function.

For a full discussion on termination criteria see Chapter 8 of Gill et al. (1981).

Note: the following are additional parameters for specific use with E04DGA. Users of E04DGF therefore need not read the remainder of this description.

11:   $\mathrm{LWSAV}\left(120\right)$ – LOGICAL arrayCommunication Array

12:   $\mathrm{IWSAV}\left(610\right)$ – INTEGER arrayCommunication Array

13:   $\mathrm{RWSAV}\left(475\right)$ – REAL (KIND=nag_wp) arrayCommunication Array

The arrays LWSAV, IWSAV and RWSAV must not be altered between calls to any of the routines E04DGA, E04DJA, E04DKA or E04WBF.

14:   $\mathrm{IFAIL}$ – INTEGERInput/Output

Note: see the parameter description for IFAIL above.

6  Error Indicators and Warnings

$\mathbf{IFAIL}<0$

A negative value of IFAIL indicates an exit from E04DGF/E04DGA because you set $\mathbf{MODE}<0$ in OBJFUN. The value of IFAIL will be the same as your setting of MODE.

$\mathbf{IFAIL}=1$

Not used by this routine.

$\mathbf{IFAIL}=2$

Not used by this routine.

$\mathbf{IFAIL}=3$

The limiting number of iterations (as determined by the optional parameter Iteration Limit ($\text{default value}=\max \left(50,5n\right)$) has been reached.

If the algorithm appears to be making satisfactory progress, then optional parameter Iteration Limit may be too small. If so, increase its value and rerun E04DGF/E04DGA. If the algorithm seems to be making little or no progress, then you should check for incorrect gradients as described under $\mathbf{IFAIL}=\mathbf{7}$.

$\mathbf{IFAIL}=4$

The computed upper bound on the step length taken during the linesearch was too small. A rerun with an increased value of the optional parameter Maximum Step Length ($\rho$ say) may be successful unless $\rho \ge {10}^{20}$ (the default value), in which case the current point cannot be improved upon.

$\mathbf{IFAIL}=5$

Not used by this routine.

$\mathbf{IFAIL}=6$

The conditions for an acceptable solution (see parameter IFAIL in Section 5) have not all been met, but a lower point could not be found.

If OBJFUN computes the objective function and its gradient correctly, then this may occur because an overly stringent accuracy has been requested, i.e., the value of the optional parameter Optimality Tolerance ($\text{default value}={\epsilon }^{0.8}$) is too small or if ${\alpha }_k\simeq 0$. In this case you should apply the three tests described under $\mathbf{IFAIL}=\mathbf{0}$ to determine whether or not the final solution is acceptable. For a discussion of attainable accuracy see Gill et al. (1981).

If many iterations have occurred in which essentially no progress has been made or E04DGF/E04DGA has failed to move from the initial point, OBJFUN may be incorrect. You should refer to the comments below under $\mathbf{IFAIL}=\mathbf{7}$ and check the gradients using the optional parameter Verify ($\text{default value}=0$). Unfortunately, there may be small errors in the objective gradients that cannot be detected by the verification process. Finite difference approximations to first derivatives are catastrophically affected by even small inaccuracies.

$\mathbf{IFAIL}=7$

The user-supplied derivatives of the objective function appear to be incorrect.

Large errors were found in the derivatives of the objective function. This value of IFAIL will occur if the verification process indicated that at least one gradient element had no correct figures. You should refer to the printed output to determine which elements are suspected to be in error.

As a first step, you should check that the code for the objective values is correct – for example, by computing the function at a point where the correct value is known. However, care should be taken that the chosen point fully tests the evaluation of the function. It is remarkable how often the values $x=0$ or $x=1$ are used to test function evaluation procedures, and how often the special properties of these numbers make the test meaningless.

Special care should be used in this test if computation of the objective function involves subsidiary data communicated in COMMON storage. Although the first evaluation of the function may be correct, subsequent calculations may be in error because some of the subsidiary data has accidentally been overwritten.

Errors in programming the function may be quite subtle in that the function value is almost correct. For example, the function may not be accurate to full precision because of the inaccurate calculation of a subsidiary quantity, or the limited accuracy of data upon which the function depends. A common error on machines where numerical calculations are usually performed in double precision is to include even one single precision constant in the calculation of the function; since some compilers do not convert such constants to double precision, half the correct figures may be lost by such a seemingly trivial error.

$\mathbf{IFAIL}=8$

The gradient $\left(g=\frac{\partial F}{\partial x}\right)$ at the starting point $x_0$ is ‘too small’. More precisely, the value of $g{\left(x_0\right)}^{\mathrm{T}}g\left(x_0\right)$ is less than ${\epsilon }_r\left|1+F\left(x_0\right)\right|$, where ${\epsilon }_r$ is the value of the optional parameter Function Precision ($\text{default value}={\epsilon }^{0.9}$).

The problem should be rerun from a different starting point.

$\mathbf{IFAIL}=9$

An input parameter is invalid.

$\mathbf{IFAIL}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

See Section 3.8 in the Essential Introduction for further information.

$\mathbf{IFAIL}=-399$

Your licence key may have expired or may not have been installed correctly.

See Section 3.7 in the Essential Introduction for further information.

$\mathbf{IFAIL}=-999$

Dynamic memory allocation failed.

See Section 3.6 in the Essential Introduction for further information.

7  Accuracy

8  Parallelism and Performance

9  Further Comments

9.1  Description of Printed Output

10  Example

10.1  Program Text

Program Text (e04dgfe.f90)

Program Text (e04dgae.f90)

10.2  Program Data

Program Data (e04dgfe.d)

Program Data (e04dgae.d)

10.3  Program Results

Program Results (e04dgfe.r)

Program Results (e04dgae.r)

11  Algorithmic Details

12  Optional Parameters

• Defaults
• Estimated Optimal Function Value
• Function Precision
• Iteration Limit
• Iters
• Itns
• Linesearch Tolerance
• List
• Maximum Step Length
• Nolist
• Optimality Tolerance
• Print Level
• Start Objective Check at Variable
• Stop Objective Check at Variable
• Verify
• Verify Gradients
• Verify Level
• Verify Objective Gradients

Begin
   Print Level = 1
End

 CALL E04DJF (IOPTNS, INFORM)

 CALL E04DKF ('Print Level = 1')

12.1  Description of the Optional Parameters

• the keywords, where the minimum abbreviation of each keyword is underlined (if no characters of an optional qualifier are underlined, the qualifier may be omitted);
• a parameter value, where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively;
• the default value, where the symbol $\epsilon$ is a generic notation for machine precision (see X02AJF), and ${\epsilon }_r$ denotes the relative precision of the objective function Function Precision.