NAG Library Routine Document

h02daf (sqp)

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

1:     $\mathbf{n}$ – IntegerInput

On entry: $n$, the total number of variables, $n_c+n_i$.

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

2:     $\mathbf{nclin}$ – IntegerInput

On entry: $n_l$, the number of general linear constraints defined by $A$ and $d$.

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

3:     $\mathbf{ncnln}$ – IntegerInput

On entry: $n_N$, the number of constraints supplied by $c\left(x\right)$.

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

4:     $\mathbf{a}\left(\mathbf{lda},*\right)$ – Real (Kind=nag_wp) arrayInput

Note: the second dimension of the array a must be at least $\mathbf{n}$ if $\mathbf{nclin}>0$.

On entry: the $\mathit{i}$th row of a must contain the coefficients of the $\mathit{i}$th general linear constraint, for $\mathit{i}=1,2,\dots ,n_l$. Any equality constraints must be specified first.

If $\mathbf{nclin}=0$, the array a is not referenced.

5:     $\mathbf{lda}$ – IntegerInput

On entry: the first dimension of the array a as declared in the (sub)program from which h02daf is called.

Constraint: $\mathbf{lda}\ge \max \left(1,\mathbf{nclin}\right)$.

6:     $\mathbf{d}\left(\mathbf{nclin}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: $d_i$, the constant for the $i$th linear constraint.

If $\mathbf{nclin}=0$, the array d is not referenced.

7:     $\mathbf{ax}\left(\mathbf{nclin}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the final values of the linear constraints $Ax$.

If $\mathbf{nclin}=0$, ax is not referenced.

8:     $\mathbf{bl}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

9:     $\mathbf{bu}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: $\mathbf{bl}$ must contain the lower bounds, $l_i$, and $\mathbf{bu}$ the upper bounds, $u_i$, for the variables; bounds on integer variables are rounded, bounds on binary variables need not be supplied.

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

10:   $\mathbf{varcon}\left(\mathbf{n}+\mathbf{nclin}+\mathbf{ncnln}\right)$ – Integer arrayInput

On entry: varcon indicates the nature of each variable and constraint in the problem. The first $n$ elements of the array must describe the nature of the variables, the next $n_L$ elements the nature of the general linear constraints (if any) and the next $n_N$ elements the general constraints (if any).

$\mathbf{varcon}\left(j\right)=0$

A continuous variable.

$\mathbf{varcon}\left(j\right)=1$

A binary variable.

$\mathbf{varcon}\left(j\right)=2$

An integer variable.

$\mathbf{varcon}\left(j\right)=3$

An equality constraint.

$\mathbf{varcon}\left(j\right)=4$

An inequality constraint.

Constraints:

• $\mathbf{varcon}\left(\mathit{j}\right)=0$, $1$ or $2$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$;
• $\mathbf{varcon}\left(\mathit{j}\right)=3$ or $4$, for $\mathit{j}=\mathbf{n}+1,\dots ,\mathbf{n}+\mathbf{nclin}+\mathbf{ncnln}$;
• At least one variable must be either binary or integer;
• Any equality constraints must precede any inequality constraints.

11:   $\mathbf{x}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: an initial estimate of the solution, which need not be feasible. Values corresponding to integer variables are rounded; if an initial value less than half is supplied for a binary variable the value zero is used, otherwise the value one is used.

On exit: the final estimate of the solution.

12:   $\mathbf{confun}$ – Subroutine, supplied by the NAG Library or the user.External Procedure

confun must calculate the constraint functions supplied by $c\left(x\right)$ and their Jacobian at $x$. If all constraints are supplied by $A$ and $d$ (i.e., $\mathbf{ncnln}=0$), confun will never be called by h02daf and confun may be the dummy routine h02ddm. (h02ddm is included in the NAG Library.) If $\mathbf{ncnln}>0$, the first call to confun will occur after the first call to objfun.

The specification of confun is:

Fortran Interface

Subroutine confun ( mode, ncnln, n, varcon, x, c, cjac, nstate, iuser, ruser) Integer, Intent (In) :: ncnln, n, varcon(*), nstate Integer, Intent (Inout) :: mode, iuser(*) Real (Kind=nag_wp), Intent (In) :: x(n) Real (Kind=nag_wp), Intent (Inout) :: cjac(ncnln,n), ruser(*) Real (Kind=nag_wp), Intent (Out) :: c(ncnln)

C Header Interface

#include <nagmk26.h> void  confun (Integer *mode, const Integer *ncnln, const Integer *n, const Integer varcon[], const double x[], double c[], double cjac[], const Integer *nstate, Integer iuser[], double ruser[])

1:     $\mathbf{mode}$ – IntegerInput/Output

On entry: indicates which values must be assigned during each call of objfun. Only the following values need be assigned:

$\mathbf{mode}=0$

Elements of c containing continuous variables.

$\mathbf{mode}=1$

Elements of cjac containing continuous variables.

On exit: may be set to a negative value if you wish to terminate the solution to the current problem, and in this case h02daf will terminate with ifail set to mode.

2:     $\mathbf{ncnln}$ – IntegerInput

On entry: the dimension of the array c and the first dimension of the array cjac as declared in the (sub)program from which h02daf is called. The number of constraints supplied by $c\left(x\right)$, $n_N$.

3:     $\mathbf{n}$ – IntegerInput

On entry: the second dimension of the array cjac as declared in the (sub)program from which h02daf is called. $n$, the total number of variables, $n_c+n_i$.

4:     $\mathbf{varcon}\left(*\right)$ – Integer arrayInput

On entry: the array varcon as supplied to h02daf.

5:     $\mathbf{x}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the vector of variables at which the objective function and/or all continuous elements of its gradient are to be evaluated.

6:     $\mathbf{c}\left(\mathbf{ncnln}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: must contain ncnln constraint values, with the value of the $j$th constraint $c_j\left(x\right)$ in $\mathbf{c}\left(j\right)$.

7:     $\mathbf{cjac}\left(\mathbf{ncnln},\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput/Output

Note: the derivative of the $i$th constraint with respect to the $j$th variable, $\frac{\partial c_i}{\partial x_{\mathrm{j}}}$, is stored in $\mathbf{cjac}\left(i,j\right)$.

On entry: continuous elements of cjac are set to the value of NaN.

On exit: the $i$th row of cjac must contain elements of $\frac{\partial c_i}{\partial x_{\mathrm{j}}}$ for each continuous variable $x_j$.

8:     $\mathbf{nstate}$ – IntegerInput

On entry: if $\mathbf{nstate}=1$, h02daf is calling confun for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

9:     $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

10:   $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

confun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h02daf is called. Arguments denoted as Input must not be changed by this procedure.

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

13:   $\mathbf{c}\left(\mathbf{ncnln}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: if $\mathbf{ncnln}>0$, $\mathbf{c}\left(\mathit{j}\right)$ contains the value of the $\mathit{j}$th constraint function $c_{\mathit{j}}\left(x\right)$ at the final iterate, for $\mathit{j}=1,2,\dots ,\mathbf{ncnln}$.

If $\mathbf{ncnln}=0$, the array c is not referenced.

14:   $\mathbf{cjac}\left(\mathbf{ncnln},\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayOutput

Note: the derivative of the $i$th constraint with respect to the $j$th variable, $\frac{\partial c_i}{\partial x_{\mathrm{j}}}$, is stored in $\mathbf{cjac}\left(i,j\right)$.

On exit: if $\mathbf{ncnln}>0$, cjac contains the Jacobian matrix of the constraint functions at the final iterate, i.e., $\mathbf{cjac}\left(\mathit{i},\mathit{j}\right)$ contains the partial derivative of the $\mathit{i}$th constraint function with respect to the $\mathit{j}$th variable, for $\mathit{i}=1,2,\dots ,\mathbf{ncnln}$ and $\mathit{j}=1,2,\dots ,\mathbf{n}$. (See the discussion of argument cjac under confun.)

If $\mathbf{ncnln}=0$, the array cjac is not referenced.

15:   $\mathbf{objfun}$ – Subroutine, supplied by the user.External Procedure

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

The specification of objfun is:

Fortran Interface

Subroutine objfun ( mode, n, varcon, x, objmip, objgrd, nstate, iuser, ruser) Integer, Intent (In) :: n, varcon(*), nstate Integer, Intent (Inout) :: mode, iuser(*) Real (Kind=nag_wp), Intent (In) :: x(n) Real (Kind=nag_wp), Intent (Inout) :: objgrd(n), ruser(*) Real (Kind=nag_wp), Intent (Out) :: objmip

C Header Interface

#include <nagmk26.h> void  objfun (Integer *mode, const Integer *n, const Integer varcon[], const double x[], double *objmip, double objgrd[], const Integer *nstate, Integer iuser[], double ruser[])

1:     $\mathbf{mode}$ – IntegerInput/Output

On entry: indicates which values must be assigned during each call of objfun. Only the following values need be assigned:

$\mathbf{mode}=0$

The objective function value, objmip.

$\mathbf{mode}=1$

The continuous elements of objgrd.

On exit: may be set to a negative value if you wish to terminate the solution to the current problem, and in this case h02daf will terminate with ifail set to mode.

2:     $\mathbf{n}$ – IntegerInput

On entry: $n$, the total number of variables, $n_c+n_i$.

3:     $\mathbf{varcon}\left(*\right)$ – Integer arrayInput

On entry: the array varcon as supplied to h02daf.

4:     $\mathbf{x}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the vector of variables at which the objective function and/or all continuous elements of its gradient are to be evaluated.

5:     $\mathbf{objmip}$ – Real (Kind=nag_wp)Output

On exit: must be set to the objective function value, $f$, if $\mathbf{mode}=0$; otherwise objmip is not referenced.

6:     $\mathbf{objgrd}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: continuous elements of objgrd are set to the value of NaN.

On exit: must contain the gradient vector of the objective function if $\mathbf{mode}=1$, with $\mathbf{objgrd}\left(j\right)$ containing the partial derivative of $f$ with respect to continuous variable $x_j$; otherwise objgrd is not referenced.

7:     $\mathbf{nstate}$ – IntegerInput

On entry: if $\mathbf{nstate}=1$, h02daf is calling objfun for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

8:     $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

9:     $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

objfun is called with the arguments iuser and ruser as supplied to h02daf. You should use the arrays iuser and ruser to supply information to objfun.

objfun must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h02daf is called. Arguments denoted as Input must not be changed by this procedure.

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

16:   $\mathbf{objgrd}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the objective function gradient at the solution.

17:   $\mathbf{maxit}$ – IntegerInput

On entry: the maximum number of iterations within which to find a solution. If maxit is less than or equal to zero, the suggested value below is used.

Suggested value: $\mathbf{maxit}=500$.

18:   $\mathbf{acc}$ – Real (Kind=nag_wp)Input

On entry: the requested accuracy for determining feasible points during iterations and for halting the method when the predicted improvement in objective function is less than acc. If acc is less than or equal to $\epsilon$ ($\epsilon$ being the machine precision as given by x02ajf), the below suggested value is used.

Suggested value: $\mathbf{acc}=0.0001$.

19:   $\mathbf{objmip}$ – Real (Kind=nag_wp)Output

On exit: with $\mathbf{ifail}=\mathbf{0}$, objmip contains the value of the objective function for the MINLP solution.

20:   $\mathbf{iopts}\left(*\right)$ – Integer arrayCommunication Array

Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array must be the same array passed as argument iopts in the previous call to h02zkf.

21:   $\mathbf{opts}\left(*\right)$ – Real (Kind=nag_wp) arrayCommunication Array

Note: the dimension of this array is dictated by the requirements of associated functions that must have been previously called. This array must be the same array passed as argument opts in the previous call to h02zkf.

On entry: the real option array as returned by h02zkf.

22:   $\mathbf{iuser}\left(*\right)$ – Integer arrayUser Workspace

23:   $\mathbf{ruser}\left(*\right)$ – Real (Kind=nag_wp) arrayUser Workspace

iuser and ruser are not used by h02daf, but are passed directly to confun and objfun and may be used to pass information to these routines.

24:   $\mathbf{ifail}$ – IntegerInput/Output

On entry: ifail must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ 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 argument, the recommended value is $0$. When the value $-\mathbf{1}\text{ or }\mathbf{1}$ is used it is essential to test the value of ifail on exit.

On exit: $\mathbf{ifail}=\mathbf{0}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6

Error Indicators and Warnings

$\mathbf{ifail}=1$

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

$\mathbf{ifail}=2$

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

$\mathbf{ifail}=3$

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

$\mathbf{ifail}=4$

On entry, $\mathbf{lda}=〈\mathit{\text{value}}〉$ and $\mathbf{nclin}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{lda}\ge \mathbf{nclin}$.

$\mathbf{ifail}=5$

On entry, $\mathbf{bl}\left(〈\mathit{\text{value}}〉\right)>\mathbf{bu}\left(〈\mathit{\text{value}}〉\right)$.
Constraint: $\mathbf{bl}\left(\mathit{i}\right)\le \mathbf{bu}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{n}$.

$\mathbf{ifail}=6$

On entry, $\mathbf{varcon}\left(〈\mathit{\text{value}}〉\right)=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{varcon}\left(\mathit{i}\right)=0$, $1$ or $2$, for $\mathit{i}=1,2,\dots ,\mathbf{n}$.

$\mathbf{ifail}=7$

On entry, $\mathbf{varcon}\left(〈\mathit{\text{value}}〉\right)=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{varcon}\left(\mathit{i}\right)=3$ or $4$, for $\mathit{i}=\mathbf{n}+1,\dots ,\mathbf{n}+\mathbf{nclin}+\mathbf{ncnln}$.

$\mathbf{ifail}=8$

The supplied objfun returned a NaN value.

$\mathbf{ifail}=9$

The supplied confun returned a NaN value.

$\mathbf{ifail}=10$

On entry, the optional parameter arrays iopts and opts have either not been initialized or been corrupted.

$\mathbf{ifail}=11$

On entry, there are no binary or integer variables.

$\mathbf{ifail}=12$

On entry, linear equality constraints do not precede linear inequality constraints.

$\mathbf{ifail}=13$

On entry, nonlinear equality constraints do not precede nonlinear inequality constraints.

$\mathbf{ifail}=81$

One or more objective gradients appear to be incorrect.

$\mathbf{ifail}=91$

One or more constraint gradients appear to be incorrect.

$\mathbf{ifail}=1001$

On entry, $\mathbf{maxit}=〈\mathit{\text{value}}〉$. Exceeded the maximum number of iterations.

$\mathbf{ifail}=1002$

More than the maximum number of feasible steps without improvement in the objective function. If the maximum number of feasible steps is small, say less than $5$, try increasing it. Optional parameter $\mathbf{Feasible\; Steps}=〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=1003$

Penalty parameter tends to infinity in an underlying mixed-integer quadratic program; the problem may be infeasible. If $\sigma$ is relatively low value, try a higher one, for example ${10}^{20}$.
Optional parameter $\mathbf{Penalty}=〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=1004$

Termination at an infeasible iterate; if the problem is feasible, try a different starting value.

$\mathbf{ifail}=1005$

Termination with zero integer trust region for integer variables; try a different starting value.
Optional parameter $\mathbf{Integer\; Trust\; Radius}=〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=1008$

The optimization failed due to numerical difficulties. Set optional parameter $\mathbf{Print\; Level}=3$ for more information.

$\mathbf{ifail}<0$

The optimization halted because you set mode negative in objfun or mode negative in confun, to $〈\mathit{\text{value}}〉$.

$\mathbf{ifail}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

See Section 3.9 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-399$

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

See Section 3.8 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

Program Text (h02dafe.f90)

10.2

Program Data

10.3

Program Results

Program Results (h02dafe.r)

11

Optional Parameters

• Branch Bound Steps
• Branching Rule
• Check Gradients
• Continuous Trust Radius
• Descent
• Descent Factor
• Feasible Steps
• Improved Bounds
• Integer Trust Radius
• Maximum Restarts
• Minor Print Level
• Modify Hessian
• Node Selection
• Non Monotone
• Objective Scale Bound
• Penalty
• Penalty Factor
• Print Level
• QP Accuracy
• Scale Continuous Variables
• Scale Objective Function
• Warm Starts

11.1

Description of the Optional Parameters

• the keywords;
• a parameter value, where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively.

Call h02zkf('Check Gradients = Yes', iopts, liopts, opts, lopts, ifail)

$\mathbf{Branching\; Rule}=\mathrm{Maximum}$

Maximum fractional branching.

$\mathbf{Branching\; Rule}=\mathrm{Minimum}$

Minimum fractional branching.

$\mathbf{Node\; Selection}=\mathrm{Best\; of\; all}$

Large tree search; this method is the slowest as it solves all subproblem QPs independently.

$\mathbf{Node\; Selection}=\mathrm{Best\; of\; two}$

Uses warm starts and less memory.

$\mathbf{Node\; Selection}=\mathrm{Depth\; first}$

Uses more warm starts. If warm starts are applied, they can speed up the solution of mixed integer subproblems significantly when solving almost identical QPs.