Algorithms
Knitro implements four stateoftheart interiorpoint and activeset methods for solving continuous, nonlinear optimization problems. Each algorithm possesses strong convergence properties and is coded for maximum efficiency and robustness. However, the algorithms have fundamental differences that lead to different behavior on nonlinear optimization problems. Together, the four methods provide a suite of different ways to attack difficult problems.
We encourage the user to try all algorithmic options to determine which one is more suitable for the application at hand.
Overview
The table below presents a brief overview of the main features included in the four NLP algorithms.
Features 
InteriorPoint/Direct 
InteriorPoint/ConjugateGradient 
Sequential Linear Quadratic Programming 
Sequential Quadratic Programming 

Large scale 
++ (sparse) 
++ (sparse or dense) 
+ 

Expensive evaluations 
+ 
++ 

Warmstart 
+ 
+ 
++ 
++ 
Least square problems 
++ 
++ 
+ 
+ 
Globalization technique 
Linesearch/Trustregion 
Trustregion 
Trustregion 
Linesearch/Trustregion 
Linear solver 
Lapack QR, MA27/57/86/97, MKL PARDISO 
Lapack QR, MA27/57/86/97, MKL PARDISO 
Lapack QR, MA27/57/86/97, MKL PARDISO 
Lapack QR, MA27/57/86/97, MKL PARDISO 
LP solver 
 
 
Clp (incl.) or Xpress/Cplex (not incl.) 
Clp (incl.) or Xpress/Cplex (not incl.) 
QP solver 
 
 
 
IP/Direct or IP/CG or SLQP 
Large scale: ability to solve large scale problems
Expensive evaluations: performance on problems with expensive function evalutations
Warmstart: ability to warmstart
Least square problems: performance on least square problems
Globalization technique: method used to improve the likelihood of convergence from any initial point. This is not related to finding a global optima of the optimized function.
Linear solver: solvers available for the resolution of internal linear systems
LP solver: solvers available for the resolution of linear subproblems
QP solver: solvers available for the resolution of quadratic subproblems
Algorithms description
This section only describes the four algorithms implemented in Knitro in very broad terms. For details, please see the Bibliography.
Interior/Direct algorithm
Interiorpoint methods (also known as barrier methods) replace the nonlinear programming problem by a series of barrier subproblems controlled by a barrier parameter. Interiorpoint methods perform one or more minimization steps on each barrier subproblem, then decrease the barrier parameter and repeat the process until the original problem has been solved to the desired accuracy. The Interior/Direct method computes new iterates by solving the primaldual KKT matrix using direct linear algebra. The method may temporarily switch to the Interior/CG algorithm, described below, if it encounters difficulties.
Interior/CG algorithm
This method is similar to the Interior/Direct algorithm. It differs mainly in the fact that the primaldual KKT system is solved using a projected conjugate gradient iteration. This approach differs from most interiorpoint methods proposed in the literature. A projection matrix is factorized and the conjugate gradient method is applied to approximately minimize a quadratic model of the barrier problem. The use of conjugate gradients on largescale problems allows Knitro to utilize exact second derivatives without explicitly forming or storing the Hessian matrix. An incomplete Cholesky preconditioner can be computed and applied during the conjugate gradient iterations for problems with equality and inequality constraints. This generally results in improved performances in terms of number of conjugate gradient iterations and CPU time.
Active Set algorithm
Active set methods solve a sequence of subproblems based on a quadratic model of the original problem. In contrast with interiorpoint methods, the algorithm seeks active inequalities and follows a more exterior path to the solution. Knitro implements a sequential linearquadratic programming (SLQP) algorithm, similar in nature to a sequential quadratic programming method but using linear programming subproblems to estimate the active set. This method may be preferable to interiorpoint algorithms when a good initial point can be provided; for example, when solving a sequence of related problems. Knitro can also “crossover” from an interiorpoint method and apply Active Set to provide highly accurate active set and sensitivity information.
Sequential Quadratic Programming (SQP) algorithm
The SQP method in Knitro is an activeset method that solves a sequence of quadratic programming (QP) subproblems to solve the problem. This method is primarily designed for small to medium scale problems with expensive function evaluations – for example, problems where the function evaluations involve performing expensive blackbox simulations and/or derivatives are computed via finitedifferencing. The SQP iteration is expensive since it involves solving a QP subproblem. However, it often converges in the fewest number of function/gradient evaluations, which is why this method is often preferable for situations where the evaluations are the dominant cost of solving the model.
Note
For mixed integer programs (MIPs), Knitro provides two variants of the branch and bound algorithm that rely on the previous four algorithms to solve the continuous (relaxed) subproblems. The first is a standard branch and bound implementation, while the second is specialized for convex, mixed integer nonlinear problems. A third method (MISQP) extends the SQP method for continuous, nonlinear optimization to the case where there are integer variables.
Algorithm choice
Automatic
By default, Knitro automatically tries to choose the best algorithm for a given problem based on problem characteristics.
However, we strongly encourage you to experiment with all the algorithms as it is difficult to predict which one will work best on any particular problem.
Interior/Direct
This algorithm often works best, and will automatically switch to Interior/CG if the direct step is suspected to be of poor quality, or if negative curvature is detected. Interior/Direct is recommended if the Hessian of the Lagrangian is illconditioned. The Interior/CG method in this case will often take an excessive number of conjugate gradient iterations. It may also work best when there are dependent or degenerate constraints. Choose this algorithm by setting user option
algorithm
= 1.We encourage you to experiment with different values of the bar_murule option when using the Interior/Direct or Interior/CG algorithm. It is difficult to predict which update rule will work best on a problem.
Note
Since the Interior/Direct algorithm in Knitro requires the explicit storage of a Hessian matrix, this algorithm only works with Hessian options (
hessopt
) 1, 2, 3, or 6. It may not be used with Hessian options 4 or 5 (where only Hessianvector products are performed) since they do not supply a full Hessian matrix.Interior/CG
This algorithm is wellsuited to large problems because it avoids forming and factorizing the Hessian matrix. Interior/CG is recommended if the Hessian is large and/or dense. It works with all Hessian options. Choose this algorithm by setting user option
algorithm
= 2.We encourage you to experiment with different values of the
bar_murule
option when using the Interior/Direct or Interior/CG algorithm. It is difficult to predict which update rule will work best on a problem.Active Set:
This algorithm is fundamentally different from interiorpoint methods. The method is efficient and robust for small and mediumscale problems, but is typically less efficient than the Interior/Direct and Interior/CG algorithms on largescale problems (many thousands of variables and constraints). Active Set is recommended 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 best at rapid detection of infeasible problems. Choose this algorithm by setting user option
algorithm
= 3.SQP
This algorithm is best suited to small problems where the function and derivative evaluations are the dominant cost. Like the activeset method above, this method can converge quickly when a good initial solution estimate is provided.
Choose this algorithm by setting user option
algorithm
= 4.Note
Since the SQP algorithm in Knitro currently requires the explicit storage of a Hessian matrix, this algorithm only works with Hessian options (
hessopt
) 1, 2, 3, or 6. It may not be used with Hessian options 4 or 5 (where only Hessianvector products are performed) since they do not supply a full Hessian matrix.Multi Algorithm:
This option runs all four algorithms above either sequentially or in parallel. It can be selected by setting user option
algorithm
= 5 and is explained in more detail below.
Multiple algorithms
Setting user option algorithm
= 5 (KN_ALG_MULTI
), allows you to
easily run all four
Knitro algorithms. The algorithms will run either sequentially or in parallel
depending on the setting of par_numthreads
(see Parallelism).
The user option ma_terminate
controls how to terminate the multialgorithm (“ma”)
procedure. If ma_terminate
= 0, the procedure will run until all four algorithms
have completed (if multiple optimal solution are found,
Knitro will return the one with the best objective value). If ma_terminate
= 1,
the procedure will terminate as soon
as the first local optimal solution is found. If ma_terminate
= 2, the procedure
will stop at the first feasible solution estimate. If ma_terminate
= 3, the procedure
will stop as soon as any of the algorithms terminate for any reason.
If you are not sure which algorithm works
best for your application, a recommended strategy is to set algorithm
= 5
with ma_terminate
= 1 (this is particularly advantageous if it can be done
in parallel).
Note
Running all the Knitro algorithms in parallel with
ma_terminate
> 0 (i.e. terminating at the first one to produce a solution or solution estimate), may result in nondeterministic behavior since the algorithm that finishes first may possibly change from one run to another.
The user options ma_maxtime_cpu
and ma_maxtime_real
place overall
time limits on the total multialgorithm procedure while the options
maxtime_cpu
and maxtime_real
impose time limits for each algorithm
solve.
The output from each algorithm can be written to a file
named knitro_ma_x.log
where “x” is the algorithm number by setting
the option ma_outsub
=1.
Crossover
Interiorpoint (or barrier) methods are a powerful tool for solving largescale 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 interiorpoint method switches to the Active Set method at the interiorpoint 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
user option. If this parameter is
greater than 0, then Knitro will attempt to perform
bar_maxcrossit
Active Set crossover iterations after
the interiorpoint method has finished, to see if it can provide a
more exact solution. This can be viewed as a form of postprocessing.
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 interiorpoint solution. If
crossover is unable to improve the solution within
bar_maxcrossit
crossover iterations, then it will
restore the interiorpoint solution estimate and terminate. If
outlev
is greater than one, Knitro will print a message
indicating that it was unable to improve the solution. For example,
if bar_maxcrossit
= 3 and the crossover procedure did
not succeed, the message will read:
Crossover mode unable to improve solution within 3 iterations.
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.