E04VJF (PDF version)
E04 Chapter Contents
E04 Chapter Introduction
NAG Library Manual

NAG Library Routine Document

E04VJF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

E04VJF may be used before E04VHF to determine the sparsity pattern for the Jacobian.

2  Specification

SUBROUTINE E04VJF ( NF, N, USRFUN, IAFUN, JAVAR, A, LENA, NEA, IGFUN, JGVAR, LENG, NEG, X, XLOW, XUPP, CW, LENCW, IW, LENIW, RW, LENRW, CUSER, IUSER, RUSER, IFAIL)
INTEGER  NF, N, IAFUN(LENA), JAVAR(LENA), LENA, NEA, IGFUN(LENG), JGVAR(LENG), LENG, NEG, LENCW, IW(LENIW), LENIW, LENRW, IUSER(*), IFAIL
REAL (KIND=nag_wp)  A(LENA), X(N), XLOW(N), XUPP(N), RW(LENRW), RUSER(*)
CHARACTER(8)  CW(LENCW), CUSER(*)
EXTERNAL  USRFUN

3  Description

When using E04VHF, if you set the optional parameter Derivative Option=0 and USRFUN provides none of the derivatives, you may need to call E04VJF to determine the input arrays IAFUN, JAVAR, A, IGFUN and JGVAR. These arrays define the pattern of nonzeros in the Jacobian matrix. A typical sequence of calls could be
CALL E04VGF (CW, LENCW, ... )
CALL E04VJF (NF, N, ... )
CALL E04VLF ('Derivative Option = 0', CW, ... )
CALL E04VHF (START, NF, ... )
E04VJF determines the sparsity pattern for the Jacobian and identifies the constant elements automatically. To do so, E04VJF approximates the problem functions, Fx , at three random perturbations of the given initial point x . If an element of the approximate Jacobian is the same at all three points, then it is taken to be constant. If it is zero, it is taken to be identically zero. Since the random points are not chosen close together, the heuristic will correctly classify the Jacobian elements in the vast majority of cases. In general, E04VJF finds that the Jacobian can be permuted to the form:
Gx A3 A2 A4 ,
where A2 , A3  and A4  are constant. Note that Gx  might contain elements that are also constant, but E04VJF must classify them as nonlinear. This is because E04VHF ‘removes’ linear variables from the calculation of F  by setting them to zero before calling USRFUN. A knowledgeable user would be able to move such elements from Fx  in USRFUN and enter them as part of IAFUN, JAVAR and A for E04VHF.

4  References

Hock W and Schittkowski K (1981) Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems 187 Springer–Verlag

5  Parameters

Note: all optional parameters are described in detail in Section 11.1 in E04VHF.
1:     NF – INTEGERInput
On entry: nf, the number of problem functions in Fx , including the objective function (if any) and the linear and nonlinear constraints. Simple upper and lower bounds on x  can be defined using the parameters XLOW and XUPP and should not be included in F .
Constraint: NF>0.
2:     N – INTEGERInput
On entry: n, the number of variables.
Constraint: N>0.
3:     USRFUN – SUBROUTINE, supplied by the user.External Procedure
USRFUN must define the problem functions Fx . This subroutine is passed to E04VJF as the external parameter USRFUN.
The specification of USRFUN is:
SUBROUTINE USRFUN ( STATUS, N, X, NEEDF, NF, F, NEEDG, LENG, G, CUSER, IUSER, RUSER)
INTEGER  STATUS, N, NEEDF, NF, NEEDG, LENG, IUSER(*)
REAL (KIND=nag_wp)  X(N), F(NF), G(LENG), RUSER(*)
CHARACTER(8)  CUSER(*)
1:     STATUS – INTEGERInput/Output
On entry: indicates the first call to USRFUN.
STATUS=0
There is nothing special about the current call to USRFUN.
STATUS=1
E04VJF is calling your subroutine for the first time. Some data may need to be input or computed and saved.
On exit: may be used to indicate that you are unable to evaluate F  at the current x . (For example, the problem functions may not be defined there).
E04VJF evaluates Fx  at random perturbation of the initial point x , say xp . If the functions cannot be evaluated at xp , you can set STATUS=-1 , E04VJF will use another random perturbation.
If for some reason you wish to terminate the current problem, set STATUS-2 .
2:     N – INTEGERInput
On entry: n , the number of variables, as defined in the call to E04VJF.
3:     X(N) – REAL (KIND=nag_wp) arrayInput
On entry: the variables x  at which the problem functions are to be calculated. The array x  must not be altered.
4:     NEEDF – INTEGERInput
On entry: indicates if F must be assigned during the call to USRFUN (see F).
5:     NF – INTEGERInput
On entry: nf, the number of problem functions.
6:     F(NF) – REAL (KIND=nag_wp) arrayInput/Output
On entry: this will be set by E04VJF.
On exit: the computed Fx  according to the setting of NEEDF.
If NEEDF=0 , F is not required and is ignored.
If NEEDF > 0 , the components of Fx  must be calculated and assigned to F. E04VJF will always call USRFUN with NEEDF>0 .
To simplify the code, you may ignore the value of NEEDF and compute Fx  on every entry to USRFUN.
7:     NEEDG – INTEGERInput
On entry: E04VJF will call USRFUN with NEEDG=0 to indicate that G is not required.
8:     LENG – INTEGERInput
On entry: the dimension of the array G as declared in the (sub)program from which E04VJF is called.
9:     G(LENG) – REAL (KIND=nag_wp) arrayInput/Output
On entry: concerns the calculations of the derivatives of the function fx .
On exit: E04VJF will always call USRFUN with NEEDG=0 : G is not required to be set on exit but must be declared correctly.
10:   CUSER(*) – CHARACTER(8) arrayUser Workspace
11:   IUSER(*) – INTEGER arrayUser Workspace
12:   RUSER(*) – REAL (KIND=nag_wp) arrayUser Workspace
USRFUN is called with the parameters CUSER, IUSER and RUSER as supplied to E04VJF. You are free to use the arrays CUSER, IUSER and RUSER to supply information to USRFUN as an alternative to using COMMON global variables.
USRFUN must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which E04VJF is called. Parameters denoted as Input must not be changed by this procedure.
4:     IAFUN(LENA) – INTEGER arrayOutput
5:     JAVAR(LENA) – INTEGER arrayOutput
6:     A(LENA) – REAL (KIND=nag_wp) arrayOutput
On exit: define the coordinates i,j  and values Aij  of the nonzero elements of the linear part A  of the function Fx=fx + Ax .
In particular, NEA triples IAFUNk,JAVARk,Ak  define the row and column indices i=IAFUNk  and j=JAVARk  of the element Aij=Ak .
7:     LENA – INTEGERInput
On entry: the dimension of the arrays IAFUN, JAVAR and A that hold i,j,Aij as declared in the (sub)program from which E04VJF is called. LENA should be an overestimate of the number of elements in the linear part of the Jacobian.
Constraint: LENA1.
8:     NEA – INTEGEROutput
On exit: is the number of nonzero entries in A  such that Fx=fx + Ax .
9:     IGFUN(LENG) – INTEGER arrayOutput
10:   JGVAR(LENG) – INTEGER arrayOutput
On exit: define the coordinates i,j  of the nonzero elements of G , the nonlinear part of the derivatives Jx=Gx + A  of the function Fx=fx + Ax .
11:   LENG – INTEGERInput
On entry: the dimension of the arrays IGFUN and JGVAR that define the varying Jacobian elements i,j,Gij as declared in the (sub)program from which E04VJF is called. LENG should be an overestimate of the number of elements in the nonlinear part of the Jacobian.
Constraint: LENG1.
12:   NEG – INTEGEROutput
On exit: the number of nonzero entries in G .
13:   X(N) – REAL (KIND=nag_wp) arrayInput
On entry: an initial estimate of the variables x . The contents of x  will be used by E04VJF in the call of USRFUN, and so each element of X should be within the bounds given by XLOW and XUPP.
14:   XLOW(N) – REAL (KIND=nag_wp) arrayInput
15:   XUPP(N) – REAL (KIND=nag_wp) arrayInput
On entry: contain the lower and upper bounds lx  and ux  on the variables x .
To specify a nonexistent lower bound lx j =- , set XLOWj -bigbnd , where bigbnd  is the optional parameter Infinite Bound Size. To specify a nonexistent upper bound XUPPj bigbnd .
To fix the j th variable (say, xj=β , where β < bigbnd ), set XLOWj=XUPPj=β .
16:   CW(LENCW) – CHARACTER(8) arrayCommunication Array
17:   LENCW – INTEGERInput
On entry: the dimension of the array CW as declared in the (sub)program from which E04VJF is called.
Constraint: LENCW600.
18:   IW(LENIW) – INTEGER arrayCommunication Array
19:   LENIW – INTEGERInput
On entry: the dimension of the array IW as declared in the (sub)program from which E04VJF is called.
Constraint: LENIW600.
20:   RW(LENRW) – REAL (KIND=nag_wp) arrayCommunication Array
21:   LENRW – INTEGERInput
On entry: the dimension of the array RW as declared in the (sub)program from which E04VJF is called.
Constraint: LENRW600.
22:   CUSER(*) – CHARACTER(8) arrayUser Workspace
23:   IUSER(*) – INTEGER arrayUser Workspace
24:   RUSER(*) – REAL (KIND=nag_wp) arrayUser Workspace
CUSER, IUSER and RUSER are not used by E04VJF, but are passed directly to USRFUN and may be used to pass information to this routine as an alternative to using COMMON global variables.
25:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to 0, -1​ 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​ or ​1 is recommended. If the output of error messages is undesirable, then the value 1 is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is 0. When the value -1​ or ​1 is used it is essential to test the value of IFAIL on exit.
On exit: IFAIL=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6  Error Indicators and Warnings

If on entry IFAIL=0 or -1, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
IFAIL=1
The initialization routine E04VGF has not been called or at least one of LENCW, LENIW or LENRW is less than 600.
IFAIL=2
An input parameter is invalid. The output message provides more details of the invalid parameter.
IFAIL=3
Undefined user-supplied function.
You have indicated that the problem functions are undefined by setting STATUS=-1  on exit from USRFUN. This exit occurs if E04VJF is unable to find a point at which the functions are defined.
IFAIL=4
User requested termination.
You have indicated the wish to terminate the call to E04VJF by setting STATUS to a value <-1 on exit from USRFUN.
IFAIL=5
Either LENA or LENG is too small, resulting in insufficient array to store the Jacobian information. Increase LENA and/or LENG
IFAIL=6
Unable to estimate the Jacobian structure.
IFAIL=7
Internal memory allocation failed when attempting to obtain the required workspace. Please contact NAG.
IFAIL=8
Internal memory allocation insufficient. Please contact NAG.

7  Accuracy

Not applicable.

8  Further Comments

None.

9  Example

This example shows how to call E04VJF to determine the sparsity pattern of the Jacobian before calling E04VHF to solve a sparse nonlinear programming problem without providing the Jacobian information in USRFUN.
It is a reformulation of Problem 74 from Hock and Schittkowski (1981) and involves the minimization of the nonlinear function
fx = 10-6 x33 + 23 × 10-6 x43+3 x3+2 x4
subject to the bounds
-0.55x1 0.55, -0.55x2 0.55, 0x3 1200, 0x4 1200,
to the nonlinear constraints
1000sin-x1-0.25+1000sin-x2-0.25-x3 = -894.8, 1000sinx1-0.25+1000sinx1-x2-0.25-x4 = -894.8, 1000sinx2-0.25+1000sinx2-x1-0.25 = -1294.8,
and to the linear constraints
-x1+x2-0.55, -x1-x2-0.55.
The initial point, which is infeasible, is
x0 = 0, 0, 0, 0 T ,
and fx0=0.
The optimal solution (to five figures) is
x*=0.11887,-0.39623,679.94,1026.0T,
and fx*=5126.4. All the nonlinear constraints are active at the solution.
The formulation of the problem combines the constraints and the objective into a single vector ( F ).
F = 1000 sin -x1 - 0.25 + 1000 sin -x2 - 0.25 - x3 1000 sin x1 - 0.25 + 1000 sin x1 - x2 - 0.25 - x4 1000 sin x2 - 0.25 + 1000 sin x2 - x1 - 0.25 -x1 + x2 x1 - x2 10-6 x33 + 23 × 10-6 x43 + 3x3 + 2x4

9.1  Program Text

Program Text (e04vjfe.f90)

9.2  Program Data

Program Data (e04vjfe.d)

9.3  Program Results

Program Results (e04vjfe.r)


E04VJF (PDF version)
E04 Chapter Contents
E04 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012