NAG Toolbox: nag_opt_nlp2_sparse_solve (e04vh)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

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

Indicates how a starting point is to be obtained.

$\mathbf{start}=0$

Requests that the Crash procedure be used, unless a Basis file is provided via optional parameters Old Basis File, Insert File or Load File.

$\mathbf{start}=1$

Is the same as $\mathbf{start}=0$ but is more meaningful when a Basis file is given.

$\mathbf{start}=2$

Means that xstate and fstate define a valid starting point (probably from an earlier call, though not necessarily).

Constraint: $\mathbf{start}=0$, $1$ or $2$.

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

Is a constant that will be added to the objective row $F_{\mathrm{obj}}$ for printing purposes. Typically, $\mathbf{objadd}=0.0$.

3:     $\mathrm{objrow}$ – int64int32nag_int scalar

Says which row of $F\left(x\right)$ is to act as the objective function. If there is no such row, set $\mathbf{objrow}=0$. Then nag_opt_nlp2_sparse_solve (e04vh) will seek a feasible point such that $l_F\le F\left(x\right)\le u_F$ and $l_x\le x\le u_x$.

Constraint: $1\le \mathbf{objrow}\le \mathbf{nf}\text{ or }\mathbf{objrow}=0$ (or a feasible point problem).

4:     $\mathrm{prob}$ – string (length at least 8) (length ≥ 8)

Is an $8$-character name for the problem. prob is used in the printed solution and in some functions that output Basis files. A blank name may be used.

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

usrfun must define the nonlinear portion $f\left(x\right)$ of the problem functions $F\left(x\right)=f\left(x\right)+Ax$, along with its gradient elements $G_{ij}\left(x\right)=\frac{\partial f_i\left(x\right)}{\partial x_j}$. (A dummy function is needed even if $f\equiv 0$ and all functions are linear.)

In general, usrfun should return all function and gradient values on every entry except perhaps the last. This provides maximum reliability and corresponds to the default option setting, $\mathbf{Derivative\; Option}=1$.

The elements of $G\left(x\right)$ are stored in the array $\mathbf{g}\left(1:\mathbf{leng}\right)$ in the order specified by the input arrays igfun and jgvar.

In practice it is often convenient not to code gradients. nag_opt_nlp2_sparse_solve (e04vh) is able to estimate them by finite differences, using a call to usrfun for each variable $x_j$ for which some $\frac{\partial f_i\left(x\right)}{\partial x_j}$ needs to be estimated. However, this reduces the reliability of the optimization algorithm, and it can be very expensive if there are many such variables $x_j$.

As a compromise, nag_opt_nlp2_sparse_solve (e04vh) allows you to code as many gradients as you like. This option is implemented as follows. Just before usrfun is called, each element of the derivative array g is initialized to a specific value. On exit, any element retaining that value must be estimated by finite differences.

Some rules of thumb follow:

(i)	for maximum reliability, compute all gradients;
(ii)	if the gradients are expensive to compute, specify optional parameter Nonderivative Linesearch and use the value of the input argument needg to avoid computing them on certain entries. (There is no need to compute gradients if $\mathbf{needg}=0$ on entry to usrfun.);
(iii)	if not all gradients are known, you must specify $\mathbf{Derivative\; Option}=0$. You should still compute as many gradients as you can. (It often happens that some of them are constant or zero.);
(iv)	again, if the known gradients are expensive, don't compute them if $\mathbf{needg}=0$ on entry to usrfun;
(v)	use the input argument status to test for special actions on the first or last entries;
(vi)	while usrfun is being developed, use the optional parameter Verify Level to check the computation of gradients that are supposedly known;
(vii)	usrfun is not called until the linear constraints and bounds on $x$ are satisfied. This helps confine $x$ to regions where the functions $f_i\left(x\right)$ are likely to be defined. However, be aware of the optional parameter Minor Feasibility Tolerance if the functions have singularities on the constraint boundaries;
(viii)	set $\mathbf{status}=-1$ if some of the functions are undefined. The linesearch will shorten the step and try again;
(ix)	set $\mathbf{status}\le -2$ if you want nag_opt_nlp2_sparse_solve (e04vh) to stop.

[status, f, g, user] = usrfun(status, n, x, needf, nf, f, needg, leng, g, user)

Input Parameters

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

Indicates the first and last calls to usrfun.

$\mathbf{status}=0$

There is nothing special about the current call to usrfun.

$\mathbf{status}=1$

nag_opt_nlp2_sparse_solve (e04vh) is calling your function for the first time. You may wish to do something special such as read data from a file.

$\mathbf{status}\ge 2$

nag_opt_nlp2_sparse_solve (e04vh) is calling your function for the last time. This argument setting allows you to perform some additional computation on the final solution.

$\mathbf{status}=2$

The current x is optimal.

$\mathbf{status}=3$

The problem appears to be infeasible.

$\mathbf{status}=4$

The problem appears to be unbounded.

$\mathbf{status}=5$

An iterations limit was reached.

If the functions are expensive to evaluate, it may be desirable to do nothing on the last call. The first executable statement could be

 if (status ≥ 2)
 return;
 end 

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

$n$, the number of variables, as defined in the call to nag_opt_nlp2_sparse_solve (e04vh).

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

The variables $x$ at which the problem functions are to be calculated. The array $x$ must not be altered.

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

Indicates whether f must be assigned during this call of usrfun.

$\mathbf{needf}=0$

f is not required and is ignored.

$\mathbf{needf}>0$

The components of $f\left(x\right)$ corresponding to the nonlinear part of $F\left(x\right)$ must be calculated and assigned to f.

If $F_i\left(x\right)$ is linear and completely defined by the $i$th row of $A$, $A_i^{\prime }$, then the associated value $f_i\left(x\right)$ is ignored and need not be assigned. However, if $F_i\left(x\right)$ has a nonlinear portion $f_i\left(x\right)$ that happens to be zero at $x$, then it is still necessary to set $f_i\left(x\right)=0$. If the linear part $A_i^{\prime }$ of a nonlinear $F_i\left(x\right)$ is provided using the arrays iafun, javar and a, then it must not be computed again as part of $f_i\left(x\right)$.

To simplify the code, you may ignore the value of needf and compute $f\left(x\right)$ on every entry to usrfun.

needf may also be ignored with Derivative Linesearch and $\mathbf{Derivative\; Option}=1$. In this case, needf is always $1$, and f must always be assigned.

5:     $\mathrm{nf}$ – int64int32nag_int scalar

Is the length of the full vector $F\left(x\right)=f\left(x\right)+Ax$ as defined in the call to nag_opt_nlp2_sparse_solve (e04vh).

6:     $\mathrm{f}\left(\mathbf{nf}\right)$ – double array

Concerns the calculation of $f\left(x\right)$.

7:     $\mathrm{needg}$ – int64int32nag_int scalar

Indicates whether g must be assigned during this call of usrfun.

$\mathbf{needg}=0$

g is not required and is ignored.

$\mathbf{needg}>0$

The partial derivatives of $f\left(x\right)$ must be calculated and assigned to g. The value of $\mathbf{g}\left(k\right)$ should be $\frac{\partial f_i\left(x\right)}{\partial x_j}$, where $i=\mathbf{igfun}\left(k\right)$, $j=\mathbf{jgvar}\left(k\right)$ and $k=1,2,\dots ,\mathbf{leng}$.

8:     $\mathrm{leng}$ – int64int32nag_int scalar

Is the length of the coordinate arrays jgvar and igfun in the call to nag_opt_nlp2_sparse_solve (e04vh).

9:     $\mathrm{g}\left(\mathbf{leng}\right)$ – double array

Concerns the calculations of the derivatives of the function $f\left(x\right)$.

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

usrfun is called from nag_opt_nlp2_sparse_solve (e04vh) with the object supplied to nag_opt_nlp2_sparse_solve (e04vh).

Output Parameters

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

May be used to indicate that you are unable to evaluate $f$ or its gradients at the current $x$. (For example, the problem functions may not be defined there.)

During the linesearch, $f\left(x\right)$ is evaluated at points $x=x_k+\alpha p_k$ for various step lengths $\alpha$, where $f\left(x_k\right)$ has already been evaluated satisfactorily. For any such $x$, if you set $\mathbf{status}=-1$, nag_opt_nlp2_sparse_solve (e04vh) will reduce $\alpha$ and evaluate $f$ again (closer to $x_k$, where $f\left(x_k\right)$ is more likely to be defined).

If for some reason you wish to terminate the current problem, set $\mathbf{status}\le -2$.

2:     $\mathrm{f}\left(\mathbf{nf}\right)$ – double array

f contains the computed functions $f\left(x\right)$ (except perhaps if $\mathbf{needf}=0$).

3:     $\mathrm{g}\left(\mathbf{leng}\right)$ – double array

Contains the computed derivatives $G\left(x\right)$ (unless $\mathbf{needg}=0$).

These derivative elements must be stored in g in exactly the same positions as implied by the definitions of arrays igfun and jgvar. There is no internal check for consistency (except indirectly via the optional parameter Verify Level), so great care is essential.

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

6:     $\mathrm{iafun}\left(\mathbf{lena}\right)$ – int64int32nag_int array

7:     $\mathrm{javar}\left(\mathbf{lena}\right)$ – int64int32nag_int array

Define the coordinates $\left(i,j\right)$ of the nonzero elements of the linear part $A$ of the function $F\left(x\right)=f\left(x\right)+Ax$.

In particular, nea triples $\left(\mathbf{iafun}\left(k\right),\mathbf{javar}\left(k\right),\mathbf{a}\left(k\right)\right)$ define the row and column indices $i=\mathbf{iafun}\left(k\right)$ and $j=\mathbf{javar}\left(k\right)$ of the element $A_{ij}=\mathbf{a}\left(k\right)$.

The coordinates may define the elements of $A$ in any order.

8:     $\mathrm{nea}$ – int64int32nag_int scalar

Is the number of nonzero entries in $A$ such that $F\left(x\right)=f\left(x\right)+Ax$.

Constraint: $0\le \mathbf{nea}\le \mathbf{lena}$.

9:     $\mathrm{a}\left(\mathbf{lena}\right)$ – double array

Define the values $A_{ij}$ of the nonzero elements of the linear part $A$ of the function $F\left(x\right)=f\left(x\right)+Ax$.

In particular, nea triples $\left(\mathbf{iafun}\left(k\right),\mathbf{javar}\left(k\right),\mathbf{a}\left(k\right)\right)$ define the row and column indices $i=\mathbf{iafun}\left(k\right)$ and $j=\mathbf{javar}\left(k\right)$ of the element $A_{ij}=\mathbf{a}\left(k\right)$.

The coordinates may define the elements of $A$ in any order.

10:   $\mathrm{igfun}\left(\mathbf{leng}\right)$ – int64int32nag_int array

11:   $\mathrm{jgvar}\left(\mathbf{leng}\right)$ – int64int32nag_int array

Define the coordinates $\left(i,j\right)$ of the nonzero elements of $G$, the nonlinear part of the derivative $J\left(x\right)=G\left(x\right)+A$ of the function $F\left(x\right)=f\left(x\right)+Ax$. nag_opt_nlp2_sparse_jacobian (e04vj) may be used to define these two arrays.

The coordinates can define the elements of $G$ in any order. However, usrfun must define the actual elements of g in exactly the same order as defined by the coordinates $\left(\mathbf{igfun},\mathbf{jgvar}\right)$.

12:   $\mathrm{neg}$ – int64int32nag_int scalar

The number of nonzero entries in $G$.

Constraint: $0\le \mathbf{neg}\le \mathbf{leng}$.

13:   $\mathrm{xlow}\left(\mathbf{n}\right)$ – double array

14:   $\mathrm{xupp}\left(\mathbf{n}\right)$ – double array

Contain the lower and upper bounds $l_x$ and $u_x$ on the variables $x$.

To specify a nonexistent lower bound ${\left[l_x\right]}_j=-\infty$, set $\mathbf{xlow}\left(j\right)\le -\mathit{bigbnd}$, where $\mathit{bigbnd}$ is the optional parameter Infinite Bound Size. To specify a nonexistent upper bound ${\left[u_x\right]}_j=\infty$, set $\mathbf{xupp}\left(j\right)\ge \mathit{bigbnd}$.

To fix the $j$th variable at $x_j=\beta$, where $\left|\beta \right|<\mathit{bigbnd}$, set $\mathbf{xlow}\left(j\right)=\mathbf{xupp}\left(j\right)=\beta$.

Constraint: $\mathbf{xlow}\left(\mathit{i}\right)\le \mathbf{xupp}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{n}$.

15:   $\mathrm{xnames}\left(\mathbf{nxname}\right)$ – cell array of strings

The optional names for the variables.

If $\mathbf{nxname}=1$, xnames is not referenced and default names will be used for output.

If $\mathbf{nxname}=\mathbf{n}$, $\mathbf{xnames}\left(j\right)$ should contain the $8$-character name of the $j$th variable.

16:   $\mathrm{flow}\left(\mathbf{nf}\right)$ – double array

17:   $\mathrm{fupp}\left(\mathbf{nf}\right)$ – double array

Contain the lower and upper bounds $l_F$ and $u_F$ on $F\left(x\right)$.

To specify a nonexistent lower bound ${\left[l_F\right]}_i=-\infty$, set $\mathbf{flow}\left(i\right)\le -\mathit{bigbnd}$. For a nonexistent upper bound ${\left[u_F\right]}_i=\infty$, set $\mathbf{fupp}\left(i\right)\ge \mathit{bigbnd}$.

To make the $i$th constraint an equality at $F_i=\beta$, where $\left|\beta \right|<\mathit{bigbnd}$, set $\mathbf{flow}\left(i\right)=\mathbf{fupp}\left(i\right)=\beta$.

Constraint: $\mathbf{flow}\left(\mathit{i}\right)\le \mathbf{fupp}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{n}$.

18:   $\mathrm{fnames}\left(\mathbf{nfname}\right)$ – cell array of strings

The optional names for the problem functions.

If $\mathbf{nfname}=1$, fnames is not referenced and default names will be used for output.

If $\mathbf{nfname}=\mathbf{nf}$, $\mathbf{fnames}\left(i\right)$ should contain the $8$-character name of the $i$th row of $F$.

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

An initial estimate of the variables $x$. See the following description of xstate.

20:   $\mathrm{xstate}\left(\mathbf{n}\right)$ – int64int32nag_int array

The initial state for each variable $x$.

If $\mathbf{start}=0$ or $1$ and no basis information is provided (the optional parameters Old Basis File, Insert File and Load File are all set to $0$; the default) x and xstate must be defined.

If nothing special is known about the problem, or if there is no wish to provide special information, you may set $\mathbf{x}\left(j\right)=0.0$, $\mathbf{xstate}\left(j\right)=0$, for all $j=1,2,\dots ,\mathbf{n}$. If you set $\mathbf{x}\left(j\right)=\mathbf{xlow}\left(j\right)$ set $\mathbf{xstate}\left(j\right)=4$; if you set $\mathbf{x}\left(j\right)=\mathbf{xupp}\left(j\right)$ then set $\mathbf{xstate}\left(j\right)=5$. In this case a Crash procedure is used to select an initial basis.

If $\mathbf{start}=0$ or $1$ and basis information is provided (at least one of the optional parameters Old Basis File, Insert File and Load File is nonzero) x and xstate need not be set.

If $\mathbf{start}=2$ (Warm Start), x and xstate must be set (probably from a previous call). In this case $\mathbf{xstate}\left(\mathit{j}\right)$ must be $0$, $1$, $2\text{ or }3$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$.

Constraint: $0\le \mathbf{xstate}\left(j\right)\le 5\text{, for }j=1,2,\dots ,\mathbf{n}$.

21:   $\mathrm{f}\left(\mathbf{nf}\right)$ – double array

An initial value for the problem functions $F$. See the following description of fstate.

22:   $\mathrm{fstate}\left(\mathbf{nf}\right)$ – int64int32nag_int array

The initial state for the problem functions $F$.

If $\mathbf{start}=0$ or $1$ and no basis information is provided (the optional parameters Old Basis File, Insert File and Load File are all set to $0$; the default, f and fstate must be defined.

If nothing special is known about the problem, or if there is no wish to provide special information, you may set $\mathbf{f}\left(i\right)=0.0$, $\mathbf{fstate}\left(i\right)=0$, for all $i=1,2,\dots ,\mathbf{nf}$. Less trivially, to say that the optimal value of function $\mathbf{f}\left(i\right)$ will probably be equal to one of its bounds, set $\mathbf{f}\left(i\right)=\mathbf{flow}\left(i\right)$ and $\mathbf{fstate}\left(i\right)=4$ or $\mathbf{f}\left(i\right)=\mathbf{fupp}\left(i\right)$ and $\mathbf{fstate}\left(i\right)=5$ as appropriate. In this case a Crash procedure is used to select an initial basis.

If $\mathbf{start}=0$ or $1$ and basis information is provided (at least one of the optional parameters Old Basis File, Insert File and Load File is nonzero), f and fstate need not be set.

If $\mathbf{start}=2$ (Warm Start), f and fstate must be set (probably from a previous call). In this case $\mathbf{fstate}\left(\mathit{i}\right)$ must be $0$, $1$, $2$ or $3$, for $\mathit{i}=1,2,\dots ,\mathbf{nf}$.

Constraint: $0\le \mathbf{fstate}\left(i\right)\le 5\text{, for }i=1,2,\dots ,\mathbf{nf}$.

23:   $\mathrm{fmul}\left(\mathbf{nf}\right)$ – double array

An estimate of $\gamma$, the vector of Lagrange multipliers (shadow prices) for the constraints $l_F\le F\left(x\right)\le u_F$. All nf components must be defined. If nothing is known about $\gamma$, set $\mathbf{fmul}\left(\mathit{i}\right)=0.0$, for $\mathit{i}=1,2,\dots ,\mathbf{nf}$. For warm start use the values from a previous call.

24:   $\mathrm{ns}$ – int64int32nag_int scalar

The number of superbasic variables. ns need not be specified for cold starts, but should retain its value from a previous call when warm start is used.

25:   $\mathrm{cw}\left(\mathit{lencw}\right)$ – cell array of strings

lencw, the dimension of the array, must satisfy the constraint $\mathit{lencw}\ge 600$.

Constraint: $\mathit{lencw}\ge 600$.

26:   $\mathrm{iw}\left(\mathit{leniw}\right)$ – int64int32nag_int array

leniw, the dimension of the array, must satisfy the constraint $\mathit{leniw}\ge 600$.

Constraint: $\mathit{leniw}\ge 600$.

27:   $\mathrm{rw}\left(\mathit{lenrw}\right)$ – double array

lenrw, the dimension of the array, must satisfy the constraint $\mathit{lenrw}\ge 600$.

Constraint: $\mathit{lenrw}\ge 600$.

Optional Input Parameters

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

Default: For nf, the dimension of the arrays f, fstate, flow, fupp, fmul. (An error is raised if these dimensions are not equal.)

$\mathit{nf}$, the number of problem functions in $F\left(x\right)$, including the objective function (if any) and the linear and nonlinear constraints. Upper and lower bounds on $x$ can be defined using the arguments xlow and xupp and should not be included in $F$.

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

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

Default: the dimension of the arrays xlow, xupp, x, xstate. (An error is raised if these dimensions are not equal.)

$n$, the number of variables.

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

3:     $\mathrm{nxname}$ – int64int32nag_int scalar

Default: the dimension of the array xnames.

The number of names provided in the array xnames.

$\mathbf{nxname}=1$

There are no names provided and generic names will be used in the output.

$\mathbf{nxname}=\mathbf{n}$

Names for all variables must be provided and will be used in the output.

Constraint: $\mathbf{nxname}=1\text{ or }\mathbf{n}$.

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

Default: the dimension of the array fnames.

The number of names provided in the array fnames.

$\mathbf{nfname}=1$

There are no names provided and generic names will be used in the output.

$\mathbf{nfname}=\mathbf{nf}$

Names for all functions must be provided and will be used in the output.

Constraint: $\mathbf{nfname}=1\text{ or }\mathbf{nf}$.

Note: if $\mathbf{nxname}=1$ then nfname must also be $1$ (and vice versa). Similarly, if $\mathbf{nxname}=\mathbf{n}$ then nfname must be nf (and vice versa).

5:     $\mathrm{lena}$ – int64int32nag_int scalar

Default: the dimension of the arrays iafun, javar, a. (An error is raised if these dimensions are not equal.)

The dimension of the arrays iafun, javar and a that hold $\left(i,j,A_{ij}\right)$.

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

6:     $\mathrm{leng}$ – int64int32nag_int scalar

Default: the dimension of the arrays igfun, jgvar. (An error is raised if these dimensions are not equal.)

The dimension of the arrays igfun and jgvar that define the varying Jacobian elements $\left(i,j,G_{ij}\right)$.

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

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

user is not used by nag_opt_nlp2_sparse_solve (e04vh), but is passed to usrfun. 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{x}\left(\mathbf{n}\right)$ – double array

The final values of the variable $x$.

2:     $\mathrm{xstate}\left(\mathbf{n}\right)$ – int64int32nag_int array

The final state of the variables.

$\mathbf{xstate}\left(j\right)$	State of variable $j$	Usual value of $\mathbf{x}\left(j\right)$
0	nonbasic	$\mathbf{xlow}\left(j\right)$
1	nonbasic	$\mathbf{xupp}\left(j\right)$
2	superbasic	Between $\mathbf{xlow}\left(j\right)$ and $\mathbf{xupp}\left(j\right)$
3	basic	Between $\mathbf{xlow}\left(j\right)$ and $\mathbf{xupp}\left(j\right)$

Basic and superbasic variables may be outside their bounds by as much as the optional parameter Minor Feasibility Tolerance. Note that if scaling is specified, the feasibility tolerance applies to the variables of the scaled problem. In this case, the variables of the original problem may be as much as $0.1$ outside their bounds, but this is unlikely unless the problem is very badly scaled. Check the value of Primal infeasibility output to the unit number associated with the optional parameter Print File.

Very occasionally some nonbasic variables may be outside their bounds by as much as the optional parameter Minor Feasibility Tolerance, and there may be some nonbasics for which $\mathbf{x}\left(j\right)$ lies strictly between its bounds.

If $\mathbf{ninf}>0$, some basic and superbasic variables may be outside their bounds by an arbitrary amount (bounded by sinf if scaling was not used).

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

The vector of the dual variables (Lagrange multipliers) for the simple bounds $l_x\le x\le u_x$.

4:     $\mathrm{f}\left(\mathbf{nf}\right)$ – double array

The final values for the problem functions $F$ (the values $F$ at the final point x).

5:     $\mathrm{fstate}\left(\mathbf{nf}\right)$ – int64int32nag_int array

The final state of the variables. The elements of fstate have the following meaning:

$\mathbf{fstate}\left(i\right)$	State of the corresponding slack variable	Usual value of $\mathbf{f}\left(i\right)$
0	nonbasic	$\mathbf{flow}\left(i\right)$
1	nonbasic	$\mathbf{fupp}\left(i\right)$
2	superbasic	Between $\mathbf{flow}\left(i\right)$ and $\mathbf{fupp}\left(i\right)$
3	basic	Between $\mathbf{flow}\left(i\right)$ and $\mathbf{fupp}\left(i\right)$

Basic and superbasic slack variables may lead to the corresponding functions being outside their bounds by as much as the optional parameter Minor Feasibility Tolerance.

Very occasionally some functions may be outside their bounds by as much as the optional parameter Minor Feasibility Tolerance, and there may be some nonbasics for which $\mathbf{f}\left(i\right)$ lies strictly between its bounds.

If $\mathbf{ninf}>0$, some basic and superbasic variables may be outside their bounds by an arbitrary amount (bounded by sinf if scaling was not used).

6:     $\mathrm{fmul}\left(\mathbf{nf}\right)$ – double array

The vector of the dual variables (Lagrange multipliers) for the general constraints $l_F\le F\left(x\right)\le u_F$

7:     $\mathrm{ns}$ – int64int32nag_int scalar

The final number of superbasic variables.

8:     $\mathrm{ninf}$ – int64int32nag_int scalar

9:     $\mathrm{sinf}$ – double scalar

Are the number and the sum of the infeasibilities of constraints that lie outside one of their bounds by more than the optional parameter Minor Feasibility Tolerance before the solution is unscaled.

If any linear constraints are infeasible, $x$ minimizes the sum of the infeasibilities of the linear constraints subject to the upper and lower bounds being satisfied. In this case ninf gives the number of variables and linear constraints lying outside their upper or lower bounds. The nonlinear constraints are not evaluated.

Otherwise, $x$ minimizes the sum of infeasibilities of the nonlinear constraints subject to the linear constraints and upper and lower bounds being satisfied. In this case ninf gives the number of components of $F\left(x\right)$ lying outside their bounds by more than the optional parameter Minor Feasibility Tolerance. Again this is before the solution is unscaled.

10:   $\mathrm{cw}\left(\mathit{lencw}\right)$ – cell array of strings

$\mathbf{cw}=\mathbf{state}.\text{cw}$$\mathit{lencw}=600$.

Communication array, used to store information between calls to nag_opt_nlp2_sparse_solve (e04vh).

11:   $\mathrm{iw}\left(\mathit{leniw}\right)$ – int64int32nag_int array

$\mathbf{iw}=\mathbf{state}.\text{iw}$$\mathit{leniw}=600$.

Communication array, used to store information between calls to nag_opt_nlp2_sparse_solve (e04vh).

12:   $\mathrm{rw}\left(\mathit{lenrw}\right)$ – double array

$\mathbf{rw}=\mathbf{state}.\text{rw}$$\mathit{lenrw}=600$.

Communication array, used to store information between calls to nag_opt_nlp2_sparse_solve (e04vh).

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

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

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

nag_opt_nlp2_sparse_solve (e04vh) returns with $\mathbf{ifail}=\mathbf{0}$ if the iterates have converged to a point $x$ that satisfies the first-order Kuhn–Tucker (see Minor Iteration Log) conditions to the accuracy requested by the optional parameter Major Optimality Tolerance, i.e., the projected gradient and active constraint residuals are negligible at $x$.

You should check whether the following four conditions are satisfied:

(i)	the final value of rgNorm (see Minor Iteration Log) is significantly less than that at the starting point;
(ii)	during the final major iterations, the values of Step and Minors (see Major Iteration Log) are both one;
(iii)	the last few values of both rgNorm and SumInf (see Minor Iteration Log) become small at a fast linear rate; and
(iv)	condHz (see Major Iteration Log) is small.

If all these conditions hold, $x$ is almost certainly a local minimum of (1).

One caution about ‘Optimal solutions’. Some of the variables or slacks may lie outside their bounds more than desired, especially if scaling was requested. Max Primal infeas in the Print file (see Description of Monitoring Information) refers to the largest bound infeasibility and which variable is involved. If it is too large, consider restarting with a smaller Minor Feasibility Tolerance (say $10$ times smaller) and perhaps $\mathbf{Scale\; Option}=0$.

Similarly, Max Dual infeas in the Print file indicates which variable is most likely to be at a nonoptimal value. Broadly speaking, if

$$\mathtt{Max\; Dual\; infeas}/\mathtt{Max\; pi}={10}^{-d}\text{,}$$

then the objective function would probably change in the $d$th significant digit if optimization could be continued. If $d$ seems too large, consider restarting with a smaller Major Optimality Tolerance.

Finally, Nonlinear constraint violn in the Print file shows the maximum infeasibility for nonlinear rows. If it seems too large, consider restarting with a smaller Major Feasibility Tolerance.

Error Indicators and Warnings

   $\mathbf{ifail}=1$

Constraint: $\mathit{lencw}\ge 600$.

Constraint: $\mathit{leniw}\ge 600$.

Constraint: $\mathit{lenrw}\ge 600$.

The initialization function nag_opt_nlp2_sparse_init (e04vg) has not been called.

   $\mathbf{ifail}=2$

Array element $\mathbf{igfun}\left(\_\right)=\_$ is out of range $1$ to $\mathbf{nf}=\_$, or array element $\mathbf{jgvar}\left(\_\right)=\_$ is out of range $1$ to $\mathbf{n}=\_$.

Basis file dimensions do not match this problem.

Constraint: $0\le \mathbf{objrow}\le \mathbf{nf}$.

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

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

Constraint: $\mathbf{nea}\le \mathbf{n}\times \mathbf{nf}$.

Constraint: $\mathbf{nea}\ge 0$.

Constraint: $\mathbf{neg}\le \mathbf{n}\times \mathbf{nf}$.

Constraint: $\mathbf{neg}\ge 0$.

Constraint: $\mathbf{nfname}=1$ or nf.

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

Constraint: $\mathbf{nxname}=1$ or n.

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

Constraint: $\mathbf{start}=0$, $1$ or $2$.

On entry, bounds flow and fupp for $\_$ are equal and infinite. $\mathbf{flow}=\mathbf{fupp}=\_$ and$\mathit{infbnd}=\_$.

On entry, bounds flow and fupp for variable $\_$ are equal and infinite. $\mathbf{flow}=\mathbf{fupp}=\_$ and$\mathit{infbnd}=\_$.

On entry, bounds for $\_$ are inconsistent. $\mathbf{flow}=\_$ and $\mathbf{fupp}=\_$.

On entry, bounds for $\_$ are inconsistent. $\mathbf{xlow}=\_$ and $\mathbf{xupp}=\_$.

On entry, bounds for variable $\_$ are inconsistent. $\mathbf{flow}=\_$ and $\mathbf{fupp}=\_$.

On entry, bounds for variable $\_$ are inconsistent. $\mathbf{xlow}=\_$ and $\mathbf{xupp}=\_$.

On entry, bounds xlow and xupp for $\_$ are equal and infinite. $\mathbf{xlow}=\mathbf{xupp}=\_$ and$\mathit{infbnd}=\_$.

On entry, bounds xlow and xupp for variable $\_$ are equal and infinite. $\mathbf{xlow}=\mathbf{xupp}=\_$ and$\mathit{infbnd}=\_$.

On entry, one but not both of nxname and nfname is equal to $1$.

   $\mathbf{ifail}=3$

The requested accuracy could not be achieved.

A feasible solution has been found, but the requested accuracy in the dual infeasibilities could not be achieved. An abnormal termination has occurred, but nag_opt_nlp2_sparse_solve (e04vh) is within ${10}^{-2}$ of satisfying the Major Optimality Tolerance. Check that the Major Optimality Tolerance is not too small.

   $\mathbf{ifail}=4$

The linear constraints appear to be infeasible.

The problem appears to be infeasible. Infeasibilites have been minimized.

The problem appears to be infeasible. Nonlinear infeasibilites have been minimized.

The problem appears to be infeasible. The linear equality constraints could not be satisfied.

When the constraints are linear, this message is based on a relatively reliable indicator of infeasibility. Feasibility is measured with respect to the upper and lower bounds on the variables and slacks. Among all the points satisfying the general constraints $Ax-s=0$ (see (6) and (7) in Major Iterations), there is apparently no point that satisfies the bounds on $x$ and $s$. Violations as small as the Minor Feasibility Tolerance are ignored, but at least one component of $x$ or $s$ violates a bound by more than the tolerance.

When nonlinear constraints are present, infeasibility is much harder to recognize correctly. Even if a feasible solution exists, the current linearization of the constraints may not contain a feasible point. In an attempt to deal with this situation, when solving each QP subproblem, nag_opt_nlp2_sparse_solve (e04vh) is prepared to relax the bounds on the slacks associated with nonlinear rows.

If a QP subproblem proves to be infeasible or unbounded (or if the Lagrange multiplier estimates for the nonlinear constraints become large), nag_opt_nlp2_sparse_solve (e04vh) enters so-called ‘nonlinear elastic’ mode. The subproblem includes the original QP objective and the sum of the infeasibilities – suitably weighted using the optional parameter Elastic Weight. In elastic mode, some of the bounds on the nonlinear rows are ‘elastic’ – i.e., they are allowed to violate their specific bounds. Variables subject to elastic bounds are known as elastic variables. An elastic variable is free to violate one or both of its original upper or lower bounds. If the original problem has a feasible solution and the elastic weight is sufficiently large, a feasible point eventually will be obtained for the perturbed constraints, and optimization can continue on the subproblem. If the nonlinear problem has no feasible solution, nag_opt_nlp2_sparse_solve (e04vh) will tend to determine a ‘good’ infeasible point if the elastic weight is sufficiently large. (If the elastic weight were infinite, nag_opt_nlp2_sparse_solve (e04vh) would locally minimize the nonlinear constraint violations subject to the linear constraints and bounds.)

Unfortunately, even though nag_opt_nlp2_sparse_solve (e04vh) locally minimizes the nonlinear constraint violations, there may still exist other regions in which the nonlinear constraints are satisfied. Wherever possible, nonlinear constraints should be defined in such a way that feasible points are known to exist when the constraints are linearized.

   $\mathbf{ifail}=5$

The problem appears to be unbounded. The constraint violation limit has been reached.

The problem appears to be unbounded. The objective function is unbounded.

The problem appears to be unbounded (or badly scaled).

For linear problems, unboundedness is detected by the simplex method when a nonbasic variable can be increased or decreased by an arbitrary amount without causing a basic variable to violate a bound. Consider adding an upper or lower bound to the variable. Also, examine the constraints that have nonzeros in the associated column, to see if they have been formulated as intended.

Very rarely, the scaling of the problem could be so poor that numerical error will give an erroneous indication of unboundedness. Consider using the optional parameter Scale Option.

For nonlinear problems, nag_opt_nlp2_sparse_solve (e04vh) monitors both the size of the current objective function and the size of the change in the variables at each step. If either of these is very large (as judged by the ‘Unbounded’ optional parameters (see Optional Parameters)), the problem is terminated and declared unbounded. To avoid large function values, it may be necessary to impose bounds on some of the variables in order to keep them away from singularities in the nonlinear functions.

The message may indicate an abnormal termination while enforcing the limit on the constraint violations. This exit implies that the objective is not bounded below in the feasible region defined by expanding the bounds by the value of the Violation Limit.

   $\mathbf{ifail}=6$

Iteration limit reached.

Major iteration limit reached.

The value of the optional parameter Superbasics Limit is too small.

Either the Iterations Limit or the Major Iterations Limit was exceeded before the required solution could be found. Check the iteration log to be sure that progress was being made. If so, and if you caused a basis file to be saved by using the optional parameter New Basis File, consider restarting the run using the optional parameter Old Basis File to see whether further progress can be made. If you have no basis file available, you might rerun the problem after increasing the optional parameters Minor Iterations Limit and/or Major Iterations Limit.

If none of the above limits have been reached, this error may mean that the problem appears to be more nonlinear than anticipated. The current set of basic and superbasic variables have been optimized as much as possible and a pricing operation (where a nonbasic variable is selected to become superbasic) is necessary to continue, but it can't continue as the number of superbasic variables has already reached the limit specified by the optional parameter Superbasics Limit. In general, raise the Superbasics Limit $s$ by a reasonable amount, bearing in mind the storage needed for the reduced Hessian.

   $\mathbf{ifail}=7$

Numerical difficulties have been encountered and no further progress can be made.

Several circumstances could lead to this exit.

1.	usrfun could be returning accurate function values but inaccurate gradients (or vice versa). This is the most likely cause. Study the comments given for $\mathbf{ifail}=\mathbf{8}$, and do your best to ensure that the coding is correct.
2.	The function and gradient values could be consistent, but their precision could be too low. For example, accidental use of a low precision data type when a higher precision was intended would lead to a relative function precision of about ${10}^{-6}$ instead of something like ${10}^{-15}$. The default Major Optimality Tolerance of $2\times {10}^{-6}$ would need to be raised to about ${10}^{-3}$ for optimality to be declared (at a rather suboptimal point). Of course, it is better to revise the function coding to obtain as much precision as economically possible.
3.	If function values are obtained from an expensive iterative process, they may be accurate to rather few significant figures, and gradients will probably not be available. One should specify Function Precision $t$ Major Optimality Tolerance $\sqrt{t}$ but even then, if $t$ is as large as ${10}^{-5}$ or ${10}^{-6}$ (only $5$ or $6$ significant figures), the same exit condition may occur. At present the only remedy is to increase the accuracy of the function calculation.
4.	An $LU$ factorization of the basis has just been obtained and used to recompute the basic variables $x_B$, given the present values of the superbasic and nonbasic variables. A step of ‘iterative refinement’ has also been applied to increase the accuracy of $x_B$. However, a row check has revealed that the resulting solution does not satisfy the current constraints $Ax-s=0$ sufficiently well. This probably means that the current basis is very ill-conditioned. If there are some linear constraints and variables, try $\mathbf{Scale\; Option}=1$ if scaling has not yet been used. For certain highly structured basis matrices (notably those with band structure), a systematic growth may occur in the factor $U$. Consult the description of Umax and Growth in Basis Factorization Statistics and set the LU Factor Tolerance to $2.0$ (or possibly even smaller, but not less than $1.0$).
5.	The first factorization attempt will have found the basis to be structurally or numerically singular. (Some diagonals of the triangular matrix $U$ were respectively zero or smaller than a certain tolerance.) The associated variables are replaced by slacks and the modified basis is refactorized, but singularity persists. This must mean that the problem is badly scaled, or the LU Factor Tolerance is too much larger than $1.0$. This is highly unlikely to occur.

   $\mathbf{ifail}=8$

User-supplied function computes incorrect constraint derivatives.

User-supplied function computes incorrect objective derivatives.

A check has been made on some elements of the Jacobian as returned in the argument g of usrfun. At least one value disagrees remarkably with its associated forward difference estimate (the relative difference between the computed and estimated values is $1.0$ or more). This exit is a safeguard, since nag_opt_nlp2_sparse_solve (e04vh) will usually fail to make progress when the computed gradients are seriously inaccurate. In the process it may expend considerable effort before terminating with $\mathbf{ifail}=\mathbf{7}$.

Check the function and Jacobian computation very carefully in usrfun. A simple omission could explain everything. If a component is very large, then give serious thought to scaling the function or the nonlinear variables.

If you feel certain that the computed Jacobian is correct (and that the forward-difference estimate is therefore wrong), you can specify $\mathbf{Verify\; Level}=0$ to prevent individual elements from being checked. However, the optimization procedure may have difficulty.

   $\mathbf{ifail}=9$

Unable to proceed into undefined region of user-supplied function.

User-supplied function is undefined at the first feasible point.

User-supplied function is undefined at the initial point.

You have indicated that the problem functions are undefined by assigning the value $\mathbf{status}=-1$ on exit from usrfun. nag_opt_nlp2_sparse_solve (e04vh) attempts to evaluate the problem functions closer to a point at which the functions are already known to be defined. This exit occurs if nag_opt_nlp2_sparse_solve (e04vh) is unable to find a point at which the functions are defined. This will occur in the case of:

–	undefined functions with no recovery possible;
–	undefined functions at the first point;
–	undefined functions at the first feasible point; or
–	undefined functions when checking derivatives.

   $\mathbf{ifail}=10$

User-supplied function requested termination.

User requested termination.

You have indicated the wish to terminate solution of the current problem by setting status to a value $<-1$ on exit from usrfun.

   $\mathbf{ifail}=11$

Internal error.

   $\mathbf{ifail}=12$

Internal memory allocation was insufficient. Please contact NAG.

   $\mathbf{ifail}=13$

An error has occurred in the basis package. Check that arrays iafun, javar, igfun and jgvar contain values in the appropriate ranges and do not define duplicate elements of a or g. Set the optional parameter Print File and examine the output carefully for further information.

   $\mathbf{ifail}=14$

An unexpected error has occurred. Set the optional parameter Print File and examine the output carefully for further information.

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

The Final Output

The ROWS section

The COLUMNS section

Example

Open in the MATLAB editor: e04vh_example

function e04vh_example


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


start  = int64(0);
objadd = 0;
objrow = int64(6);
prob  = '        ';
iarow = int64([1;2;4;4;5;5;6;6]);
iacol = int64([3;4;1;2;1;2;3;4]);
nea   = int64(8);
a     = [ -1; -1; -1;  1;  1; -1;  3;  2];
igrow = int64([1;1;2;2;3;3;6;6]);
igcol = int64([1;2;1;2;1;2;3;4]);
neg   = int64(8);

xlow  = [-0.55;  -0.55;    0;    0];
xupp  = [ 0.55;   0.55; 1200; 1200];
x     = [ 0;      0;       0;    0];
xnames = {' '};
xstate = zeros(4, 1, 'int64');

flow  = [-894.8; -894.8; -1294.8; -0.55; -0.55; -1e25];
fupp  = [-894.8; -894.8; -1294.8;  1e25;  1e25;  1e25];
f     = [   0;      0;       0;       0;     0;     0];
fnames = {' '};
fstate = zeros(6, 1, 'int64');
fmul   = zeros(6, 1);
ns     = int64(0);

[cw, iw, rw, ifail] = e04vg;

[x, xstate, xmul, f, fstate, fmul, ns, ninf, sinf, ...
                                   cw, iw, rw, cuser, ifail] = ...
     e04vh(...
           start, objadd, objrow, prob, @usrfun, iarow, iacol, ...
           nea, a, igrow, igcol, neg, xlow, xupp, xnames, flow, fupp, ...
           fnames, x, xstate, f, fstate, fmul, ns, cw, iw, rw);
% x, xstate, xmul, f, fstate, fmul, ns, ninf, sinf, ifail

fprintf('Final objective value  :   %8.1f\n',f(objrow));
fprintf('Optimal values for x   :  ');
fprintf(' %9.2f',x);
fprintf('\n');



function [status, f, g, user] = ...
  usrfun(status, n, x, needf, nf, f, needg, leng, g, user)

  if (needf > 0)
%   The nonlinear components of f_i(x) need to be assigned,
%   for i = 1 to NF
    f(1) = 1000*sin(-x(1)-0.25)     + 1000*sin(-x(2) -0.25);
    f(2) = 1000*sin(x(1)-0.25)      + 1000*sin(x(1)-x(2) -0.25);
    f(3) = 1000*sin(x(2)-x(1)-0.25) + 1000*sin(x(2) -0.25);
%   n.b. in this example there is no need to assign for the wholly
%   linear components f_4(x) and f_5(x).
    f(6) = 1.0d-6*x(3)^3 + 2.0d-6*x(4)^3/3;
  end

  if (needg > 0)
%   The derivatives of the function f_i(x) need to be assigned.
%   G(k) should be set to partial derivative df_i(x)/dx_j where
%   i = IGFUN(k) and j = IGVAR(k), for k = 1 to LENG.
    g(1) = -1000*cos(-x(1)-0.25);
    g(2) = -1000*cos(-x(2)-0.25);
    g(3) =  1000*cos(x(1)-0.25)      + 1000*cos(x(1)-x(2) -0.25);
    g(4) = -1000*cos(x(1)-x(2)-0.25);
    g(5) = -1000*cos(x(2)-x(1)-0.25);
    g(6) =  1000*cos(x(2)-x(1)-0.25) + 1000*cos(x(2) -0.25);
    g(7) = 3.0d-6*x(3)^2;
    g(8) = 2.0d-6*x(4)^2;
  end

e04vh example results

Final objective value  :     5126.5
Optimal values for x   :        0.12     -0.40    679.95   1026.07

Algorithmic Details

Constraints and Slack Variables

Major Iterations

Minor Iterations

The Merit Function

Treatment of Constraint Infeasibilities

Optional Parameters

• Backup Basis File
• Central Difference Interval
• Check Frequency
• Crash Option
• Crash Tolerance
• Defaults
• Derivative Linesearch
• Derivative Option
• Difference Interval
• Dump File
• Elastic Weight
• Expand Frequency
• Factorization Frequency
• Feasibility Tolerance
• Feasible Point
• Function Precision
• Hessian Frequency
• Hessian Full Memory
• Hessian Limited Memory
• Hessian Updates
• Infinite Bound Size
• Insert File
• Iterations Limit
• Linesearch Tolerance
• List
• Load File
• LU Complete Pivoting
• LU Density Tolerance
• LU Factor Tolerance
• LU Partial Pivoting
• LU Rook Pivoting
• LU Singularity Tolerance
• LU Update Tolerance
• Major Feasibility Tolerance
• Major Iterations Limit
• Major Optimality Tolerance
• Major Print Level
• Major Step Limit
• Maximize
• Minimize
• Minor Feasibility Tolerance
• Minor Iterations Limit
• Minor Print Level
• New Basis File
• New Superbasics Limit
• Nolist
• Nonderivative Linesearch
• Old Basis File
• Partial Price
• Pivot Tolerance
• Print File
• Print Frequency
• Proximal Point Method
• Punch File
• Save Frequency
• Scale Option
• Scale Print
• Scale Tolerance
• Solution File
• Summary File
• Summary Frequency
• Superbasics Limit
• Suppress Parameters
• System Information No
• System Information Yes
• Timing Level
• Unbounded Objective
• Unbounded Step Size
• Verify Level
• Violation Limit

[cw, iw, rw, ifail] = e04vl('Print Level = 5', cw, iw, rw);

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, and $\mathit{bigbnd}$ signifies the value of Infinite Bound Size.