nag_opt_sparse_nlp_jacobian (e04vjc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_opt_sparse_nlp_jacobian (e04vjc)

 Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_opt_sparse_nlp_jacobian (e04vjc) may be used before nag_opt_sparse_nlp_solve (e04vhc) to determine the sparsity pattern for the Jacobian.

2  Specification

#include <nag.h>
#include <nage04.h>
void  nag_opt_sparse_nlp_jacobian (Integer nf, Integer n,
void (*usrfun)(Integer *status, Integer n, const double x[], Integer needf, Integer nf, double f[], Integer needg, Integer leng, double g[], Nag_Comm *comm),
Integer iafun[], Integer javar[], double a[], Integer lena, Integer *nea, Integer igfun[], Integer jgvar[], Integer leng, Integer *neg, const double x[], const double xlow[], const double xupp[], Nag_E04State *state, Nag_Comm *comm, NagError *fail)

3  Description

When using nag_opt_sparse_nlp_solve (e04vhc), if you set the optional argument Derivative Option=0 and usrfun provides none of the derivatives, you may need to call nag_opt_sparse_nlp_jacobian (e04vjc) 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
e04vgc (&state, ... );
e04vjc (nf, n, ... );
e04vlc ("Derivative Option = 0", &state, ... );
e04vhc (start, nf, ... );
nag_opt_sparse_nlp_jacobian (e04vjc) determines the sparsity pattern for the Jacobian and identifies the constant elements automatically. To do so, nag_opt_sparse_nlp_jacobian (e04vjc) 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, nag_opt_sparse_nlp_jacobian (e04vjc) 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 nag_opt_sparse_nlp_jacobian (e04vjc) must classify them as nonlinear. This is because nag_opt_sparse_nlp_solve (e04vhc) ‘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 nag_opt_sparse_nlp_solve (e04vhc).

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  Arguments

Note: all optional arguments are described in detail in Section 12.1 in nag_opt_sparse_nlp_solve (e04vhc).
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 arguments 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 function, supplied by the userExternal Function
usrfun must define the problem functions Fx . This function is passed to nag_opt_sparse_nlp_jacobian (e04vjc) as the external argument usrfun.
The specification of usrfun is:
void  usrfun (Integer *status, Integer n, const double x[], Integer needf, Integer nf, double f[], Integer needg, Integer leng, double g[], Nag_Comm *comm)
1:     status Integer *Input/Output
On entry: indicates the first call to usrfun.
status=0
There is nothing special about the current call to usrfun.
status=1
nag_opt_sparse_nlp_jacobian (e04vjc) is calling your function 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).
nag_opt_sparse_nlp_jacobian (e04vjc) 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 , nag_opt_sparse_nlp_jacobian (e04vjc) 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 nag_opt_sparse_nlp_jacobian (e04vjc).
3:     x[n] const doubleInput
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] doubleInput/Output
On entry: this will be set by nag_opt_sparse_nlp_jacobian (e04vjc).
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. nag_opt_sparse_nlp_jacobian (e04vjc) 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: nag_opt_sparse_nlp_jacobian (e04vjc) will call usrfun with needg=0 to indicate that g is not required.
8:     leng IntegerInput
On entry: the dimension of the array g.
9:     g[leng] doubleInput/Output
On entry: concerns the calculations of the derivatives of the function fx .
On exit: nag_opt_sparse_nlp_jacobian (e04vjc) will always call usrfun with needg=0 : g is not required to be set on exit but must be declared correctly.
10:   comm Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to usrfun.
userdouble *
iuserInteger *
pPointer 
The type Pointer will be void *. Before calling nag_opt_sparse_nlp_jacobian (e04vjc) you may allocate memory and initialize these pointers with various quantities for use by usrfun when called from nag_opt_sparse_nlp_jacobian (e04vjc) (see Section 3.2.1.1 in the Essential Introduction).
4:     iafun[lena] IntegerOutput
5:     javar[lena] IntegerOutput
6:     a[lena] doubleOutput
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 iafun[k-1],javar[k-1],a[k-1]  define the row and column indices i=iafun[k-1]  and j=javar[k-1]  of the element Aij=a[k-1] .
7:     lena IntegerInput
On entry: the dimension of the arrays iafun, javar and a that hold i,j,Aij. lena should be an overestimate of the number of elements in the linear part of the Jacobian.
Constraint: lena1.
8:     nea Integer *Output
On exit: is the number of nonzero entries in A  such that Fx=fx + Ax .
9:     igfun[leng] IntegerOutput
10:   jgvar[leng] IntegerOutput
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. leng should be an overestimate of the number of elements in the nonlinear part of the Jacobian.
Constraint: leng1.
12:   neg Integer *Output
On exit: the number of nonzero entries in G .
13:   x[n] const doubleInput
On entry: an initial estimate of the variables x . The contents of x  will be used by nag_opt_sparse_nlp_jacobian (e04vjc) in the call of usrfun, and so each element of x should be within the bounds given by xlow and xupp.
14:   xlow[n] const doubleInput
15:   xupp[n] const doubleInput
On entry: contain the lower and upper bounds lx  and ux  on the variables x .
To specify a nonexistent lower bound lx j =- , set xlow[j-1] -bigbnd , where bigbnd  is the optional argument Infinite Bound Size. To specify a nonexistent upper bound xupp[j-1] bigbnd .
To fix the j th variable (say, xj=β , where β < bigbnd ), set xlow[j-1]=xupp[j-1]=β .
16:   state Nag_E04State *Communication Structure
state contains internal information required for functions in this suite. It must not be modified in any way.
17:   comm Nag_Comm *
The NAG communication argument (see Section 3.2.1.1 in the Essential Introduction).
18:   fail NagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

6  Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.2.1.2 in the Essential Introduction for further information.
NE_ALLOC_INSUFFICIENT
Internal memory allocation was insufficient. Please contact NAG.
NE_ARRAY_TOO_SMALL
Either lena or leng is too small. Increase both of them and corresponding array sizes. lena=value and leng=value.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_E04VGC_NOT_INIT
The initialization function nag_opt_sparse_nlp_init (e04vgc) has not been called.
NE_INT
On entry, lena=value.
Constraint: lena1.
On entry, leng=value.
Constraint: leng1.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
An unexpected error has been triggered by this function. Please contact NAG.
See Section 3.6.6 in the Essential Introduction for further information.
NE_JACOBIAN_STRUCTURE_FAIL
Cannot estimate Jacobian structure at given point x.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 3.6.5 in the Essential Introduction for further information.
NE_USER_STOP
User-supplied function usrfun requested termination.
You have indicated the wish to terminate the call to nag_opt_sparse_nlp_jacobian (e04vjc) by setting status to a value <-1 on exit from usrfun.
NE_USRFUN_UNDEFINED
User-supplied function usrfun indicates that functions are undefined near given point x.
You have indicated that the problem functions are undefined by setting status=-1  on exit from usrfun. This exit occurs if nag_opt_sparse_nlp_jacobian (e04vjc) is unable to find a point at which the functions are defined.

7  Accuracy

Not applicable.

8  Parallelism and Performance

nag_opt_sparse_nlp_jacobian (e04vjc) is not threaded by NAG in any implementation.
nag_opt_sparse_nlp_jacobian (e04vjc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9  Further Comments

None.

10  Example

This example shows how to call nag_opt_sparse_nlp_jacobian (e04vjc) to determine the sparsity pattern of the Jacobian before calling nag_opt_sparse_nlp_solve (e04vhc) 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  

10.1  Program Text

Program Text (e04vjce.c)

10.2  Program Data

Program Data (e04vjce.d)

10.3  Program Results

Program Results (e04vjce.r)


nag_opt_sparse_nlp_jacobian (e04vjc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

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