NAG CL Interface
h02dac (sqp)
1
Purpose
h02dac solves general nonlinear programming problems with integer constraints on some of the variables.
2
Specification
void |
h02dac (Integer n,
Integer nclin,
Integer ncnln,
const double a[],
Integer pda,
const double d[],
double ax[],
const double bl[],
const double bu[],
const Integer varcon[],
double x[],
double c[],
double cjac[],
double objgrd[],
Integer maxit,
double acc,
double *objmip,
const Integer iopts[],
const double opts[],
Nag_Comm *comm,
NagError *fail) |
|
The function may be called by the names: h02dac or nag_mip_sqp.
Before calling
h02dac,
h02zkc must be called with
optstr set to ‘
Initialize = h02dac’. Optional parameters may also be specified by calling
h02zkc before the call to
h02dac.
3
Description
h02dac solves mixed integer nonlinear programming problems using a modified sequential quadratic programming method. The problem is assumed to be stated in the following general form:
with
continuous variables and
binary and integer variables in a total of
variables;
equality constraints in a total of
constraint functions.
Partial derivatives of and are not required for the integer variables. Gradients with respect to integer variables are approximated by difference formulae.
No assumptions are made regarding except that it is twice continuously differentiable with respect to continuous elements of . It is not assumed that integer variables are relaxable. In other words, problem functions are evaluated only at integer points.
The method seeks to minimize the exact penalty function:
where
is adapted by the algorithm and
is given by:
Successive quadratic approximations are applied under the assumption that integer variables have a smooth influence on the model functions, that is function values do not change drastically when incrementing or decrementing an integer value. In practice this requires integer variables to be ordinal not categorical. The algorithm is stabilised by a trust region method including Yuan's second order corrections, see
Yuan and Sun (2006). The Hessian of the Lagrangian function is approximated by BFGS (see
Section 11.4 in
e04ucc) updates subject to the continuous and integer variables.
The mixed-integer quadratic programming subproblems of the SQP-trust region method are solved by a branch and cut method with continuous subproblem solutions obtained by the primal-dual method of Goldfarb and Idnani, see
Powell (1983). Different strategies are available for selecting a branching variable:
- Maximal fractional branching. Select an integer variable from the relaxed subproblem solution with largest distance from next integer value
- Minimal fractional branching. Select an integer variable from the relaxed subproblem solution with smallest distance from next integer value
and a node from where branching, that is the generation of two new subproblems, begins:
- Best of two. The optimal objective function values of the two child nodes are compared and the node with a lower value is chosen
- Best of all. Select an integer variable from the relaxed subproblem solution with the smallest distance from the next integer value
- Depth first. Select a child node whenever possible.
This implementation is based on the algorithm MISQP as described in
Exler et al. (2013).
Linear constraints may optionally be supplied by a matrix
and vector
rather than the constraint functions
such that
Partial derivatives with respect to of these constraint functions are not requested by h02dac.
4
References
Exler O, Lehmann T and Schittkowski K (2013) A comparative study of SQP-type algorithms for nonlinear and nonconvex mixed-integer optimization Mathematical Programming Computation 4 383–412
Mann A (1986) GAMS/MINOS: Three examples Department of Operations Research Technical Report Stanford University
Powell M J D (1983) On the quadratic programming algorithm of Goldfarb and Idnani Report DAMTP 1983/Na 19 University of Cambridge, Cambridge
Yuan Y-x and Sun W (2006) Optimization Theory and Methods Springer–Verlag
5
Arguments
-
1:
– Integer
Input
-
On entry: , the total number of variables, .
Constraint:
.
-
2:
– Integer
Input
-
On entry: , the number of general linear constraints defined by and .
Constraint:
.
-
3:
– Integer
Input
-
On entry: , the number of constraints supplied by .
Constraint:
.
-
4:
– const double
Input
-
Note: the dimension,
dim, of the array
a
must be at least
when
.
The th element of the matrix is stored in .
On entry: the
th row of
a must contain the coefficients of the
th general linear constraint, for
. Any equality constraints must be specified first.
If
, the array
a is not referenced and may be
NULL.
-
5:
– Integer
Input
-
On entry: the stride separating matrix row elements in the array
a.
Constraint:
.
-
6:
– const double
Input
-
On entry:
, the constant for the
th linear constraint.
If
, the array
d is not referenced and may be
NULL.
-
7:
– double
Output
-
On exit: the final residuals of the linear constraints
.
If
,
ax is not referenced and may be
NULL.
-
8:
– const double
Input
-
9:
– const double
Input
-
On entry: must contain the lower bounds, , and the upper bounds, , for the variables; bounds on integer variables are rounded, bounds on binary variables need not be supplied.
Constraint:
, for .
-
10:
– const Integer
Input
-
On entry:
varcon indicates the nature of each variable and constraint in the problem. The first
elements of the array must describe the nature of the variables, the next
elements the nature of the general linear constraints (if any) and the next
elements the general constraints (if any).
- A continuous variable.
- A binary variable.
- An integer variable.
- An equality constraint.
- An inequality constraint.
Constraints:
- , or , for ;
- or , for ;
- At least one variable must be either binary or integer;
- Any equality constraints must precede any inequality constraints.
-
11:
– double
Input/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:
– function, supplied by the user
External Function
-
confun must calculate the constraint functions supplied by
and their Jacobian at
. If all constraints are supplied by
and
(i.e.,
),
confun will never be called by
h02dac and If
, the first call to
confun will occur after the first call to
objfun.
The specification of
confun is:
-
1:
– Integer *
Input/Output
-
On entry: indicates which values must be assigned during each call of
objfun. Only the following values need be assigned:
- Elements of c containing continuous variables.
- 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
h02dac will terminate with
fail set to
mode.
-
2:
– Integer
Input
-
On entry: the dimension of the array
c and the
first
dimension of the array
cjac. The number of constraints supplied by
,
.
-
3:
– Integer
Input
-
On entry: the
second
dimension of the array
cjac.
, the total number of variables,
.
-
4:
– const Integer
Input
-
On entry: the array
varcon as supplied to
h02dac.
-
5:
– const double
Input
-
On entry: the vector of variables at which the objective function and/or all continuous elements of its gradient are to be evaluated.
-
6:
– double
Output
-
On exit: must contain
ncnln constraint values, with the value of the
th constraint
in
.
-
7:
– double
Input/Output
-
Note: the derivative of the th constraint with respect to the th variable, , is stored in .
On entry: continuous elements of
cjac are set to the value of NaN.
On exit: the
th row of
cjac must contain elements of
for each continuous variable
.
-
8:
– Integer
Input
-
On entry: if
,
h02dac 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:
– Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
confun.
- user – double *
- iuser – Integer *
- p – Pointer
The type Pointer will be
void *. Before calling
h02dac you may allocate memory and initialize these pointers with various quantities for use by
confun when called from
h02dac (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note: confun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
h02dac. If your code inadvertently
does return any NaNs or infinities,
h02dac is likely to produce unexpected results.
-
13:
– double
Output
-
On exit: if
,
contains the value of the
th constraint function
at the final iterate, for
.
If
, the array
c is not referenced and may be
NULL.
-
14:
– double
Output
-
Note: the derivative of the th constraint with respect to the th variable, , is stored in .
On exit: if
,
cjac contains the Jacobian matrix of the constraint functions at the final iterate, i.e.,
contains the partial derivative of the
th constraint function with respect to the
th variable, for
and
. (See the discussion of argument
cjac under
confun.)
If
, the array
cjac is not referenced and may be
NULL.
-
15:
– function, supplied by the user
External Function
-
objfun must calculate the objective function
and its gradient for a specified
-element vector
.
The specification of
objfun is:
-
1:
– Integer *
Input/Output
-
On entry: indicates which values must be assigned during each call of
objfun. Only the following values need be assigned:
- The objective function value, objmip.
- 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
h02dac will terminate with
fail set to
mode.
-
2:
– Integer
Input
-
On entry: , the total number of variables, .
-
3:
– const Integer
Input
-
On entry: the array
varcon as supplied to
h02dac.
-
4:
– const double
Input
-
On entry: the vector of variables at which the objective function and/or all continuous elements of its gradient are to be evaluated.
-
5:
– double *
Output
-
On exit: must be set to the objective function value, .
-
6:
– double
Input/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
, with
containing the partial derivative of
with respect to continuous variable
; otherwise
objgrd is not referenced.
-
7:
– Integer
Input
-
On entry: if
,
h02dac 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:
– Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
objfun.
- user – double *
- iuser – Integer *
- p – Pointer
The type Pointer will be
void *. Before calling
h02dac you may allocate memory and initialize these pointers with various quantities for use by
objfun when called from
h02dac (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note: objfun should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
h02dac. If your code inadvertently
does return any NaNs or infinities,
h02dac is likely to produce unexpected results.
-
16:
– double
Output
-
On exit: the objective function gradient at the solution.
-
17:
– Integer
Input
-
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:
.
-
18:
– double
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
(
being the
machine precision as given by
X02AJC), the below suggested value is used.
Suggested value:
.
-
19:
– double *
Output
-
On exit: with
NE_NOERROR,
objmip contains the value of the objective function for the MINLP solution.
-
20:
– const Integer
Communication 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
h02zkc.
-
21:
– const double
Communication 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
h02zkc.
On entry: the real option array as returned by
h02zkc.
-
22:
– Nag_Comm *
-
The NAG communication argument (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
-
23:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_BOUND
-
On entry, .
Constraint: , for .
- NE_CONSTRAINT
-
On entry, linear equality constraints do not precede linear inequality constraints.
On entry, nonlinear equality constraints do not precede nonlinear inequality constraints.
- NE_DERIV_ERRORS
-
One or more constraint gradients appear to be incorrect.
One or more objective gradients appear to be incorrect.
- NE_INFEASIBLE
-
Termination at an infeasible iterate; if the problem is feasible, try a different starting value.
- NE_INFINITE
-
Penalty parameter tends to infinity in an underlying mixed-integer quadratic program; the problem may be infeasible. If is relatively low value, try a higher one, for example .
Optional parameter .
- NE_INITIALIZATION
-
On entry, the optional parameter arrays
iopts and
opts have either not been initialized or been corrupted.
- NE_INT
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, .
Constraint: .
- NE_INT_3
-
On entry, and .
Constraint: .
- NE_INT_ARRAY_CONS
-
On entry, .
Constraint: , or , for .
On entry, .
Constraint: or , for .
- 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.
See
Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library CL Interface for further information.
- NE_NUM_DIFFICULTIES
-
The optimization failed due to numerical difficulties. Set optional parameter for more information.
- NE_TOO_MANY
-
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 , try increasing it. Optional parameter .
- NE_USER_NAN
-
The supplied
confun returned a NaN value.
The supplied
objfun returned a NaN value.
- NE_USER_STOP
-
The optimization halted because you set
mode negative in
objfun or
mode negative in
confun, to
.
- NE_ZERO_COEFF
-
Termination with zero integer trust region for integer variables; try a different starting value.
Optional parameter .
- NE_ZERO_VARS
-
On entry, there are no binary or integer variables.
- NW_TOO_MANY_ITER
-
On entry, . Exceeded the maximum number of iterations.
7
Accuracy
Not applicable.
8
Parallelism and Performance
h02dac 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.
None.
10
Example
Select a portfolio of at most
assets from
available with expected return
, is fully invested and that minimizes
where
- is a vector of proportions of selected assets
- is an indicator variable that describes if an asset is in or out
- is a vector of mean returns
- is the covariance matrix of returns.
This example is taken from
Mann (1986) with
Linear constraints are supplied through both
and
, and
confun.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results
11
Optional Parameters
This section can be skipped if you wish to use the default values for all optional parameters, otherwise, the following is a list of the optional parameters available and a full description of each optional parameter is provided in
Section 11.1.
11.1
Description of the Optional Parameters
For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
- the keywords;
- a parameter value,
where the letters , and denote options that take character, integer and real values respectively.
All options accept the value in order to return single options to their default states.
Keywords and character values are case insensitive, however they must be separated by at least one space.
h02zkc can be called to supply options, one call being necessary for each optional parameter. For example,
Call h02zkc('Check Gradients = Yes', iopts, liopts, opts, lopts, ifail)
h02zkc should be consulted for a full description of the method of supplying optional parameters.
For
h02dac the maximum length of the argument
cvalue used by
h02zlc is
.
Branch Bound Steps | | Default |
Maximum number of branch-and-bound steps for solving the mixed integer quadratic problems.
Constraint:
.
Branching Rule | | Default |
Branching rule for branch and bound search.
- Maximum fractional branching.
- Minimum fractional branching.
Check Gradients | | Default |
Perform an internal check of supplied objective and constraint gradients. It is advisable to set during code development to avoid difficulties associated with incorrect user-supplied gradients.
Continuous Trust Radius | | Default |
Initial continuous trust region radius, ; the initial trial step for the SQP approximation must satisfy .
Constraint:
.
Initial descent parameter, , larger values of allow penalty optional parameter to increase faster which can lead to faster convergence.
Constraint:
.
Descent Factor | | Default |
Factor for decreasing the internal descent parameter, , between iterations.
Constraint:
.
Feasible Steps | | Default |
Maximum number of feasible steps without improvements, where feasibility is measured by .
Constraint:
.
Improved Bounds | | Default |
Calculate improved bounds in case of ‘Best of all’ node selection strategy.
Integer Trust Radius | | Default |
Initial integer trust region radius, ; the initial trial step for the SQP approximation must satisfy .
Constraint:
.
Maximum Restarts | | Default |
Maximum number of restarts that allow the mixed integer SQP algorithm to return to a better solution. Setting a value higher than the default might lead to better results at the expense of function evaluations.
Constraint:
.
Minor Print Level | | Default |
Print level of the subproblem solver. Active only if .
Constraint:
.
Modify Hessian | | Default |
Modify the Hessian approximation in an attempt to get more accurate search directions. Calculation time is increased when the number of integer variables is large.
Node Selection | | Default |
Node selection strategy for branch and bound.
- Large tree search; this method is the slowest as it solves all subproblem QPs independently.
- Uses warm starts and less memory.
- 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.
Maximum number of successive iterations considered for the non-monotone trust region algorithm, allowing the penalty function to increase.
Constraint:
.
Objective Scale Bound | | Default |
When internally scale absolute function values greater than or .
Constraint:
.
Initial penalty optional parameter, .
Constraint:
.
Penalty Factor | | Default |
Factor for increasing penalty optional parameter when the trust regions cannot be enlarged at a trial step.
Constraint:
.
Specifies the desired output level of printing.
- No output.
- Final convergence analysis.
- One line of intermediate results per iteration.
- Detailed information printed per iteration.
QP Accuracy | | Default |
Termination tolerance of the relaxed quadratic program subproblems.
Constraint:
.
Scale Continuous Variables | | Default |
Internally scale continuous variables values.
Scale Objective Function | | Default |
Internally scale objective function values.
- No scaling.
- Scale absolute values greater than .
Maximum number of warm starts within the mixed integer QP solver, see .
Constraint:
.