h02daf : NAG Library, Mark 26

h02daf solves general nonlinear programming problems with integer constraints on some of the variables.

Fortran Interface

Subroutine h02daf (

n, nclin, ncnln, a, lda, d, ax, bl, bu, varcon, x, confun, c, cjac, objfun, objgrd, maxit, acc, objmip, iopts, opts, iuser, ruser, ifail)

Integer, Intent (In)	::	n, nclin, ncnln, lda, varcon(n+nclin+ncnln), maxit, iopts(*)
Integer, Intent (Inout)	::	iuser(*), ifail
Real (Kind=nag_wp), Intent (In)	::	a(lda,), d(nclin), bl(n), bu(n), acc, opts()
Real (Kind=nag_wp), Intent (Inout)	::	x(n), ruser(*)
Real (Kind=nag_wp), Intent (Out)	::	ax(nclin), c(ncnln), cjac(ncnln,n), objgrd(n), objmip
External	::	confun, objfun

C Header Interface

#include nagmk26.h

void

h02daf_ ( const Integer *n, const Integer *nclin, const Integer *ncnln, const double a[], const Integer *lda, const double d[], double ax[], const double bl[], const double bu[], const Integer varcon[], double x[],
void (NAG_CALL *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[]),
double c[], double cjac[],
void (NAG_CALL *objfun)( Integer *mode, const Integer *n, const Integer varcon[], const double x[], double *objmip, double objgrd[], const Integer *nstate, Integer iuser[], double ruser[]),
double objgrd[], const Integer *maxit, const double *acc, double *objmip, const Integer iopts[], const double opts[], Integer iuser[], double ruser[], Integer *ifail)

Before calling h02daf, h02zkf must 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:

\begin{array}{lll} \underset{x \in \{R^{n_{c}}, Z^{n_{i}}\}}{minimize} & f (x) \\ subject to & c_{j} (x) = 0, & j = 1, 2, \dots, m_{e} \\ c_{j} (x) \geq 0, & j = m_{e} + 1, m_{e} + 2, \dots, m \\ l \leq x_{i} \leq u, & i = 1, 2, \dots, n \end{array}

with

n_{c}

continuous variables and

n_{i}

binary and integer variables in a total of

n

variables;

m_{e}

equality constraints in a total of

m

constraint functions.

Partial derivatives of

f (x)

and

c (x)

are not required for the

n_{i}

integer variables. Gradients with respect to integer variables are approximated by difference formulae.

No assumptions are made regarding

f (x)

except that it is twice continuously differentiable with respect to continuous elements of

x

. 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:

P_{σ} (x) = f (x) + σ {‖g (x)‖}_{\infty}

where

σ

is adapted by the algorithm and

g (x)

is given by:

\begin{array}{lcll} g (x) & = & c_{j} (x), & j = 1, 2, \dots, m_{e} \\ = & \min (c_{j} (x), 0), & j = m_{e} + 1, m_{e} + 2, \dots, m . \end{array}

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.

This implementation is based on the algorithm MISQP as described in Exler et al. (2013).

Linear constraints may optionally be supplied by a matrix

A

and vector

d

rather than the constraint functions

c (x)

such that

A x = d or   ​ A x \geq d .

Partial derivatives with respect to

x

of these constraint functions are not requested by h02daf.

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

If on entry

ifail = 0

or

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

Not applicable.

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.

None.

Select a portfolio of at most

p

assets from

n

available with expected return

ρ

, is fully invested and that minimizes

\begin{array}{llcl} x^{T} Σ x \\ subject to & r^{T} x & = & ρ \\ \sum_{i = 1}^{n} x_{i} & = & 1 \\ x_{i} & \leq & y_{i} \\ \sum_{i = 1}^{n} y_{i} & \leq & p \\ x_{i} & \geq & 0 \\ y_{i} & = & 0 or 1 \end{array}

where

$x$ is a vector of proportions of selected assets
$y$ is an indicator variable that describes if an asset is in or out
$r$ is a vector of mean returns
$Σ$ is the covariance matrix of returns.

This example is taken from Mann (1986) with

\begin{array}{lcl} r & = & (\begin{matrix} 8 & 9 & 12 & 7 \end{matrix}) \\ Σ & = & (\begin{matrix} 4 & 3 & - 1 & 0 \\ 3 & 6 & 1 & 0 \\ - 1 & 1 & 10 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}) \\ p & = & 3 \\ ρ & = & 10 . \end{array}

Linear constraints are supplied through both

A

and

d

, and confun.

None.

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.

For each option, we give a summary line, a description of the optional parameter and details of constraints.

The summary line contains:

All options accept the value

DEFAULT

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.

h02zkf can be called to supply options, one call being necessary for each optional parameter. For example,

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

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

12

.

Maximum number of branch-and-bound steps for solving the mixed integer quadratic problems.

Constraint:

Branch Bound Steps > 1

.

Branching rule for branch and bound search.

Perform an internal check of supplied objective and constraint gradients. It is advisable to set

Check Gradients = Yes

during code development to avoid difficulties associated with incorrect user-supplied gradients.

Initial continuous trust region radius,

Δ_{0}^{c}

; the initial trial step

d \in R^{n_{c}}

for the SQP approximation must satisfy

{‖d‖}_{\infty} \leq Δ_{0}^{c}

.

Constraint:

Continuous Trust Radius > 0.0

.

Initial descent parameter,

δ

, larger values of

δ

allow penalty optional parameter

σ

to increase faster which can lead to faster convergence.

Constraint:

0.0 < Descent < 1.0

.

Factor for decreasing the internal descent parameter,

δ

, between iterations.

Constraint:

0.0 < Descent Factor < 1.0

.

Maximum number of feasible steps without improvements, where feasibility is measured by

{‖g (x)‖}_{\infty} \leq \sqrt{acc}

.

Constraint:

Feasible Steps > 1

.

Calculate improved bounds in case of ‘Best of all’ node selection strategy.

Initial integer trust region radius,

Δ_{0}^{i}

; the initial trial step

e \in R^{n_{i}}

for the SQP approximation must satisfy

{‖e‖}_{\infty} \leq Δ_{0}^{i}

.

Constraint:

Integer Trust Radius \geq 1.0

.

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:

0 < Maximum Restarts \leq 15

.

Print level of the subproblem solver. Active only if

Print Level \neq 0

.

Constraint:

0 < Minor Print Level < 4

.

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.

Maximum number of successive iterations considered for the non-monotone trust region algorithm, allowing the penalty function to increase.

Constraint:

0 < Non Monotone < 100

.

When

Scale Objective Function > 0

internally scale absolute function values greater than

1.0

or Objective Scale Bound.

Constraint:

Objective Scale Bound > 0.0

.

Initial penalty optional parameter,

σ

.

Constraint:

Penalty \geq 0.0

.

Factor for increasing penalty optional parameter

σ

when the trust regions cannot be enlarged at a trial step.

Constraint:

Penalty Factor > 1.0

.

Specifies the desired output level of printing.

$Print Level = 0$: No output.
$Print Level = 1$: Final convergence analysis.
$Print Level = 2$: One line of intermediate results per iteration.
$Print Level = 3$: Detailed information printed per iteration.

Termination tolerance of the relaxed quadratic program subproblems.

Constraint:

QP Accuracy > 0.0

.

Internally scale continuous variables values.

Internally scale objective function values.

$Scale Objective Function = 0$: No scaling.
$Scale Objective Function = 1$: Scale absolute values greater than Objective Scale Bound.

Maximum number of warm starts within the mixed integer QP solver, see Node Selection.

Constraint:

Warm Starts \geq 0

.

NAG Library Routine Document

h02daf (sqp)

▸▿ Contents

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

6

Error Indicators and Warnings

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

10.2

Program Data

10.3

Program Results

11

Optional Parameters

11.1

Description of the Optional Parameters

NAG Library Routine Document

h02daf (sqp)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

11 Optional Parameters

11.1 Description of the Optional Parameters

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

6

Error Indicators and Warnings

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

10.2

Program Data

10.3

Program Results

11

Optional Parameters

11.1

Description of the Optional Parameters