NAG Toolbox: nag_mip_sqp (h02da)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

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

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

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

2:     $\mathrm{a}\left(\mathit{lda},:\right)$ – double array

The first dimension of the array a must be at least $\max \left(1,\mathbf{nclin}\right)$.

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

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.

3:     $\mathrm{d}\left(\mathbf{nclin}\right)$ – double array

$d_i$, the constant for the $i$th linear constraint.

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

4:     $\mathrm{bl}\left(\mathbf{n}\right)$ – double array

5:     $\mathrm{bu}\left(\mathbf{n}\right)$ – double array

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

6:     $\mathrm{varcon}\left(\mathbf{n}+\mathbf{nclin}+\mathbf{ncnln}\right)$ – int64int32nag_int array

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.

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

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.

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

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 nag_mip_sqp (h02da) and confun may be the string nag_mip_sqp_dummy_confun (h02ddm). (nag_mip_sqp_dummy_confun (h02ddm) is included in the NAG Toolbox.) If $\mathbf{ncnln}>0$, the first call to confun will occur after the first call to objfun.

[mode, c, cjac, user] = confun(mode, ncnln, n, varcon, x, cjac, nstate, user)

Input Parameters

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

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.

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

The dimension of the array c and the first dimension of the array cjac. the number of constraints supplied by $c\left(x\right)$, $n_N$.

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

The second dimension of the array cjac. $n$, the total number of variables, $n_c+n_i$.

4:     $\mathrm{varcon}\left(\mathbf{n}+\mathit{nclin}+\mathbf{ncnln}\right)$ – int64int32nag_int array

The array varcon as supplied to nag_mip_sqp (h02da).

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

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

6:     $\mathrm{cjac}\left(\mathbf{ncnln},\mathbf{n}\right)$ – double array

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)$.

Continuous elements of cjac are set to the value of NaN.

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

If $\mathbf{nstate}=1$, nag_mip_sqp (h02da) 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.

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

confun is called from nag_mip_sqp (h02da) with the object supplied to nag_mip_sqp (h02da).

Output Parameters

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

May be set to a negative value if you wish to terminate the solution to the current problem, and in this case nag_mip_sqp (h02da) will terminate with ifail set to mode.

2:     $\mathrm{c}\left(\max \left(1,\mathbf{ncnln}\right)\right)$ – double array

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

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

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)$.

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

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

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

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

[mode, objmip, objgrd, user] = objfun(mode, n, varcon, x, objgrd, nstate, user)

Input Parameters

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

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.

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

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

3:     $\mathrm{varcon}\left(\mathbf{n}+\mathit{nclin}+\mathit{ncnln}\right)$ – int64int32nag_int array

The array varcon as supplied to nag_mip_sqp (h02da).

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

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

5:     $\mathrm{objgrd}\left(\mathbf{n}\right)$ – double array

Continuous elements of objgrd are set to the value of NaN.

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

If $\mathbf{nstate}=1$, nag_mip_sqp (h02da) 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.

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

objfun is called from nag_mip_sqp (h02da) with the object supplied to nag_mip_sqp (h02da).

Output Parameters

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

May be set to a negative value if you wish to terminate the solution to the current problem, and in this case nag_mip_sqp (h02da) will terminate with ifail set to mode.

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

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

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

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.

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

10:   $\mathrm{iopts}\left(:\right)$ – int64int32nag_int 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 nag_mip_optset (h02zk).

11:   $\mathrm{opts}\left(:\right)$ – double 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 nag_mip_optset (h02zk).

The real option array as returned by nag_mip_optset (h02zk).

Optional Input Parameters

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

Default: the dimension of the arrays bl, bu, x and the second dimension of the array a. (An error is raised if these dimensions are not equal.)

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

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

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

Default: the dimension of the array d and the first dimension of the array a. (An error is raised if these dimensions are not equal.)

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

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

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

Default: $500$

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.

4:     $\mathrm{acc}$ – double scalar

Default: $1.0e-4$

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 nag_machine_precision (x02aj)), the below suggested value is used.

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

user is not used by nag_mip_sqp (h02da), but is passed to confun and objfun. 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{ax}\left(\max \left(1,\mathbf{nclin}\right)\right)$ – double array

The final values of the linear constraints $Ax$.

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

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

The final estimate of the solution.

3:     $\mathrm{c}\left(\max \left(1,\mathbf{ncnln}\right)\right)$ – double array

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.

4:     $\mathrm{cjac}\left(\max \left(1,\mathbf{ncnln}\right),\mathbf{n}\right)$ – double array

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)$.

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.

5:     $\mathrm{objgrd}\left(\mathbf{n}\right)$ – double array

The objective function gradient at the solution.

6:     $\mathrm{objmip}$ – double scalar

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

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

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

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

Error Indicators and Warnings

   $\mathbf{ifail}=1$

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

   $\mathbf{ifail}=2$

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

   $\mathbf{ifail}=3$

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

   $\mathbf{ifail}=4$

Constraint: $\mathit{lda}\ge \mathbf{nclin}$.

   $\mathbf{ifail}=5$

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$

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

   $\mathbf{ifail}=7$

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. Exceeded the maximum number of iterations.

   $\mathbf{ifail}=1002$

More than the maximum number of feasible steps without improvement in the objective function.

   $\mathbf{ifail}=1003$

Penalty parameter tends to infinity in an underlying mixed-integer quadratic program; the problem may be infeasible.

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

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

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

Example

Open in the MATLAB editor: h02da_example

function h02da_example

  diary h02da_example.r
  fprintf('h02da example results\n\n');

  % Problem size
  n = int64(8);
  nclin = int64(5);
  ncnln = int64(2);

  varcon = zeros(n+nclin+ncnln, 1, 'int64');

  % Set variable types: continuous then binary
  varcon(1:4) = int64([0;0;0;0]);
  varcon(5:8) = int64([1;1;1;1]);

  bl = zeros(n,1);
  bu = zeros(n,1);

  % Set bounds of continuous variables
  bl(1:4) = 0;
  bu(1:4) = 1000;

  % Set linear constraints
  varcon(n+1)         = 3; % equality
  varcon(n+2:n+nclin) = 4; % inequality

  % Set Ax=d then Ax>=d
  a = zeros(nclin,n);
  a(1,1:4) = 1;
  a(2,[1,5]) = [-1,1];
  a(3,[2,6]) = [-1,1];
  a(4,[3,7]) = [-1,1];
  a(5,[4,8]) = [-1,1];

  d = zeros(nclin,1);
  d(1) = 1;

  % Set constraints supplied by confun, equality first
  varcon(n+nclin+1) = 3;
  varcon(n+nclin+2) = 4;

  iopts = zeros(200, 1, 'int64');
  opts = zeros(100, 1);

  % Initialize options
  [iopts, opts, ifail] = h02zk( ...
                                'Initialize = h02da', iopts, opts);

  % Optimisation parameters
  maxit =  int64(500);
  acc = 1e-6;

  x = zeros(n,1);
  % Initial estimate (binary variables need not be given)
  x(1:4) = 1;

  % Portfolio parameters
  user.p = 3;
  user.rho = 10;

  % Call the solver
  [ax, x, c, cjac, objgrd, objmip, user, ifail] = ...
  h02da( ...
         ncnln, a, d, bl, bu, varcon, x, @confun, @objfun, iopts, opts, ...
         'user', user);

  % Query the accuracy of the mixed integer QP solver
  [ivalue, accqp, cvalue, optype, ifail] = ...
    h02zl('QP Accuracy', iopts, opts);

  % Results
  [ifail] = x04ca('G', ' ', x, 'Final estimate');
  fprintf('\nMixed integer QP Accuracy: %g', accqp);
  fprintf('\nOptimised value: %g\n\n', objmip);


  diary off

function [mode, c, cjac, user] = ...
         confun(mode, ncnln, n, varcon, x, cjac, nstate, user)
  c = zeros(ncnln, 1);

  if (mode == 0)
    % Constraints
    % Mean return at least rho:
    c(1) = 8*x(1) + 9*x(2) + 12*x(3) + 7*x(4) - user.rho;

    % Maximum of p assets in portfolio:
    c(2) = user.p - x(5) - x(6) - x(7) - x(8);
  else
    % Jacobian
    cjac(1,1:4) = [8,9,12,7];

    % c(2) does not include continuous variables which requires
    % that their derivatives are zero
    cjac(2,1:4) = 0;
  end

function [mode, objmip, objgrd, user] = ...
         objfun(mode, n, varcon, x, objgrd, nstate, user)
  objmip = 0;

  if (mode == 0)
    % Objective value
    objmip = x(1)*(4*x(1)+3*x(2)-x(3)) + ...
             x(2)*(3*x(1)+6*x(2)+x(3)) + ...
             x(3)*(x(2)-x(1)+10*x(3));
  else
    % Objective gradients for continuous variables
    objgrd(1) = 8*x(1) +  6*x(2) -  2*x(3);
    objgrd(2) = 6*x(1) + 12*x(2) +  2*x(3);
    objgrd(3) = 2*(x(2)-x(1)) + 20*x(3);
    objgrd(4) = 0;
  end

h02da example results

 Final estimate
          1
 1   0.3750
 2   0.0000
 3   0.5250
 4   0.1000
 5   1.0000
 6   0.0000
 7   1.0000
 8   1.0000

Mixed integer QP Accuracy: 1e-10
Optimised value: 2.925

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

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.