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_29.3/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