NAG FL Interface
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}$ – Integer Input

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

void  objfun_ (Integer *mode, const Integer *n, const double x[], double *objf, double objgrd[], const Integer *nstate, Integer iuser[], double ruser[])

C++ Header Interface

#include <nag.h> extern "C" { void  objfun_ (Integer &mode, const Integer &n, const double x[], double &objf, double objgrd[], const Integer &nstate, Integer iuser[], double ruser[]) }

1: $\mathbf{mode}$ – Integer Input/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}$ – Integer Input

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

3: $\mathbf{x}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) array Input

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) array Output

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}$ – Integer Input

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 blocks when $\mathbf{nstate}=1$.

7: $\mathbf{iuser}\left(*\right)$ – Integer array User Workspace

8: $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array User 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}$ – Integer Output

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) array Output

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) array Input/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 array Workspace

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

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

10: $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) array User 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}$ – Integer Input/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 4 in the Introduction to the NAG Library FL Interface 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:

1. (i)$F_{k-1}-F_k<{\tau }_F\left(1+\left|F_k\right|\right)$
2. (ii)$‖x_{k-1}-x_k‖<\sqrt{{\tau }_F}\left(1+‖x_k‖\right)$
3. (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 array Communication Array

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

13: $\mathbf{rwsav}\left(475\right)$ – Real (Kind=nag_wp) array Communication 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}$ – Integer Input/Output

Note: see the argument description for ifail above.

6 Error Indicators and Warnings

$\mathbf{ifail}<0$

User requested termination.

$\mathbf{ifail}=3$

Too many iterations.

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$

Computed upper bound on step length is 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}=6$

Current point cannot be improved upon.

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$

Large errors found in the derivatives.

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.

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$

Gradient at the starting point is too small.

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$

On entry, $\mathbf{n}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{n}>0$.

$\mathbf{ifail}=-99$

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

See Section 7 in the Introduction to the NAG Library FL Interface for further information.

$\mathbf{ifail}=-399$

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

See Section 8 in the Introduction to the NAG Library FL Interface for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

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