naginterfaces.library.mip.sqp

naginterfaces.library.mip.sqp(ncnln, bl, bu, varcon, x, objfun, comm, a=None, d=None, confun=None, maxit=500, acc=0.0001, data=None, io_manager=None, spiked_sorder='C')[source]

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

Note: this function uses optional algorithmic parameters, see also: optset().

For full information please refer to the NAG Library document for h02da

https://www.nag.com/numeric/nl/nagdoc_28.5/flhtml/h/h02daf.html

Parameters
ncnlnint

, the number of constraints supplied by .

blfloat, array-like, shape

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.

bufloat, array-like, shape

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.

varconint, array-like, shape

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.

xfloat, array-like, shape

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.

objfuncallable (objmip, objgrd) = objfun(mode, varcon, x, objgrd, nstate, data=None)

must calculate the objective function and its gradient for a specified -element vector .

Parameters
modeint

Indicates which values must be assigned during each call of . Only the following values need be assigned:

The objective function value, .

The continuous elements of .

varconint, ndarray, shape

The array as supplied to sqp.

xfloat, ndarray, shape

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

objgrdfloat, ndarray, shape

Continuous elements of are set to the value of NaN.

nstateint

If , sqp is calling for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
objmipfloat

Must be set to the objective function value, .

objgrdfloat, array-like, shape

Must contain the gradient vector of the objective function if , with containing the partial derivative of with respect to continuous variable ; otherwise is not referenced.

commdict, communication object

Communication structure.

This argument must have been initialized by a prior call to optset().

aNone or float, array-like, shape , optional

Note: the required extent for this argument in dimension 2 is determined as follows: if : ; otherwise: .

The th row of must contain the coefficients of the th general linear constraint, for . Any equality constraints must be specified first.

If , the array is not referenced.

dNone or float, array-like, shape , optional

, the constant for the th linear constraint.

If , the array is not referenced.

confunNone or callable (c, cjac) = confun(mode, varcon, x, cjac, nstate, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

must calculate the constraint functions supplied by and their Jacobian at . If all constraints are supplied by and (i.e., ), will never be called by sqp and may be None. If , the first call to will occur after the first call to .

Parameters
modeint

Indicates which values must be assigned during each call of . Only the following values need be assigned:

Elements of containing continuous variables.

Elements of containing continuous variables.

varconint, ndarray, shape

The array as supplied to sqp.

xfloat, ndarray, shape

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

cjacfloat, ndarray, shape

Note: the derivative of the th constraint with respect to the th variable, , is stored in .

Continuous elements of are set to the value of NaN.

nstateint

If , sqp is calling for the first time. This argument setting allows you to save computation time if certain data must be read or calculated only once.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
cfloat, array-like, shape

Must contain constraint values, with the value of the th constraint in .

cjacfloat, array-like, shape

The th row of must contain elements of for each continuous variable .

maxitint, optional

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

accfloat, optional

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

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

spiked_sorderstr, optional

If is spiked (i.e., has unit extent in all but one dimension, or has size ), selects the storage order to associate with it in the NAG Engine:

spiked_sorder =

row-major storage will be used;

spiked_sorder =

column-major storage will be used.

Two-dimensional arrays returned from callback functions in this routine must then use the same storage order.

Returns
axfloat, ndarray, shape

The final residuals of the linear constraints .

If , is not referenced.

xfloat, ndarray, shape

The final estimate of the solution.

cfloat, ndarray, shape

If , contains the value of the th constraint function at the final iterate, for .

If , the array is not referenced.

cjacfloat, ndarray, shape

If , 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 , for . (See the discussion of argument under .)

If , the array is not referenced.

objgrdfloat, ndarray, shape

The objective function gradient at the solution.

objmipfloat

With no exception or warning is raised, contains the value of the objective function for the MINLP solution.

Other Parameters
‘Branch Bound Steps’int

Default

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

‘Branching Rule’str

Default

Branching rule for branch and bound search.

Maximum fractional branching.

Minimum fractional branching.

‘Check Gradients’str

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’float

Default

Initial continuous trust region radius, ; the initial trial step for the SQP approximation must satisfy .

‘Descent’float

Default

Initial descent parameter, , larger values of allow penalty option to increase faster which can lead to faster convergence.

‘Descent Factor’float

Default

Factor for decreasing the internal descent parameter, , between iterations.

‘Feasible Steps’int

Default

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

‘Improved Bounds’str

Default

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

‘Integer Trust Radius’float

Default

Initial integer trust region radius, ; the initial trial step for the SQP approximation must satisfy .

‘Maximum Restarts’int

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.

‘Minor Print Level’int

Default

Print level of the subproblem solver. Active only if .

‘Modify Hessian’str

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’str

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.

‘Non Monotone’int

Default

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

‘Objective Scale Bound’float

Default

When internally scale absolute function values greater than or ‘Objective Scale Bound’.

‘Penalty’float

Default

Initial penalty option, .

‘Penalty Factor’float

Default

Factor for increasing penalty option when the trust regions cannot be enlarged at a trial step.

‘Print Level’int

Default

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’float

Default

Termination tolerance of the relaxed quadratic program subproblems.

‘Scale Continuous Variables’str

Default

Internally scale continuous variables values.

‘Scale Objective Function’int

Default

Internally scale objective function values.

No scaling.

Scale absolute values greater than ‘Objective Scale Bound’.

‘Warm Starts’int

Default

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

Raises
NagValueError
(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: , for .

(errno )

On entry, .

Constraint: , or , for .

(errno )

On entry, .

Constraint: or , for .

(errno )

The supplied returned a NaN value.

(errno )

The supplied returned a NaN value.

(errno )

On entry, the option arrays [‘iopts’] and [‘opts’] have either not been initialized or been corrupted.

(errno )

On entry, there are no binary or integer variables.

(errno )

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

(errno )

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

(errno )

One or more objective gradients appear to be incorrect.

(errno )

One or more constraint gradients appear to be incorrect.

(errno )

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

(errno )

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 .

Option .

(errno )

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

(errno )

Termination with zero integer trust region for integer variables; try a different starting value.

Option .

(errno )

The optimization failed due to numerical difficulties. Set option for more information.

Warns
NagAlgorithmicWarning
(errno )

On entry, . Exceeded the maximum number of iterations.

NagCallbackTerminateWarning
(errno )

The optimization halted because you set negative in or negative in , to .

Notes

sqp 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 The Quasi-Newton Update for opt.nlp1_solve) 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 sqp.

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