NAG Toolbox: nag_opt_uncon_conjgrd_comp (e04dg)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

1:     $\mathrm{objfun}$ – function handle or string containing name of m-file

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

[mode, objf, objgrd, user] = objfun(mode, n, x, nstate, user)

Input Parameters

1:     $\mathrm{mode}$ – int64int32nag_int scalar

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.

2:     $\mathrm{n}$ – int64int32nag_int scalar

$n$, the number of variables.

3:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

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

4:     $\mathrm{nstate}$ – int64int32nag_int scalar

Will be $1$ on the first call of objfun by nag_opt_uncon_conjgrd_comp (e04dg), 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 global variables when $\mathbf{nstate}=1$.

5:     $\mathrm{user}$ – Any MATLAB object

objfun is called from nag_opt_uncon_conjgrd_comp (e04dg) with the object supplied to nag_opt_uncon_conjgrd_comp (e04dg).

Output Parameters

1:     $\mathrm{mode}$ – int64int32nag_int scalar

May be set to a negative value if you wish to terminate the solution to the current problem, and in this case nag_opt_uncon_conjgrd_comp (e04dg) will terminate with ifail set to mode.

2:     $\mathrm{objf}$ – double scalar

The value of the objective function at $x$.

3:     $\mathrm{objgrd}\left(\mathbf{n}\right)$ – double array

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$.

4:     $\mathrm{user}$ – Any MATLAB object

Note:  objfun should be tested separately before being used in conjunction with nag_opt_uncon_conjgrd_comp (e04dg). See also the description of the optional parameter Verify.

2:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

An initial estimate of the solution.

3:     $\mathrm{lwsav}\left(120\right)$ – logical array

4:     $\mathrm{iwsav}\left(610\right)$ – int64int32nag_int array

5:     $\mathrm{rwsav}\left(475\right)$ – double array

The arrays lwsav, iwsav and rwsav must not be altered between calls to any of the functions nag_opt_uncon_conjgrd_comp (e04dg), nag_opt_uncon_conjgrd_option_string (e04dk) or nag_opt_init (e04wb).

Optional Input Parameters

1:     $\mathrm{n}$ – int64int32nag_int scalar

Default: the dimension of the array x.

$n$, the number of variables.

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

2:     $\mathrm{user}$ – Any MATLAB object

user is not used by nag_opt_uncon_conjgrd_comp (e04dg), but is passed to objfun. Note that for large objects it may be more efficient to use a global variable which is accessible from the m-files than to use user.

Output Parameters

1:     $\mathrm{iter}$ – int64int32nag_int scalar

The total number of iterations performed.

2:     $\mathrm{objf}$ – double scalar

The value of the objective function at the final iterate.

3:     $\mathrm{objgrd}\left(\mathbf{n}\right)$ – double array

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

4:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

The final estimate of the solution.

5:     $\mathrm{user}$ – Any MATLAB object

6:     $\mathrm{lwsav}\left(120\right)$ – logical array

7:     $\mathrm{iwsav}\left(610\right)$ – int64int32nag_int array

8:     $\mathrm{rwsav}\left(475\right)$ – double array

9:     $\mathrm{ifail}$ – int64int32nag_int scalar

$\mathbf{ifail}=\mathbf{0}$ unless the function detects an error (see Error Indicators and Warnings).

nag_opt_uncon_conjgrd_comp (e04dg) 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).

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

W  $\mathbf{ifail}<0$

A negative value of ifail indicates an exit from nag_opt_uncon_conjgrd_comp (e04dg) 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 function.

   $\mathbf{ifail}=2$

Not used by this function.

   $\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 nag_opt_uncon_conjgrd_comp (e04dg). 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 function.

W  $\mathbf{ifail}=6$

The conditions for an acceptable solution (see argument ifail in Arguments) 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 nag_opt_uncon_conjgrd_comp (e04dg) 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.

W  $\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 global 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.

   $\mathbf{ifail}=-399$

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

   $\mathbf{ifail}=-999$

Dynamic memory allocation failed.

Accuracy

Further Comments

Description of Printed Output

Example

Open in the MATLAB editor: e04dg_example

function e04dg_example


fprintf('e04dg example results\n\n');

x = [-1  1];

% Initialize
[cwsav,lwsav,iwsav,rwsav,ifail] = e04wb( ...
                                         'e04dg');

% Optimize
[iter, objf, objgrd, x, user, lwsav, iwsav, rwsav, ifail] = ...
e04dg( ...
       @objfun, x, lwsav, iwsav, rwsav);

fprintf('Variable          Value     Gradient value\n');
for i=1:2
 fprintf('Varbl %3d    %12.8f    %9.1e\n', i, x(i), objgrd(i));
end
fprintf('\nFinal objective value = %15.7e\n',objf);



function [mode, objf, objgrd, user] = objfun(mode, n, x, nstate, user)

  expx1 = exp(x(1));
  objf = expx1*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);
  if (mode == 2)
    objgrd(1) = 4*expx1*(2*x(1)+x(2)) + objf;
    objgrd(2) = 2*expx1*(2*x(2)+2*x(1)+1);
  else
    objgrd = zeros(2,1);
  end

e04dg example results

Variable          Value     Gradient value
Varbl   1      0.50000001      9.1e-07
Varbl   2     -0.99999989      8.3e-07

Final objective value =   5.3083002e-14

Algorithmic Details

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

[lwsav, iwsav, rwsav, inform] = e04dk('Print Level = 1', lwsav, iwsav, rwsav);

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 nag_machine_precision (x02aj)), and ${\epsilon }_r$ denotes the relative precision of the objective function Function Precision.