KNITRO

Introduction

Artelys Knitro is a software package for finding local solutions of both continuous (i.e. smooth) optimization problems, with or without constraints, and discrete optimization problems with integer or binary variables. Even though Knitro has been designed for solving large-scale general problems, it is efficient for solving all of the following classes of optimization problems:

  • unconstrained,
  • bound constrained,
  • equality constrained,
  • systems of nonlinear equations,
  • least squares problems,
  • linear programming problems (LPs),
  • quadratic programming problems (QPs),
  • general (inequality) constrained problems,
  • (convex) mixed integer nonlinear programs (MINLP) of moderate size.

The Knitro package provides the following features:

  • Efficient and robust solution of small or large problems,
  • Solvers for both continuous and discrete problems,
  • Derivative-free, 1st derivative and 2nd derivative options,
  • Both interior-point (barrier) and active-set optimizers,
  • Both feasible and infeasible versions,
  • Both iterative and direct approaches for computing steps,

The problems solved by Knitro have the form

\[ \begin{array}{rclr} \mbox{minimize} & \qquad \qquad & f(x) & \qquad \qquad \qquad (1a) \\ \mbox{subject to} & \qquad \qquad & c^L \leq c(x) \leq c^U & \qquad \qquad \qquad (1b) \\ & \qquad \qquad & b^L \leq x \leq b^U, & \qquad \qquad \qquad (1c) \end{array} \]

where the variables \(x\) can be continuous, binary, or integer. This allows many forms of constraints, including bounds on the variables. Knitro requires that the functions \(f(x)\) and \(c(x)\) be smooth functions.

Knitro implements both state-of-the-art interior-point and active-set methods for solving nonlinear optimization problems. In the interior method (also known as a barrier method), the nonlinear programming problem is replaced by a series of barrier sub-problems controlled by a barrier parameter \(\mu\). The algorithm uses trust regions and a merit function to promote convergence. The algorithm performs one or more minimization steps on each barrier problem, then decreases the barrier parameter, and repeats the process until the original problem (1) has been solved to the desired accuracy.

Knitro provides two procedures for computing the steps within the interior point approach. In the version known as Interior/CG each step is computed using a projected conjugate gradient iteration. This approach differs from most interior methods proposed in the literature in that it does not compute each step by solving a linear system involving the KKT (or primal-dual) matrix. Instead, it factors a projection matrix, and uses the conjugate gradient method, to approximately minimize a quadratic model of the barrier problem.

The second procedure for computing the steps, which we call Interior/Direct, always attempts to compute a new iterate by solving the primal-dual KKT matrix using direct linear algebra. In the case when this step cannot be guaranteed to be of good quality, or if negative curvature is detected, then the new iterate is computed by the Interior/CG procedure.

Knitro also implements an active-set sequential linear-quadratic programming (SLQP) algorithm which we call Active. This method is similar in nature to a sequential quadratic programming method but uses linear programming sub-problems to estimate the active-set at each iteration. This active-set code may be preferable when a good initial point can be provided, for example, when solving a sequence of related problems.

For problems with discrete variables, Knitro provides two variants of the branch and bound algorithm. The first is a standard implementation, while the second is specialized for convex, mixed-integer nonlinear problems.

We encourage the user to try all algorithmic options to determine which one is more suitable for the application at hand. For guidance on choosing the best algorithm see section Algorithm Options .

For a detailed description of the algorithm implemented in Interior/CG see [50] and for the global convergence theory see [51] . The method implemented in Interior/Direct is described in [249] . The Active algorithm is described in [53] and the global convergence theory for this algorithm is in [54] . An important component of Knitro is the HSL routine MA27 [119] which is used to solve the linear systems arising at every iteration of the algorithm. In addition, the Active Set algorithm in Knitro may make use of the COIN-OR Clp linear programming solver module. The version used in Knitro may be downloaded from http://www.artelys.com/tools/clp/.

Usage

Basic details of solver usage, including how to choose Knitro as the solver and how to use a solver-specific option file, are part of Chapter Solver Usage.

As an NLP solver, Knitro can also be used to solve linear programs (LP), and both convex and nonconvex quadratic programs (QCP).

GAMS Options

The following GAMS options are used by the GAMS/Knitro link:

  • Option ResLim = x;

    Sets the time limit in seconds. If this limit is exceeded the solver will terminate and pass on the current solution to GAMS. See also reslim in section GAMS options .

  • Option SysOut = On;

    This option sends additional Knitro messages to the GAMS listing file. It is useful in case of a solver failure or to get algorithmic details. See also sysout in section GAMS options

  • ModelName.optCA = x;

    Absolute gap stop criterion for a discrete problem. The Knitro option mip_integral_gap_abs takes its default from this value. See also optca in section GAMS options.

  • ModelName.optCR = x;

    Relative gap stop criterion for a discrete problem. The Knitro option mip_integral_gap_rel takes its default from this value. See also optcr in section GAMS options.

Summary of Knitro Options

The Knitro options file knitro.opt allows the user to easily set options controlling Knitro's behavior. Options are set by specifying a keyword and a corresponding value on a line in the knitro.opt file. Lines that begin with a # character are treated as comments and blank lines are ignored. For example, to set the maximum allowable number of iterations to 500, one could use the following options file:

Barrier options

Option Description Default
bar_directinterval limit on consecutive CG steps before Knitro will try to force a direct linear algebra step 10
bar_feasible specifies whether special emphasis is placed on getting and staying feasible 0
bar_feasmodetol tolerance for activation of bar_feasible mode 1e-4
bar_initmu initial barrier parameter value 1e-1
bar_initpt initial point strategy for barrier algorithms 0
bar_maxbacktrack limit on backtracks during the linesearch of the Interior/Direct algorithm 3
bar_maxcrossit limit on crossover iterations 0
bar_maxrefactor limit on KKT refactorizations per iteration of the Interior/Direct algorithm auto
bar_murule controls the barrier parameter update strategy 0
bar_pencons controls whether a penalty approach is applied to the constraints auto
bar_penrule controls penalty parameter strategy used to accept a trial iterate auto
bar_refinement toggles barrier solution refinement method 0
bar_relaxcons controls application of a relaxation approach to the constraints 2
bar_switchrule controls switch to new feasibility-only phase 0
bar_watchdog toggles watchdog heuristic for barrier algorithms 0

General options

Option Description Default
act_qpalg controls choice of algorithm used for QP subproblems when in active-set mode 0
algorithm controls which algorithm to use 0
blasoption specifies the BLAS/LAPACK function library to use for basic vector and matrix computations 1
datacheck toggles KNITRO check for structural errors in problem input 0
delta initial trust region radius scaling factor 1e-0
feastol relative feasibility error tolerance 1e-6
feastolabs absolute feasibility error tolerance 1.0e-3
fstopval custom stopping condition on objective value none
ftol control termination based on successive small objective changes 1e-15
ftol_iters control termination based on successive small objective changes 5
gradopt controls gradient computation 1
hessopt controls Hessian computation 1
honorbnds maintain feasibility of intermediate iterates w.r.t. variable bounds 0
infeastol controls relative tolerance for declaring a model infeasible 1e-8
linsolver controls which linear system solver to use 0
linsolver_ooc controls out-of-core behavior for MKL PARDISO 0
lmsize controls number of limited-memory pairs stored for quasi-Newton BFGS 10
maxcgit limit on inner CG iterations per minor iteration 0
maxfevals controls the maximum number of function evaluations before termination unlimited
maxit major iteration limit 0
maxtime_cpu CPU time limit 1e8
maxtime_real real or wall-clock time limit 1e8
objrange parameter used in unboundedness check 1e20
option_file additional option file name - read only by KNITRO solver lib
opttol relative optimality error tolerance 1e-6
opttolabs absolute optimality error tolerance 1.0e-3
outlev controls the level of output 2
output_time print output on where time is used 0
par_blasnumthreads number of threads to use for BLAS operations 1
par_lsnumthreads number of threads to use for PARDISO linear system solver 1
pivot initial pivot threshold used in the factorization routine 1e-8
presolve controls presolve level 1
presolve_tol controls presolver tolerance 1e-6
reform allow objective reformulation 1
scale toggles problem scaling 1
soc toggles the second order correction option 1
threads default thread count 1
xtol tolerance for termination on a small stepsize 1e-15

Multi-algorithm options

Option Description Default
ma_maxtime_cpu cumulative CPU time limit for multi-algorithm method 1e8
ma_maxtime_real cumulative real or wall-clock time limit for multi-algorithm method 1e8
ma_terminate condition for terminating the multi-algorithm method 1

MIP options

Option Description Default
mip_branchrule branching rule to use for MIP B&B 0
mip_gub_branch toggles branching on generalized upper bounds 0
mip_heuristic MIP heuristic to use in searching for an initial integer feasible point 0
mip_heuristic_maxit maximum iterations to allow the MIP heuristic 100
mip_implications toggles addition of constraints derived from logical implications 1
mip_integer_tol integrality tolerance 1e-8
mip_integral_gap_abs absolute stopping tolerance for MIP 1e-6
mip_integral_gap_rel relative stopping tolerance for MIP 1e-6
mip_knapsack knapsack cut generation control 1
mip_lpalg algorithm to use for LP subproblems 0
mip_maxnodes maximum number of nodes to explore: 0=no limit 100000
mip_maxsolves maximum number of subproblem solves: 0=no limit 200000
mip_maxtime_cpu cumulative CPU time limit for MIP 1e8
mip_maxtime_real cumulative real or wall-clock time limit for MIP 1e8
mip_method specify MIP method to use 0
mip_nodealg algorithm to use for MIP B&B subproblems 0
mip_outinterval node printing interval for MIP 10
mip_outlevel how much MIP information to print 1
mip_pseudoinit pseudocost initialization method control 0
mip_relaxable specifies whether integer variables are relaxable 1
mip_rootalg algorithm to use for the root node solve 0
mip_rounding MIP rounding rule to apply 0
mip_selectrule selection rule for the next node in the B&B tree 0
mip_strong_candlim max candidates to explore in strong branching 10
mip_strong_level max levels on which to perform strong branching 10
mip_strong_maxit max iterations to allow for strong branching 1000
mip_terminate condition for terminating the MIP algorithm 0

Multi-start options

Option Description Default
ms_deterministic allow for deterministic parallel MS if ms_terminate=0 1
ms_enable toggles multi-start method 0
ms_maxbndrange maximum range to vary unbounded x when generating start points 1e3
ms_maxsolves maximum number of start points to try during multi-start auto
ms_maxtime_cpu cumulative CPU time limit for multi-start 1e8
ms_maxtime_real cumulative real or wall-clock time limit for multi-start 1e8
ms_seed random seed for generating start points 0
ms_startptrange maximum range to vary all x when generating start points 1e20
ms_terminate termination condition for multi-start 0

Tuner options

Option Description Default
tuner enable Tuner 0
tuner_maxtimecpu CPU time limit for Tuner run 1e8
tuner_maxtimereal real time limit for Tuner run 1e8
tuner_optionsfile specify Tuner options file
tuner_outsub control additional Tuner subproblem solve output files 0
tuner_terminate termination condition for Tuner run 0

Detailed Descriptions of Knitro Options

act_qpalg (integer): controls choice of algorithm used for QP subproblems when in active-set mode

Default: 0

valuemeaning
0 automatic, based on problem characteristics
1 interior/direct
2 interior/CG
3 active-set

algorithm (integer): controls which algorithm to use

Default: 0

valuemeaning
0 automatic, based on problem characteristics
1 interior/direct
2 interior/CG
3 active-set CG method
4 active-set SQP method
5 multi-method, perhaps in parallel

bar_directinterval (integer): limit on consecutive CG steps before Knitro will try to force a direct linear algebra step

Range: [0, ∞]

Default: 10

bar_feasible (integer): specifies whether special emphasis is placed on getting and staying feasible

Indicates whether or not to use the feasible version of Knitro.

NOTE: This option can be used only with the Interior/CG and Interior/Direct algorithms, i.e. when algorithm=2 or algorithm=3. See section Feasible version for more details.

Options 1 and 3 above activate the feasible version of KNITRO. Given an initial point which sufficiently satisfies all inequality constraints as defined by,

\begin{equation} cl + tol \le c(x) \le cu - tol \end{equation}

(for \(cl \ne cu\)), the feasible version of Knitro ensures that all subsequent solution estimates strictly satisfy the inequality constraints. However, the iterates may not be feasible with respect to the equality constraints. The tolerance \(tol>0\) in (2) for determining when the feasible mode is active is determined by the double precision parameter bar_feasmodetol described below. This tolerance (i.e. bar_feasmodetol) must be strictly positive. That is, in order to enter feasible mode, the point given to Knitro must be strictly feasible with respect to the inequality constraints.

If the initial point is infeasible (or not sufficiently feasible according to (2)) with respect to the inequality constraints, then Knitro will run the infeasible version until a point is obtained which sufficiently satisfies all the inequality constraints. At this point it will switch to feasible mode.

Default: 0

valuemeaning
0 No special emphasis on feasibility
1 Iterates must satisfy inequality cons once they become sufficiently feasible
2 Special emphasis is placed on getting feasible before trying to optimize
3 Implement both options 1 and 2 above

bar_feasmodetol (real): tolerance for activation of bar_feasible mode

Specifies the tolerance in (2) by which the iterate must be feasible with respect to the inequality constraints before the feasible mode becomes active. This option is only relevant when feasible=1.

Default: 1e-4

bar_initmu (real): initial barrier parameter value

Specifies the initial value for the barrier parameter \(\mu\).

Default: 1e-1

bar_initpt (integer): initial point strategy for barrier algorithms

Indicates whether an initial point strategy is used.

Default: 0

valuemeaning
0 let KNITRO choose the initial point strategy
1 initialization strategy 1
2 initialization strategy 2
3 initialization strategy 3

bar_maxbacktrack (integer): limit on backtracks during the linesearch of the Interior/Direct algorithm

Indicates the maximum allowable number of backtracks during the linesearch of the Interior/Direct algorithm before reverting to a CG step.

Increasing this value will make the Interior/Direct algorithm less likely to take CG steps. If the Interior/Direct algorithm is taking a large number of CG steps (as indicated by a positive value for "CGits" in the output), this may improve performance. This option has no effect on the Active Set algorithm.

Default: 3

bar_maxcrossit (integer): limit on crossover iterations

Specifies the maximum number of crossover iterations before termination. If the value is positive, then KNITRO will crossover from the barrier to the Active Set algorithm near the solution. The Active Set algorithm will then perform at most n iterations to get a more exact solution. If the value is 0, no Active Set crossover occurs and the interior-point solution is the final result.

If Active Set crossover is unable to improve the approximate interior-point solution, then KNITRO will restore the interior-point solution. In some cases (especially on large-scale problems or difficult degenerate problems) the cost of the crossover procedure may be significant - for this reason, crossover is disabled by default. Enabling crossover generally provides a more accurate solution than Interior/Direct or Interior/CG.

Default: 0

bar_maxrefactor (integer): limit on KKT refactorizations per iteration of the Interior/Direct algorithm

Indicates the maximum number of refactorizations of the KKT system per iteration of the Interior/Direct algorithm before reverting to a CG step. If this value is set to -1, it will use a dynamic strategy.

These refactorizations are performed if negative curvature is detected in the model. Rather than reverting to a CG step, the Hessian matrix is modified in an attempt to make the subproblem convex and then the KKT system is refactorized. Increasing this value will make the Interior/Direct algorithm less likely to take CG steps. If the Interior/Direct algorithm is taking a large number of CG steps (as indicated by a positive value for "CGits" in the output), this may improve performance. This option has no effect on the Active Set algorithm.

Range: [-1, ∞]

Default: auto

bar_murule (integer): controls the barrier parameter update strategy

NOTE: Only strategies 0-2 are available for the Interior/CG algorithm. All strategies are available for the Interior/Direct algorithm. Strategies 4 and 5 are typically recommended for linear programs or convex quadratic programs.

Default: 0

valuemeaning
0 automatically choose the rule for updating the barrier parameter
1 monotonically decrease the barrier parameter
2 use an adaptive rule based on the complementarity gap to determine the value of the barrier parameter at every iteration
3 use a probing (affine-scaling) step
4 use a Mehrotra predictor-corrector type rule, with safeguards on the corrector step
5 use a Mehrotra predictor-corrector type rule, with no safeguards on the corrector step
6 minimize a quality function at each iteration

bar_pencons (integer): controls whether a penalty approach is applied to the constraints

Default: auto

valuemeaning
0 automatic
1 no constraints are penalized
2 a penalty approach is applied to all general constraints

bar_penrule (integer): controls penalty parameter strategy used to accept a trial iterate

Default: auto

valuemeaning
0 automatic
1 use a single penalty parameter in the merit function to weight feasibility versus optimality
2 use a more tolerant and flexible step acceptance procedure

bar_refinement (boolean): toggles barrier solution refinement method

Default: 0

bar_relaxcons (integer): controls application of a relaxation approach to the constraints

Using a relaxation approach may be helpful when the problem has degenerate or difficult constraints. This option has no effect on the Active Set algorithm.

Default: 2

valuemeaning
0 no constraints are relaxed
1 general equality constraints are relaxed
2 general inequality constraints are relaxed
3 all general constraints are relaxed

bar_switchrule (integer): controls switch to new feasibility-only phase

NOTE: The feasibility-only phase is new in Knitro 8.0. To get the behavior of older Knitro versions, choose strategy 1 (never switch).

Default: 0

valuemeaning
0 automatic
1 never switch to feasibility phase
2 allow switches to feasibility phase
3 more aggressive switches to feasibility phase

bar_watchdog (boolean): toggles watchdog heuristic for barrier algorithms

In general, enabling the watchdog heuristic makes the barrier algorithms more likely to accept trial points. Specifically, the watchdog heuristic may occasionally accept trial points that increase the merit function, provided that subsequent iterates decrease the merit function.

Default: 0

blasoption (integer): specifies the BLAS/LAPACK function library to use for basic vector and matrix computations

BLAS and LAPACK functions from the Intel Math Kernel Library (MKL) are provided with the Knitro solver. The MKL is available for Windows, Linux, and Mac OS X; it is not available for Solaris. The number of threads to use for the MKL BLAS are specified via the par_blasnumthreads option.

BLAS (Basic Linear Algebra Subroutines) and LAPACK (Linear Algebra PACKage) functions are used throughout Knitro for fundamental vector and matrix calculations. Some optimization problems are observed to spend very little CPU time in BLAS/LAPACK operations, while others spend more than 50% there. Be aware that the different implementations can return slightly different results. Thus, changing the value of blasoption can alter the iterates generated by Knitro, or even the final solution point.

Setting blasoption=0 (the Knitro option) uses built-in BLAS/LAPACK functions based on standard netlib routines (www.netlib.org). The Intel option blasoption=1 uses MKL functions written especially for x86 and x86_64 processor architectures. On a machine running an Intel processor (e.g., Pentium 4), testing indicates that the MKL functions can significantly reduce the CPU time in BLAS/LAPACK operations.

Default: 1

valuemeaning
0 use Knitro built-in functions
1 use Intel MKL functions on supported platforms

datacheck (boolean): toggles KNITRO check for structural errors in problem input

Default: 0

delta (real): initial trust region radius scaling factor

Specifies the initial trust region radius scaling factor used to determine the initial trust region size.

Default: 1e-0

feastol (real): relative feasibility error tolerance

Specifies the final relative stopping tolerance for the feasibility error. Smaller values of feastol result in a higher degree of accuracy in the solution with respect to feasibility.

Default: 1e-6

feastolabs (real): absolute feasibility error tolerance

Synonym: feastol_abs

Specifies the final absolute stopping tolerance for the feasibility error. Smaller values of feastolabs result in a higher degree of accuracy in the solution with respect to feasibility.

Default: 1.0e-3

fstopval (real): custom stopping condition on objective value

Knitro will stop and declare that a satisfactory solution was found if a feasible objective function value at least as good as fstopval is achieved.

Default: none

ftol (real): control termination based on successive small objective changes

The optimization process will terminate if the relative change in the objective function is less than ftol for ftol_iters consecutive iterations.

Range: [0, ∞]

Default: 1e-15

ftol_iters (integer): control termination based on successive small objective changes

The optimization process will terminate if the relative change in the objective function is less than ftol for ftol_iters consecutive iterations.

Range: [1, ∞]

Default: 5

gradopt (integer): controls gradient computation

Specifies how to compute the gradients of the objective and constraint functions.

Default: 1

valuemeaning
1 use exact gradients computed by GAMS
2 KNITRO computes gradients by forward finite differences
3 KNITRO computes gradients by central finite differences

hessopt (integer): controls Hessian computation

Specifies how to compute the (approximate) Hessian of the Lagrangian.

NOTE: In nearly all cases it is strongly recommended to use the exact Hessian option (option 1) or the exact Hessian-vector product option (option 5).

If exact Hessians (or exact Hessian-vector products) are not efficient to compute but exact gradients are provided and are not too expensive to compute, option \(4\) above is typically recommended. The finite-difference Hessian-vector option is comparable in terms of robustness to the exact Hessian option (assuming exact gradients are provided) and typically not too much slower in terms of time if gradient evaluations are not the dominant cost.

In the event that the exact Hessian (or Hessian-vector products) are too expensive to compute, multiple quasi-Newton options which internally approximate the Hessian matrix using first derivative information are provided. Options 2 and 3 are only recommended for small problems ( \(n < 1000\) ) since they require working with a dense Hessian approximation. Option 6 should be used in the large-scale case.

NOTE: Options hessopt= and hessopt=5 are not available when algorithm=1. See section

"Second derivative options" for more detail on second derivative options.

Default: 1

valuemeaning
1 use exact Hessians computed by GAMS
2 use a dense quasi-Newton BFGS Hessian
3 use a dense quasi-Newton SR1 Hessian
4 compute Hessian-vector products using finite differences
5 use exact Hessian-vector products computed by GAMS
6 use a limited-memory quasi-Newton BFGS Hessian

honorbnds (integer): maintain feasibility of intermediate iterates w.r.t. variable bounds

Indicates whether or not to enforce satisfaction of the simple bounds (1c) throughout the optimization (see section Honor Bounds).

Default: 0

valuemeaning
0 does not enforce that the bounds on the variables are satisfied at intermediate iterates
1 enforces that the initial point and all subsequent solution estimates satisfy the bounds on the variables
2 enforces that the initial point satisfies the bounds on the variables

infeastol (real): controls relative tolerance for declaring a model infeasible

Smaller values make it more difficult to satisfy the conditions Knitro uses for detecting infeasible models. If you believe Knitro incorrectly declares a model to be infeasible, you should try a smaller value for infeastol.

Default: 1e-8

linsolver (integer): controls which linear system solver to use

Indicates which linear solver to use to solve linear systems arising in KNITRO algorithms.

Default: 0

valuemeaning
0 automatic: based on problem characteristics
1 internal: reserved for internal use, currently automatic
2 hybrid: linear solver used depends on the particular linear system to be solved
3 QR: use dense LAPACK QR routines, only suitable for small problems
4 MA27: use the HSL MA27 sparse symmetric indefinite solver
5 MA57: use the HSL MA57 sparse symmetric indefinite solver
6 PARDISO: use the Intel MKL PARDISO sparse symmetric indefinite solver

linsolver_ooc (integer): controls out-of-core behavior for MKL PARDISO

Indicates whether to use out-of-core solve of linear systems when using Intel MKL PARDISO as the linear solver. N.B.: this option is only active when linsolver=6.

Default: 0

valuemeaning
0 no: do not use MKL PARDISO out-of-core option
1 automatic: MKL PARDISO decides whether to use out-of-core option
2 yes: do use MKL PARDISO out-of-core option

lmsize (integer): controls number of limited-memory pairs stored for quasi-Newton BFGS

Specifies the number of limited-memory pairs stored when approximating the Hessian using the limited-memory quasi-Newton BFGS option ( hessopt=6). Larger values may give a more accurate, but more expensive, Hessian approximation. Smaller values may give a less accurate, but faster, Hessian approximation. When using the limited memory BFGS approach it is recommended to experiment with different values of this parameter.

Range: [1, 100]

Default: 10

maxcgit (integer): limit on inner CG iterations per minor iteration

Specifies the maximum allowable number of inner conjugate gradient (CG) iterations per KNITRO minor iteration.

Default: 0

valuemeaning
0 upper bound determined automatically
n at most n CG iterations may be performed

maxfevals (integer): controls the maximum number of function evaluations before termination

Default: unlimited

valuemeaning
-1 unlimited
n at most n >= 0 function evaluations may be performed

maxit (integer): major iteration limit

Specifies the maximum number of iterations before termination.

Default: 0

valuemeaning
0 automatically determines a value based on the problem size. Currently KNITRO 7.0 sets this value to10000 for LPs/NLPs and 3000 for MIPs/MINLPs
n At most n iterations may be performed before terminating, where \(n > 0\).

maxtime_cpu (real): CPU time limit

Specifies the CPU time limit, in seconds.

Default: 1e8

maxtime_real (real): real or wall-clock time limit

Specifies the real or wall-clock time limit, in seconds.

Default: 1e8

ma_maxtime_cpu (real): cumulative CPU time limit for multi-algorithm method

Default: 1e8

ma_maxtime_real (real): cumulative real or wall-clock time limit for multi-algorithm method

Default: 1e8

ma_terminate (integer): condition for terminating the multi-algorithm method

Default: 1

valuemeaning
0 terminate after all algorithms have completed
1 terminate at first local optimum
2 terminate at first feasible solution

mip_branchrule (integer): branching rule to use for MIP B&B

Branching rule to use for MIP B&B.

Default: 0

valuemeaning
0 automatic
1 use most fractional (most infeasible) branching
2 use pseudo-cost branching
3 use strong branching

mip_gub_branch (boolean): toggles branching on generalized upper bounds

Toggles branching on generalized upper bounds.

Default: 0

mip_heuristic (integer): MIP heuristic to use in searching for an initial integer feasible point

Heuristic to use in searching for an initial integer feasible point.

Default: 0

valuemeaning
0 automatic
1 none
2 feasibility pump
3 heuristic based on MPEC formulation

mip_heuristic_maxit (integer): maximum iterations to allow the MIP heuristic

Specifies the maximum number of iterations to allow for MIP heuristic, if one is enabled.

Default: 100

mip_implications (boolean): toggles addition of constraints derived from logical implications

Toggles addition of constraints derived from logical implications

Default: 1

mip_integer_tol (real): integrality tolerance

Specifies the integrality tolerance for discrete variables.

Default: 1e-8

mip_integral_gap_abs (real): absolute stopping tolerance for MIP

The absolute integrality gap stop tolerance. If not set by the user, the GAMS optCA value is used.

Default: 1e-6

mip_integral_gap_rel (real): relative stopping tolerance for MIP

The relative integrality gap stop tolerance. If not set by the user, the GAMS optCA value is used.

Default: 1e-6

mip_knapsack (integer): knapsack cut generation control

Default: 1

valuemeaning
0 none
1 only for inequalities
2 for inequalities and equalities

mip_lpalg (integer): algorithm to use for LP subproblems

Specifies which algorithm to use for any LP subproblem solves that may occur in the B&B procedure. LP subproblems may arise if the problem has no nonlinear parts or if using mip_method=2.

Default: 0

valuemeaning
0 automatically try to choose the best algorithm based on the problem characteristics
1 use the Interior/Direct algorigthm
2 use the Interior/CG algorigthm
3 use the Active Set (simplex) algorigthm

mip_maxnodes (integer): maximum number of nodes to explore: 0=no limit

Specifies the maximum number of nodes explored (0 means no limit)

Default: 100000

mip_maxsolves (integer): maximum number of subproblem solves: 0=no limit

Specifies the maximum number of subproblem solves allowed (0 means no limit).

Default: 200000

mip_maxtime_cpu (real): cumulative CPU time limit for MIP

Specifies the cumulative CPU time limit, in seconds.

Default: 1e8

mip_maxtime_real (real): cumulative real or wall-clock time limit for MIP

Specifies the cumulative real or wall-clock time limit, in seconds.

Default: 1e8

mip_method (integer): specify MIP method to use

Specifies which method to use.

Default: 0

valuemeaning
0 automatic
1 standard branch and bound method
2 hybrid Quesada-Grossman method (for convex, nonlinear problems only)
3 MISQP method: allows nonconvex and/or non-relaxable models

mip_nodealg (integer): algorithm to use for MIP B&B subproblems

Previously, this behavior was specified with the algorithm option. If specified, this option now takes precedence.

Default: 0

valuemeaning
0 automatic, based on problem characteristics
1 interior/direct
2 interior/CG
3 active-set CG method
4 active-set SQP method
5 multi-method, perhaps in parallel

mip_outinterval (integer): node printing interval for MIP

Specifies node printing interval for mip_outlevel when mip_outlevel > 0.

Range: [1, ∞]

Default: 10

mip_outlevel (integer): how much MIP information to print

Specifies how much MIP information to print.

Default: 1

valuemeaning
0 do not print any MIP node information
1 print one line of output for every node

mip_pseudoinit (integer): pseudocost initialization method control

Default: 0

valuemeaning
0 automatic
1 use average value
2 use strong branching

mip_relaxable (boolean): specifies whether integer variables are relaxable

This option only applies to the MISQP method, i.e. when mip_method=3.

Default: 1

mip_rootalg (integer): algorithm to use for the root node solve

Specifies which algorithm to use for the root node solve.

Default: 0

valuemeaning
0 automatic, based on problem characteristics
1 interior/direct
2 interior/CG
3 active-set method

mip_rounding (integer): MIP rounding rule to apply

Specifies the rounding rule to apply.

Default: 0

valuemeaning
0 automatic
1 do not round if a node is infeasible
2 round using a fast heuristic only
3 round and solve a subproblem if likely to succeed
4 always round and solve a subproblem

mip_selectrule (integer): selection rule for the next node in the B&B tree

Specifies the select rule for choosing the next node in the tree.

Default: 0

valuemeaning
0 automatic
1 search using a depth first procedure
2 select the node with the best relaxation bound
3 use depth first unless pruned, then best bound

mip_strong_candlim (integer): max candidates to explore in strong branching

Specifies the maximum number of candidates to explore for strong branching.

Default: 10

mip_strong_level (integer): max levels on which to perform strong branching

Specifies the maximum number of tree levels on which to perform strong branching.

Default: 10

mip_strong_maxit (integer): max iterations to allow for strong branching

Specifies the maximum number of iterations to allow for strong branching.

Default: 1000

mip_terminate (integer): condition for terminating the MIP algorithm

Specifies conditions for terminating the MIP algorithm.

Default: 0

valuemeaning
0 terminate at optimum
1 terminate at first integer feasible point

ms_deterministic (boolean): allow for deterministic parallel MS if ms_terminate=0

Default: 1

ms_enable (boolean): toggles multi-start method

Toggles multi-start method.

Default: 0

ms_maxbndrange (real): maximum range to vary unbounded x when generating start points

Maximum range to vary unbounded x when generating start points.

Default: 1e3

ms_maxsolves (integer): maximum number of start points to try during multi-start

Specifies the maximum number of start points to try during multi-start.

Default: auto

valuemeaning
0 KNITRO sets the number based on problem size
n try exactly n > 0 start points

ms_maxtime_cpu (real): cumulative CPU time limit for multi-start

Specifies the cumulative CPU time limit, in seconds.

Default: 1e8

ms_maxtime_real (real): cumulative real or wall-clock time limit for multi-start

Specifies the cumulative real or wall-clock time limit, in seconds.

Default: 1e8

ms_seed (integer): random seed for generating start points

Default: 0

ms_startptrange (real): maximum range to vary all x when generating start points

Maximum range to vary all x when generating start points.

Default: 1e20

ms_terminate (integer): termination condition for multi-start

Specifies conditions for terminating the multi-start algorithm.

Default: 0

valuemeaning
0 terminate after ms_maxsolves
1 terminate at first local optimum (if before ms_maxsolves)
2 terminate at first feasible solution (if before ms_maxsolves)
3 terminate at first solver completion

objrange (real): parameter used in unboundedness check

Specifies the extreme limits of the objective function for purposes of determining unboundedness. If the magnitude of the objective function is greater than objrange and the iterate is feasible, then the problem is determined to be unbounded and Knitro proceeds no further.

Default: 1e20

option_file (string): additional option file name - read only by KNITRO solver lib

opttol (real): relative optimality error tolerance

Specifies the final relative stopping tolerance for the KKT (optimality) error. Smaller values of opttol result in a higher degree of accuracy in the solution with respect to optimality.

Default: 1e-6

opttolabs (real): absolute optimality error tolerance

Synonym: opttol_abs

Specifies the final absolute stopping tolerance for the KKT (optimality) error. Smaller values of opttolabs result in a higher degree of accuracy in the solution with respect to optimality.

Default: 1.0e-3

outlev (integer): controls the level of output

controls the level of output.

Default: 2

valuemeaning
0 printing of all output is suppressed
1 only summary information is printed
2 print basic information every 10 iterations
3 print basic information at each iteration
4 print basic information and the function count at each iteration
5 print all of the above, and the values of the solution vector x
6 print all of the above, and the values of the constraints c and the Lagrange multipliers lambda

output_time (boolean): print output on where time is used

Default: 0

par_blasnumthreads (integer): number of threads to use for BLAS operations

This value is used when blasoption=1 (the default). Avoid setting both par_blasnumthreads and par_lsnumthreads to values greater than one.

Range: [1, ∞]

Default: 1

par_lsnumthreads (integer): number of threads to use for PARDISO linear system solver

This value is used when the PARDISO linear system solver is used, i.e. when linsolver=6. Avoid setting both par_blasnumthreads and par_lsnumthreads to values greater than one.

Range: [1, ∞]

Default: 1

pivot (real): initial pivot threshold used in the factorization routine

Specifies the initial pivot threshold used in the factorization routine. The value should be in the range \([0 \dots 0.5]\) with higher values resulting in more pivoting (more stable factorizations). Values less than 0 will be set to 0 and values larger than 0.5 will be set to 0.5. If pivot is non-positive initially no pivoting will be performed. Smaller values may improve the speed of the code but higher values are recommended for more stability (for example, if the problem appears to be very ill-conditioned).

Range: [0, 0.5]

Default: 1e-8

presolve (integer): controls presolve level

Default: 1

valuemeaning
0 no presolve
1 basic presolve

presolve_tol (real): controls presolver tolerance

Controls the presolver tolerance for removing variables and constraints. If you believe the Knitro presolver is incorrectly modifying the model, or you want to limit the changes made by the presolver, use a tighter tolerance or set presolve=0.

Default: 1e-6

reform (boolean): allow objective reformulation

Default: 1

scale (integer): toggles problem scaling

Performs a scaling of the objective and constraint functions based on their values at the initial point. If scaling is performed, all internal computations, including the stopping tests, are based on the scaled values.

Default: 1

valuemeaning
0 No scaling is performed.
1 The objective function and constraints may be scaled.

soc (integer): toggles the second order correction option

Specifies whether or not to try second order corrections (SOC). A second order correction may be beneficial for problems with highly nonlinear constraints.

Default: 1

valuemeaning
0 No second-order correction steps are attempted.
1 Second-order correction steps may be attempted.
2 Second-order correction steps are always attempted if the original step is rejected and there are nonlinear constraints.

threads (integer): default thread count

Synonym: par_numthreads

Controls the number of threads to use. Non-positive values are interpreted as the number of cores to leave free so setting threads to 0 uses all available cores while setting threads to -1 leaves one core free for other tasks.

By default, Knitro decides automatically how to use the threads specified. For example, if the multi-start method is enabled, it can run in parallel threads. If the multi-algorithm algorithm=5 is selected, the different algorithms can be run in parallel threads if threads are allocated. In case only one algorithm is running, multiple threads can be allocated to the MKL BLAS library or to the PARDISO linear solver via the threads option: see the blasoption, par_blasnumthreads, and par_lsnumthreads options for details.

Range: [-∞, ∞]

Default: 1

tuner (boolean): enable Tuner

Default: 0

tuner_maxtimecpu (real): CPU time limit for Tuner run

Default: 1e8

tuner_maxtimereal (real): real time limit for Tuner run

Default: 1e8

tuner_optionsfile (string): specify Tuner options file

tuner_outsub (integer): control additional Tuner subproblem solve output files

Default: 0

valuemeaning
0 no additional output files
1 one summary output file
2 detailed subproblem output files

tuner_terminate (integer): termination condition for Tuner run

Default: 0

valuemeaning
0 terminate after all solves have completed
1 terminate at first local optimum
2 terminate at first feasible solution
3 terminate at first solver completion

xtol (real): tolerance for termination on a small stepsize

Specifies when to terminate the optimization based on stepsize. The optimization will terminate when the relative change in the solution estimate is less than xtol. If using an interior-point algorithm and the barrier parameter is still large, Knitro will first try decreasing the barrier parameter before terminating.

Default: 1e-15

Knitro Termination Test and Optimality

Continuous problems

The first-order conditions for identifying a locally optimal solution of the problem (1) are:

\[ \tag{3} \begin{array}{rll} \displaystyle \nabla_x {\cal L}(x,\lambda) = \nabla f(x) + \sum_{i=1 \dots m} \lambda_i^c \nabla c_i(x) + \sum_{j=1 \dots n} \lambda_j^b & = 0 \\ \displaystyle \lambda_i^c \min [(c_i(x)-c_i^L),(c_i^U-c_i(x))] & = 0, & i=1 \dots m \\ \displaystyle \lambda_j^b \min [(x_j-b_j^L),(b_j^U-x_j)] & = 0, & j=1 \dots n \\ \displaystyle c_i^L \leq c_i(x) & \leq c_i^U, & i=1 \dots m \\ \displaystyle b_j^L \leq x_j & \leq b_j^U, & j=1 \dots n \\ \displaystyle \lambda_i^c & \geq 0, & i \in {\cal I}, \ c_i^L=-\infty,\ c_i^U\ \mbox{finite} \\ \displaystyle \lambda_i^c & \leq 0, & i \in {\cal I}, \ c_i^U=+\infty,\ c_i^L\ \mbox{finite} \\ \displaystyle \lambda_j^b & \geq 0, & j \in {\cal B}, \ b_j^L=-\infty,\ b_j^U\ \mbox{finite} \\ \displaystyle \lambda_j^b & \leq 0, & j \in {\cal B}, \ b_j^U=+\infty,\ b_j^L\ \mbox{finite} \end{array} \]

where \({\cal I}\) and \({\cal B}\) represent the sets of indices corresponding to the general inequality constraints and non-fixed variable bound constraints respectively, \(\lambda_i^c\) is the Lagrange multiplier corresponding to constraint \(c_i(x)\), and \(\lambda_j^b\) is the Lagrange multiplier corresponding to the simple bounds on \(x_j\). There is exactly one Lagrange multiplier for each constraint and variable. The Lagrange multiplier may be restricted to take on a particular sign depending on the corresponding constraint or variable bounds.

In Knitro we define the feasibility error (FeasErr) at a point \(x^k\) to be the maximum violation of the constraints of (1), i.e.,

\[ \mbox{FeasErr} = \max_{i=1 \dots m, \ j=1 \dots n} (0, (c_i^L-c_i(x^k)), (c_i(x^k)-c_i^U), (b_j^L-x_j^k), (x_j^k-b_j^U)), \]

while the optimality error (OptErr) is defined as the maximum violation of the first three conditions of (3)

\[ \mbox{OptErr} = \max_{i=1 \dots m, \ j=1 \dots n} (\|\nabla_x {\cal L}(x^k,\lambda^k) \|_\infty, \lambda_i^c \min [(c_i(x)-c_i^L),(c_i^U-c_i(x))], \lambda_j^b \min [(x_j-b_j^L),(b_j^U-x_j)]). \]

The remaining conditions on the sign of the multipliers are enforced explicitly throughout the optimization. In order to take into account problem scaling in the termination test, the following scaling factors are defined In order to take into account problem scaling in the termination test, the following scaling factors are defined

\begin{align*} \tau_1 & = \max (1, (c_i^L-c_i(x^0)), (c_i(x^0)-c_i^U),(b_j^L-x_j^0), , (x_j^0-b_j^U))), \\ \tau_2 & = \begin{cases} \max (1, \|\nabla f(x^k)\|_\infty), & \text{for constrained problems}, \\ \max (1, \min(|f(x^k)| , \|\nabla f(x^0)\|_\infty)), & \text{for unconstrained problems}, \end{cases} \end{align*}

where \(x^0\) represents the initial point. The special treatment for unconstraints problems is necessary, as for these problems, \(\|\nabla f(x^k)\|_\infty \rightarrow 0\) as a solution is approached, thus \(\max (1, \|\nabla f(x^k)\|_\infty)\) would not be effective.

Knitro stops and declares Locally optimal solution found if the following stopping conditions are satisfied:

\begin{equation} \tag{4} \mbox{FeasErr} \le \max (\tau_1*\mbox{feastol},\mbox{feastolabs}) \end{equation}

\begin{equation}\tag{5} \mbox{OptErr} \le \max (\tau_2*\mbox{opttol}, \mbox{opttolabs}) \end{equation}

where feastol, opttol, feastolabs and opttolabs are user-defined options (see section Usage ).

This stopping test is designed to give the user much flexibility in deciding when the solution returned by Knitro is accurate enough. One can use a purely scaled stopping test (which is the recommended and default option) by setting feastolabs and opttolabs equal to 0.0e0. Likewise, an absolute stopping test can be enforced by setting feastol and opttol equal to 0.0e0.

Unbounded problems

Since by default Knitro uses a relative/scaled stopping test it is possible for the optimality conditions to be satisfied for an unbounded problem. For example, if \(\tau_2 \to \infty\) while the optimality error OptErr stays bounded, condition (5) will eventually be satisfied for some opttol>0. If you suspect that your problem may be unbounded, using an absolute stopping test will allow Knitro to detect this.

Discrete problems

Algorithms for solving versions of (1) where one or more of the variables are restricted to take on only discrete values, proceed by solving a sequence of continuous relaxations, where the discrete variables are relaxed such that they can take on any continuous value. The global solutions \(f(x_R)\) of these relaxed problems provide a lower bound on the optimal objective value for problem (1) (upper bound if maximizing). If a feasible point is found for problem (1) that satisfies the discrete restrictions on the variables, then this provides an upper bound on the optimal objective value of problem (1) (lower bound if maximizing). We will refer to these feasible points as incumbent points and denote the objective value at an incumbent point by \(f(x_I)\). Assuming all the continuous subproblems have been solved to global optimality (if the problem is convex, all local solutions are global solutions), an optimal solution of problem (1) is verified when the lower bound and upper bound are equal.

Knitro declares optimality for a discrete problem when the gap between the best (i.e., largest) lower bound \(f(x_R)\) and the best (i.e., smallest) upper bound \(f(x_I)\) is less than a threshold determined by the user options mip_integral_gap_abs and mip_integral_gap_rel. Specifically, Knitro declares optimality when either

\[ f(x_I) - f(x_R) \leq mip\_integral\_gap\_abs \]

or

\[ f(x_I) - f(x_R) \leq mip\_integral\_gap\_rel \cdot \max (1,|f(x_I)|), \]

where mip_integral_gap_abs and mip_integral_gap_rel are typically small positive numbers. Since these termination conditions assume that the continuous subproblems are solved to global optimality and Knitro only finds local solutions of nonconvex, continuous optimization problems, they are only reliable when solving convex, mixed integer problems. The integrality gap \(f(x_I) - f(x_R)\) should be non-negative although it may become slightly negative from roundoff error, or if the continuous subproblems are not solved to sufficient accuracy. If the integrality gap becomes largely negative, this may be an indication that the model is nonconvex, in which case Knitro may not converge to the optimal solution, and will be unable to verify optimality (even if it claims otherwise).

Note that the default values for mip_integral_gap_abs and mip_integral_gap_rel are taken from the GAMS options optCA and optCR, but an explicit setting of mip_integral_gap_abs or mip_integral_gap_rel will override those.

Knitro Output

If outlev=0 then all printing of output is suppressed. The description below assumes the default output level (outlev=2) except where indicated:

Nondefault Options:

This output lists all user options (see section Usage) which are different from their default values. If nothing is listed in this section then all user options are set to their default values.

Problem Characteristics:

The output begins with a description of the problem characteristics.

Iteration Information - Continuous Problems:

An iteration, in the context of Knitro, is defined as a step which generates a new solution estimate (i.e., a successful step). The columns of the iteration log are as follows:

  • Iter Iteration number.
  • fCount The cumulative number of function evaluations, only included if (outlev>3)
  • Objective Gives the value of the objective function at the current iterate.
  • FeasErr Gives a measure of the feasibility violation at the current iterate.
  • OptErr Gives a measure of the violation of the Karush-Kuhn-Tucker (KKT) (first-order) optimality conditions (not including feasibility) at the current iterate.
  • ||Step|| The 2-norm length of the step (i.e., the distance between the new iterate and the previous iterate).
  • CG its The number of Projected Conjugate Gradient (CG) iterations required to compute the step.

If outlev=2, information is printed every 10 major iterations. If outlev=3 information is printed at each major iteration. If outlev>4 addition information is included in the log.

Iteration Information - Discrete Problems:

By default, the GAMS/Knitro link prints a log line at every 10'th node. This frequency can be changed via the mip_outinterval option. To turn off the node log completely, set the mip_outlevel option to 0. The columns of the iteration log for discrete models are as follows:

  • Node The node number. If an integer feasible point was found at a given node, it is marked with a *
  • Left The current number of active nodes left in the branch and bound tree.
  • Iinf The current number of active nodes left in the branch and bound tree.
  • Objective Gives the value of the objective function at the solution of the relaxed subproblem solved at the current node. If the subproblem was infeasible or failed, this is indicated. Additional symbols may be printed at some nodes if the node was pruned (pr), integer feasible (f), or an integer feasible point was found through rounding (r).
  • Best relaxatn The value of the current best relaxation (lower bound on the solution if minimizing).
  • Best incumbent The value of the current best integer feasible point (upper bound on the solution if minimizing).

Termination Message: At the end of the run a termination message is printed indicating whether or not the optimal solution was found and if not, why the solver terminated. Below is a list of some possible termination messages.

  • EXIT: Locally optimal solution found.

    Knitro found a locally optimal point which satisfies the stopping criterion (see section Knitro Termination Test and Optimality) for more detail on

    how this is defined). If the problem is convex (for example, a linear

    program), then this point corresponds to a globally optimal solution.

  • EXIT: Iteration limit reached.

    The iteration limit was reached before being able to satisfy the required stopping criteria.

  • EXIT: Convergence to an infeasible point. Problem appears to be locally infeasible.

    The algorithm has converged to an infeasible point from which it cannot further decrease the infeasibility measure. This happens when the problem is infeasible, but may also occur on occasion for feasible problems with nonlinear constraints or badly scaled problems. It is recommended to try various initial points. If this occurs for a variety of initial points, it is likely the problem is infeasible.

  • EXIT: Problem appears to be unbounded.

    The objective function appears to be decreasing without bound, while satisfying the constraints.

  • EXIT: Current point cannot be improved.

    No more progress can be made. If the current point is feasible it is likely it may be optimal, however the stopping tests cannot be satisfied perhaps because of degeneracy, ill-conditioning or bad scaling).

  • EXIT: Current point cannot be improved. Point appears to be optimal, but desired accuracy could not be achieved.

    No more progress can be made, but the stopping tests are close to being satisfied (within a factor of 100) and so the current approximate solution is believed to be optimal.

  • EXIT: Time limit reached.

    The time limit was reached before being able to satisfy the required stopping criteria.

  • EXIT: Evaluation error.

    This termination value indicates that an evaluation error occurred (e.g., divide by 0, taking the square root of a negative number), preventing the optimization from continuing.

  • EXIT: Not enough memory available to solve problem.

    This termination value indicates that there was not enough memory available to solve the problem.

Final Statistics:

Following the termination message some final statistics on the run are printed. Both relative and absolute error values are printed.

Solution Vector/Constraints:

If outlev=5, the values of the solution vector are printed after the final statistics. If outlev=6, the final constraint values are also printed before the solution vector and the values of the Lagrange multipliers (or dual variables) are printed next to their corresponding constraint or bound.

Algorithm Options

Automatic

By default, Knitro will automatically try to choose the best optimizer for the given problem based on the problem characteristics.

Interior/Direct

If the Hessian of the Lagrangian is ill-conditioned or the problem does not have a large-dense Hessian, it may be advisable to compute a step by directly factoring the KKT (primal-dual) matrix rather than using an iterative approach to solve this system. Knitro offers the Interior/Direct optimizer which allows the algorithm to take direct steps by setting algorithm=1. This option will try to take a direct step at each iteration and will only fall back on the iterative step if the direct step is suspected to be of poor quality, or if negative curvature is detected.

Using the Interior/Direct optimizer may result in substantial improvements over Interior/CG when the problem is ill-conditioned (as evidenced by Interior/CG taking a large number of Conjugate Gradient iterations). We encourage the user to try both options as it is difficult to predict in advance which one will be more effective on a given problem. In each case, also experiment with the bar_murule option, as it is difficult to predict which update rule will work best.

NOTE: Since the Interior/Direct algorithm in Knitro requires the explicit storage of a Hessian matrix, this version can only be used with Hessian options, hessopt=1, 2, 3 or 6. It may not be used with Hessian options, hessopt=4 or 5, which only provide Hessian-vector products. Both the Interior/Direct and Interior/CG methods can be used with the bar_feasible option.

Interior/CG

Since Knitro was designed with the idea of solving large problems, the Interior/CG optimizer in Knitro offers an iterative Conjugate Gradient approach to compute the step at each iteration. This approach has proven to be efficient in most cases and allows Knitro to handle problems with large, dense Hessians, since it does not require factorization of the Hessian matrix. The Interior/CG algorithm can be chosen by setting algorithm=2. It can use any of the Hessian options as well as the bar_feasible option.

Active Set

Knitro includes an active-set Sequential Linear-Quadratic Programing (SLQP) optimizer. This optimizer is particular advantageous when "warm starting" (i.e., when the user can provide a good initial solution estimate, for example, when solving a sequence of closely related problems). This algorithm is also the preferred algorithm for detecting infeasible problems quickly. The Active Set algorithm can be chosen by setting algorithm=3. It can use any of the Hessian options.

Other Knitro special features

This section describes in more detail some of the more important special features of Knitro and provides some guidance on how use them so that Knitro runs most efficiently for the problem at hand.

Second derivative options

The default version of Knitro assumes that exact second derivatives of the objective function and constraint functions can be computed. If this is possible and the cost of computing the second derivatives is not overly expensive, it is highly recommended to use exact second derivatives. However, Knitro also offers other options which are described in detail below.

(Dense) Quasi-Newton BFGS
The quasi-Newton BFGS option uses gradient information to compute a symmetric, positive-definite approximation to the Hessian matrix. Typically this method requires more iterations to converge than the exact Hessian version. However, since it is only computing gradients rather than Hessians, this approach may be more efficient in many cases. This option stores a dense quasi-Newton Hessian approximation so it is only recommended for small to medium problems ( \(n < 1000\)). The quasi-Newton BFGS option can be chosen by setting options value hessopt=2.

(Dense) Quasi-Newton SR1
As with the BFGS approach, the quasi-Newton SR1 approach builds an approximate Hessian using gradient information. However, unlike the BFGS approximation, the SR1 Hessian approximation is not restricted to be positive-definite. Therefore the quasi-Newton SR1 approximation may be a better approach, compared to the BFGS method, if there is a lot of negative curvature in the problem since it may be able to maintain a better approximation to the true Hessian in this case. The quasi-Newton SR1 approximation maintains a dense Hessian approximation and so is only recommended for small to medium problems ( \(n < 1000\)). The quasi-Newton SR1 option can be chosen by setting options value hessopt=3.

Finite-difference Hessian-vector product option
If the problem is large and gradient evaluations are not the dominate cost, then Knitro can internally compute Hessian-vector products using finite-differences. Each Hessian-vector product in this case requires one additional gradient evaluation. This option can be chosen by setting options value hessopt=4. This option is generally only recommended if the exact gradients are provided.

NOTE: This option may not be used when algorithm=1.

Exact Hessian-vector products
In some cases the problem which the user wishes to solve may have a large, dense Hessian which makes it impractical to store or work with the Hessian directly. The performance of this option should be nearly identical to the exact Hessian option but requires much less storage. This option can be chosen by setting options value hessopt=5.

NOTE: This option may not be used when algorithm=1.

Limited-memory Quasi-Newton BFGS
The limited-memory quasi-Newton BFGS option is similar to the dense quasi-Newton BFGS option described above. However, it is better suited for large-scale problems since, instead of storing a dense Hessian approximation, it only stores a limited number of gradient vectors used to approximate the Hessian. In general it requires more iterations to converge than the dense quasi-Newton BFGS approach but will be much more efficient on large-scale problems. This option can be chosen by setting options value hessopt=6.

Feasible version

Knitro offers the user the option of forcing intermediate iterates to stay feasible with respect to the inequality constraints (it does not enforce feasibility with respect to the equality constraints however). Given an initial point which is sufficiently feasible with respect to all inequality constraints and selecting bar_feasible = 1, forces all the iterates to strictly satisfy the inequality constraints throughout the solution process. For the feasible mode to become active the iterate \(x\) must satisfy

\begin{equation}\tag{21} cl + tol \le c(x) \le cu - tol \end{equation}

for all inequality constraints (i.e., for \(cl \ne cu\)). The tolerance \(tol>0\) by which an iterate must be strictly feasible for entering the feasible mode is determined by the parameter bar_feasmodetol which is 1.0e-4 by default. If the initial point does not satisfy (21) then the default infeasible version of Knitro will run until it obtains a point which is sufficiently feasible with respect to all the inequality constraints. At this point it will switch to the feasible version of Knitro and all subsequent iterates will be forced to satisfy the inequality constraints.

For a detailed description of the feasible version of Knitro see [52] .

NOTE: This option may only be used when algorithm=2.

Honor Bounds

By default Knitro does not enforce that the simple bounds on the variables (1c) are satisfied throughout the optimization process. Rather, satisfaction of these bounds is only enforced at the solution. In some applications, however, the user may want to enforce that the initial point and all intermediate iterates satisfy the bounds \(bl \le x \leq bu\). This can be enforced by setting honorbnds=1.

Crossover

Interior-point (or barrier) methods are a powerful tool for solving large-scale optimization problems. However, one drawback of these methods is that they do not always provide a clear picture of which constraints are active at the solution. In general they return a less exact solution and less exact sensitivity information. For this reason, Knitro offers a crossover feature in which the interior-point method switches to the Active Set method at the interior-point solution estimate, in order to "clean up" the solution and provide more exact sensitivity and active set information. The crossover procedure is controlled by the bar_maxcrossit option. If this option is greater than 0, then Knitro will attempt to perform bar_maxcrossit Active Set crossover iterations after the interior-point method has finished, to see if it can provide a more exact solution. This can be viewed as a form of post-processing. If bar_maxcrossit is not positive, then no crossover iterations are attempted.

The crossover procedure will not always succeed in obtaining a more exact solution compared with the interior-point solution. If crossover is unable to improve the solution within bar_maxcrossit crossover iterations, then it will restore the interior-point solution estimate and terminate. By default, Knitro will then print a message indicating that it was unable to improve the solution within the iterations allowed. In this case, you may want to increase the value of bar_maxcrossit and try again. If Knitro determines that the crossover procedure will not succeed, no matter how many iterations are tried, then a message of the form Crossover mode unable to improve solution. will be printed.

The extra cost of performing crossover is problem dependent. In most small or medium scale problems, the crossover cost is a small fraction of the total solve cost. In these cases it may be worth using the crossover procedure to obtain a more exact solution. On some large scale or difficult degenerate problems, however, the cost of performing crossover may be significant. It is recommended to experiment with this option to see whether improvement in the exactness of the solution is worth the additional cost.

Tuner

The Knitro-Tuner can help you identify some non-default options settings that may improve performance on a particular model or set of models. The Knitro tuner is enabled with the tuner option and controlled via the tuner_ family of options. If you are unsure about what Knitro options should be tuned to try to improve performance, you can run the default Knitro-Tuner by simply setting the option tuner=1 when solving with Knitro. This will cause Knitro to run your model with a variety of automatically determined option settings, and report some statistics at the end. Any Knitro options that have been set in the usual way will remain fixed throughout the tuning procedure.

If you have some ideas about which Knitro options you want to tune, you can tell Knitro which options you want it to tune, as well as specify the values for particular options that you want Knitro to explore. This can be done by specifying a Tuner options file. A Tuner options file is a simple text file that is similar to a standard Knitro options file, with some important differences:

  • You can define multiple values (separated by spaces) for each option. This tells Knitro the values you want it to explore.
  • You can specify an option name without any values. This will tell Knitro to explore all possible option values for that option. This only works for options that have a finite set of possible option value settings.
  • A Tuner options file is loaded via the tuner_optionsfile option.

All possible combinations of options/values specified in a Tuner options file will be explored by Knitro, while any Knitro options that have been set in the usual way will remain fixed throughout the tuning procedure.

Solving Systems of Nonlinear Equations

Knitro is quite effective at solving systems of nonlinear equations. To solve a square system of nonlinear equations using Knitro one should specify the nonlinear equations as equality constraints (i.e., constraints with \(cl = cu\)), and specify the objective function (1a) as zero (i.e., \(f(x)=0\)).

Solving Least Squares Problems

There are two ways of using Knitro for solving problems in which the objective function is a sum of squares of the form

\[ f(x) = \textstyle\frac{1}{2} \sum_{j=1}^q r_j(x)^2. \]

If the value of the objective function at the solution is not close to zero (the large residual case), the least squares structure of \(f\) can be ignored and the problem can be solved as any other optimization problem. Any of the Knitro options can be used.

On the other hand, if the optimal objective function value is expected to be small (small residual case) then Knitro can implement the Gauss-Newton or Levenberg-Marquardt methods which only require first derivatives of the residual functions, \(r_j(x)\), and yet converge rapidly. To do so, the user need only define the Hessian of \(f\) to be

\[ \nabla^2 f(x) = J(x)^TJ(x), \]

where

\[ J(x) = \left[ \frac{\partial r_j}{\partial x_i} \right]_{\begin{array}{c} j=1,2,\dots,q \\ i=1,2,\dots,n \end{array}}. \]

The actual Hessian is given by

\[ \nabla^2 f(x) = J(x)^T J(x) + \sum_{j=1}^q r_j(x) \nabla^2 r_j(x); \]

the Gauss-Newton and Levenberg-Marquardt approaches consist of ignoring the last term in the Hessian.

Knitro will behave like a Gauss-Newton method by setting algorithm=1, and will be very similar to the classical Levenberg-Marquardt method when algorithm=2. For a discussion of these methods see, for example, [186] .