NAG Library Routine Document

e04dgf  (uncon_conjgrd_comp_old)
e04dga (uncon_conjgrd_comp)

1

Purpose

2

Specification

2.1

Specification for e04dgf

2.2

Specification for e04dga

3

Description

4

References

5

Arguments

1:     $\mathbf{n}$ – IntegerInput

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

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

2:     $\mathbf{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:

Fortran Interface

Subroutine objfun ( mode, n, x, objf, objgrd, nstate, iuser, ruser) Integer, Intent (In) :: n, nstate Integer, Intent (Inout) :: mode, iuser(*) Real (Kind=nag_wp), Intent (In) :: x(n) Real (Kind=nag_wp), Intent (Inout) :: ruser(*) Real (Kind=nag_wp), Intent (Out) :: objf, objgrd(n)

C Header Interface

#include <nagmk26.h> void  objfun (Integer *mode, const Integer *n, const double x[], double *objf, double objgrd[], const Integer *nstate, Integer iuser[], double ruser[])

1:     $\mathbf{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:     $\mathbf{n}$ – IntegerInput

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

3:     $\mathbf{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:     $\mathbf{objf}$ – Real (Kind=nag_wp)Output

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

5:     $\mathbf{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:     $\mathbf{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:     $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

8:     $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

objfun is called with the arguments iuser and ruser as supplied to e04dgf/e04dga. You should use the arrays iuser and ruser to supply information to objfun.

objfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which e04dgf/e04dga is called. Arguments denoted as Input must not be changed by this procedure.

Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e04dgf/e04dga. If your code inadvertently does return any NaNs or infinities, e04dgf/e04dga is likely to produce unexpected results.

objfun should be tested separately before being used in conjunction with e04dgf/e04dga. See also the description of the optional parameter Verify.

3:     $\mathbf{iter}$ – IntegerOutput

On exit: the total number of iterations performed.

4:     $\mathbf{objf}$ – Real (Kind=nag_wp)Output

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

5:     $\mathbf{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:     $\mathbf{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:     $\mathbf{iwork}\left(\mathbf{n}+1\right)$ – Integer arrayWorkspace

8:     $\mathbf{work}\left(13\times \mathbf{n}\right)$ – Real (Kind=nag_wp) arrayWorkspace

9:     $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

10:   $\mathbf{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.

11:   $\mathbf{ifail}$ – IntegerInput/Output

Note: for e04dga, ifail does not occur in this position in the argument list. See the additional arguments described below.

On entry: ifail must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation 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 arguments 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 arguments for specific use with e04dga. Users of e04dgf therefore need not read the remainder of this description.

11:   $\mathbf{lwsav}\left(120\right)$ – Logical arrayCommunication Array

12:   $\mathbf{iwsav}\left(610\right)$ – Integer arrayCommunication Array

13:   $\mathbf{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:   $\mathbf{ifail}$ – IntegerInput/Output

Note: see the argument 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, 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 argument 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 argument is invalid.

$\mathbf{ifail}=-99$

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

See Section 3.9 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-399$

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

See Section 3.8 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

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/e04dja (ioptns, inform)

Call e04dkf/e04dka ('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.

12.2

Description of Printed Output