NAG Library Function Document

nag_opt_conj_grad (e04dgc)

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

1:    $\mathbf{n}$ – IntegerInput

On entry: the number $n$ of variables.

Constraint: $\mathbf{n}\ge 1$.

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

objfun must calculate the objective function $F\left(x\right)$ and its gradient at a specified point $x$.

The specification of objfun is:

void  objfun (Integer n, const double x[], double *objf, double g[], Nag_Comm *comm)

1:    $\mathbf{n}$ – IntegerInput

On entry: the number $n$ of variables.

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

On entry: the point $x$ at which the objective function is required.

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

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

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

On exit: $\mathbf{g}\left[\mathit{i}-1\right]$ must contain the value of $\frac{\partial F}{\partial x_{\mathit{i}}}$ at the point $x$, for $\mathit{i}=1,2,\dots ,n$.

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

Pointer to structure of type $\mathrm{Nag\_Comm}$; the following members are relevant to objfun.

flag – IntegerInput/Output

On entry: $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ is always non-negative.

On exit: if objfun resets $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ to some negative number then nag_opt_conj_grad (e04dgc) will terminate immediately with the error indicator NE_USER_STOP. If fail is supplied to nag_opt_conj_grad (e04dgc) $\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 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 nag_opt_conj_grad (e04dgc) these pointers may be allocated memory and initialized with various quantities for use by objfun when called from nag_opt_conj_grad (e04dgc).

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

Note: objfun should be tested separately before being used in conjunction with nag_opt_conj_grad (e04dgc). The array x must not be changed by objfun.

3:    $\mathbf{x}\left[\mathbf{n}\right]$ – doubleInput/Output

On entry: $x_0$, an estimate of the solution point $x^{*}$.

On exit: the final estimate of the solution.

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

On exit: the value of the objective function $F\left(x\right)$ at the final iterate.

5:    $\mathbf{g}\left[\mathbf{n}\right]$ – doubleOutput

On exit: the objective gradient at the final iterate.

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

On entry/exit: a pointer to a structure of type $\mathrm{Nag\_E04\_Opt}$ whose members are optional parameters for nag_opt_conj_grad (e04dgc). 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 nag_opt_init (e04xxc) and supplied as an argument to nag_opt_conj_grad (e04dgc). However, if the optional parameters are not required the NAG defined null pointer, E04_DEFAULT, can be used in the function call.

7:    $\mathbf{comm}$ – Nag_Comm *Input/Output

Note: comm is a NAG defined type (see Section 3.3.1.1 in How to Use the NAG Library and its Documentation).

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 nag_opt_conj_grad (e04dgc); comm will then be declared internally for use in calls to user-supplied functions.

8:    $\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

6

Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.

NE_BAD_PARAM

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

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{verify\_grad}$ had an illegal value.

NE_DERIV_ERRORS

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

This value of fail will occur if the verification process indicated that at least one gradient component 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.

NE_GRAD_TOO_SMALL

The gradient at the starting point is too small, rerun the problem at a different starting point.

The value of $g{\left(x_0\right)}^{\mathrm{T}}g\left(x_0\right)$ is less than $\epsilon \left|F\left(x_o\right)\right|$, where $\epsilon$ is the machine precision.

NE_INT_ARG_LT

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

NE_INVALID_INT_RANGE_1

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

NE_INVALID_REAL_RANGE_EF

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{f\_prec}$ not valid. Correct range is $\epsilon \le \mathbf{options}\mathbf{.}\mathbf{f\_prec}<1.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{optim\_tol}$ not valid. Correct range is $〈\mathit{\text{value}}〉$ $\le \mathbf{options}\mathbf{.}\mathbf{optim\_tol}<1.0$.

NE_INVALID_REAL_RANGE_F

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_line\_step}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{max\_line\_step}>0.0$.

NE_INVALID_REAL_RANGE_FF

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

NE_NOT_APPEND_FILE

Cannot open file $〈\mathit{string}〉$ for appending.

NE_NOT_CLOSE_FILE

Cannot close file $〈\mathit{string}〉$.

NE_OPT_NOT_INIT

Options structure not initialized.

NE_USER_STOP

User requested termination, user flag value $=〈\mathit{\text{value}}〉$.

This exit occurs if you set $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ to a negative value in objfun. 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 $〈\mathit{string}〉$.

NW_NO_IMPROVEMENT

A sufficient decrease in the function value could not be attained during the final linesearch. Current point cannot be improved upon.

If objfun computes the function and gradients correctly, then this warning may occur because an overly stringent accuracy has been requested, i.e., $\mathbf{options}\mathbf{.}\mathbf{optim\_tol}$ is too small or if the minimum lies close to a step length of zero. In this case you should apply the tests described in Section 3 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 nag_opt_conj_grad (e04dgc) has failed to move from the initial point, then the function objfun may be incorrect. You should refer to the comments below under NE_DERIV_ERRORS and check the gradients using the $\mathbf{options}\mathbf{.}\mathbf{verify\_grad}$ argument. 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.

NW_STEP_BOUND_TOO_SMALL

Computed upper-bound on step length was too small

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

NW_TOO_MANY_ITER

The maximum number of iterations, $〈\mathit{\text{value}}〉$, have been performed.

If the algorithm appears to be making progress the value of $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$ value may be too small (see Section 11), you should increase its value and rerun nag_opt_conj_grad (e04dgc). If the algorithm seems to be ‘bogged down’, you should check for incorrect gradients or ill-conditioning as described below under NW_NO_IMPROVEMENT.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

9.1

Timing

10

Example

10.1

Program Text

Program Text (e04dgce.c)

10.2

Program Data

Program Options (e04dgce.opt)

10.3

Program Results

Program Results (e04dgce.r)

11

Optional Parameters

11.1

Optional Parameter Checklist and Default Values

11.2

Description of the Optional Parameters

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

11.3

Description of Printed Output

11.3.1

Output of results via a user-defined printing function

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

n – Integer

The number of variables.

x – double *

Points to the $\mathbf{st}\mathbf{\to }\mathbf{n}$ memory locations holding the current point $x_k$.

f – double

The value of the current objective function.

g – double *

Points to the $\mathbf{st}\mathbf{\to }\mathbf{n}$ memory locations holding the first derivatives of $F$ at the current point $x_k$.

step – double

The step $\alpha$ taken along the search direction $p_k$.

xk_norm – double

The Euclidean norm of $x_{k-1}-x_k$.

iter – Integer

The number of iterations performed by nag_opt_conj_grad (e04dgc).

nf – Integer

The cumulative number of calls made to objfun.

n – Integer

The number of variables.

x – double *

Points to the $\mathbf{st}\mathbf{\to }\mathbf{n}$ memory locations holding the initial point $x_0$.

g – double *

Points to the $\mathbf{st}\mathbf{\to }\mathbf{n}$ memory locations holding the first derivatives of $F$ at the initial point $x_0$.

gprint – Nag_GPrintSt *

Which in turn contains two substructures $\mathbf{gprint}\mathbf{\to }\mathbf{g\_chk}$, $\mathbf{gprint}\mathbf{\to }\mathbf{f\_sim}$ and a pointer to an array of substructures, $*\mathbf{gprint}\mathbf{\to }\mathbf{f\_comp}$.

g_chk – Nag_Grad_Chk_St *

This substructure contains the members:

type – Nag_GradChk 

The type of derivative check performed by nag_opt_conj_grad (e04dgc). This will be the same value as in $\mathbf{options}\mathbf{.}\mathbf{verify\_grad}$.

g_error – Integer

This member will be equal to one of the error codes NE_NOERROR or NE_DERIV_ERRORS according to whether the derivatives were found to be correct or not.

obj_start – Integer

Specifies the gradient element at which any component check started. This value will be equal to $\mathbf{options}\mathbf{.}\mathbf{obj\_check\_start}$.

obj_stop – Integer

Specifies the gradient element at which any component check ended. This value will be equal to $\mathbf{options}\mathbf{.}\mathbf{obj\_check\_stop}$.

f_sim – Nag_SimSt *

The result of a simple derivative check, $\mathbf{g\_chk}\mathbf{\to }\mathbf{type}=\mathrm{Nag\_SimpleCheck}$, will be held in this substructure which has members:

correct – Nag_Boolean

If Nag_TRUE then the objective gradient is consistent with the finite difference approximation according to a simple check.

dir_deriv – double *

The directional derivative $g{\left(x\right)}^{T}p$ where $p$ is a random vector of unit length with elements of approximately equal magnitude.

fd_approx – double *

The finite difference approximation, $\left(F\left(x+hp\right)-F\left(x\right)\right)/h$, to the directional derivative.

f_comp – Nag_CompSt *

The results of a component derivative check, $\mathbf{g\_chk}\mathbf{\to }\mathbf{type}=\mathrm{Nag\_CheckObj}$, will be held in the array of $\mathbf{st}\mathbf{\to }\mathbf{n}$ substructures of type $\mathrm{Nag\_CompSt}$ pointed to by $\mathbf{gprint}\mathbf{\to }\mathbf{f\_comp}$. The procedure for the derivative check is based on finding an interval that produces an acceptable estimate of the second derivative, and then using that estimate to compute an interval that should produce a reasonable forward-difference approximation. The gradient element is then compared with the difference approximation. (The method of finite difference interval estimation is based on Gill et al. (1983)).

correct – Nag_Boolean

If Nag_TRUE then this objective gradient component is consistent with its finite difference approximation.

hopt – double *

The optimal finite difference interval. This is dx[i] in the NAG default printout.

gdiff – double *

The finite difference approximation for this gradient component.

iter – Integer

The number of trials performed to find a suitable difference interval.

comment – char

A character string which describes the possible nature of the reason for which an estimation of the finite difference interval failed to produce a satisfactory relative condition error of the second-order difference. Possible strings are: "Constant?", "Linear or odd?", "Too nonlinear?" and "Small derivative?".

g_prt – Nag_Boolean

Will be Nag_TRUE only when the print function is called with the result of the derivative check of objfun.

it_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the result 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 nag_opt_conj_grad (e04dgc) 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.