The routine may be called by the names h02daf or nagf_mip_sqp.
Before calling h02daf, h02zkfmust be called with optstr set to ‘Initialize = h02daf’. Optional parameters may also be specified by calling h02zkf before the call to h02daf.
h02daf 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 e04ucf/e04uca) 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.
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.
, for .
10: – Integer arrayInput
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.
, or , for ;
or , for ;
At least one variable must be either binary or integer;
Any equality constraints must precede any inequality constraints.
11: – 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: – Subroutine, supplied by the NAG Library or the user.External Procedure
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 h02daf and confun may be the dummy routine h02ddm. (h02ddm is included in the NAG Library.) If , the first call to confun will occur after the first call to objfun.
On entry: the vector of variables at which the objective function and/or all continuous elements of its gradient are to be evaluated.
6: – Real (Kind=nag_wp) arrayOutput
On exit: must contain ncnln constraint values, with the value of the th constraint in .
7: – Real (Kind=nag_wp) arrayInput/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: – IntegerInput
On entry: if , 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: – Integer arrayUser Workspace
10: – 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: – Real (Kind=nag_wp) arrayOutput
On exit: if ,
contains the value of the th constraint function at the final iterate, for .
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.)
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: – Real (Kind=nag_wp) arrayOutput
On exit: the objective function gradient at the solution.
17: – 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.
18: – 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 ( being the machine precision as given by x02ajf), the below suggested value is used.
19: – Real (Kind=nag_wp)Output
On exit: with , objmip contains the value of the objective function for the MINLP solution.
20: – 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: – 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: – Integer arrayUser Workspace
23: – 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: – IntegerInput/Output
On entry: ifail must be set to , or to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of means that an error message is printed while a value of means that it is not.
If halting is not appropriate, the value or is recommended. If message printing is undesirable, then the value is recommended. Otherwise, the value is recommended. When the value or is used it is essential to test the value of ifail on exit.
On exit: unless the routine detects an error or a warning has been flagged (see Section 6).
6Error Indicators and Warnings
If on entry or , explanatory error messages are output on the current error message unit (as defined by x04aaf).
An unexpected error has been triggered by this routine. Please
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.
8Parallelism and Performance
Background information to multithreading can be found in the Multithreading documentation.
h02daf 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 routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.
Select a portfolio of at most assets from available with expected return , is fully invested and that minimizes
is a vector of proportions of selected assets
is an indicator variable that describes if an asset is in or out
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.
h02zkf should be consulted for a full description of the method of supplying optional parameters.
For h02daf the maximum length of the argument cvalue used by h02zlf is .
Branch Bound Steps
Maximum number of branch-and-bound steps for solving the mixed integer quadratic problems.
Branching rule for branch and bound search.
Maximum fractional branching.
Minimum fractional branching.
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
Initial continuous trust region radius, ; the initial trial step for the SQP approximation must satisfy .
Initial descent parameter, , larger values of allow penalty optional parameter to increase faster which can lead to faster convergence.
Factor for decreasing the internal descent parameter, , between iterations.
Maximum number of feasible steps without improvements, where feasibility is measured by .
Calculate improved bounds in case of ‘Best of all’ node selection strategy.
Integer Trust Radius
Initial integer trust region radius, ; the initial trial step for the SQP approximation must satisfy .
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.
Minor Print Level
Print level of the subproblem solver. Active only if .
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 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.