Algorithms

Knitro offers a variety of algorithms for solving both linear (LP) and nonlinear (NLP) continuous optimization problems. The LP algorithm is selected via the lp_algorithm user option, while the nonlinear algorithm is selected using the nlp_algorithm option. The nonlinear algorithms apply to general nonlinear problems as well as quadratic optimization problems (e.g. QPs, QCQPs). This section mainly focuses on describing the properties for the nonlinear algorithms, although a summary of the LP algorithm offerings in Knitro is provided at the end of this section.

Knitro implements several state-of-the-art methods for solving continuous, nonlinear optimization problems, including interior-point/barrier methods, active-set methods, and augmented Lagrangian methods. 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 collection of methods provides 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 NLP algorithms.

Features	Interior-Point/Direct	Interior-Point/Conjugate-Gradient	Active-Set (SLQP)	Sequential Quadratic Programming	Augmented Lagrangian
Large scale	++ (sparse)	++ (sparse or dense)	+		++ (sparse or dense)
Expensive evaluations			+	++
Warm-start	+	+	++	++
Least square problems	++	++	+	+
Globalization technique	Line-search/Trust-region	Trust-region	Trust-region	Line-search/Trust-region
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	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
Warm-start: ability to warm-start
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 algorithms implemented in Knitro in very broad terms. For details, please see the Bibliography.

Interior/Direct algorithm

Interior-point methods (also known as barrier methods) replace the nonlinear programming problem by a series of barrier subproblems controlled by a barrier parameter. Interior-point 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 primal-dual 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 primal-dual KKT system is solved using a projected conjugate gradient iteration. This approach differs from most interior-point 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 large-scale 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 interior-point methods, the algorithm seeks active inequalities and follows a more exterior path to the solution. Knitro implements a sequential linear-quadratic 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 interior-point algorithms when a good initial point can be provided; for example, when solving a sequence of related problems. Knitro can also “crossover” from an interior-point 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 active-set 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 black-box simulations and/or derivatives are computed via finite-differencing. 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.
Augmented Lagrangian algorithm

Augmented Lagrangian (AL) methods offer an alternative to interior-point methods for solving very-large scale optimization problems. These methods minimize an objective that includes the Lagrangian function plus a squared, 2-norm penalty term of the constraint violation. Several of these subproblems may need to be solved for increasing values of the penalty parameter to achieve feasibility. There are variations of AL methods that differ in how the subproblems are formed (e.g. bound-constrained versus nonlinearly constrained), and the level of derivatives used (only first order versus second order). The variant introduced in Knitro 15.0 is a nonlinearly constrained Lagrangian (NCL) version that can make use of second derivatives if available. The primary advantage of this approach for large-scale problems (compared to interior-point methods) is that it is designed to better handle difficult problems with degenerate constraints where the Linear Independence Constraint Qualification (LICQ) is not satisfied.

Note

For mixed integer programs (MIPs), Knitro provides a branch-and-bound algorithm that relies on the algorithms described above to solve the continuous (relaxed) subproblems. Knitro also offers a mixed-integer SQP algorithm (MISQP), which extends the SQP method for continuous, nonlinear optimization to the case where there are integer variables. See mip_method for more details.

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 ill-conditioned. 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 nlp_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 Hessian-vector products are performed) since they do not supply a full Hessian matrix.
Interior/CG

This algorithm is well-suited 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 nlp_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 interior-point methods. The method is efficient and robust for small and medium-scale problems, but is typically less efficient than the Interior/Direct and Interior/CG algorithms on large-scale 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 nlp_algorithm = 3.
SQP

This algorithm is best suited to small problems where the function and derivative evaluations are the dominant cost. Like the active-set method above, this method can converge quickly when a good initial solution estimate is provided.

Choose this algorithm by setting user option nlp_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 Hessian-vector products are performed) since they do not supply a full Hessian matrix.
Augmented Lagrangian

This algorithm is best suited to small or large problems with difficult (degenerate) constraints. Specifically, it is advantageous on models where the Linear Independence Constraint Qualification (LICQ) does not hold. These are problems where the active constraint gradients are linearly dependent (i.e. the active constraint Jacobian matrix is rank-deficient) at the solution.

Choose this algorithm by setting user option nlp_algorithm = 6.
Multi Algorithm:

This option runs the first four algorithms above either sequentially or in parallel. It can be selected by setting user option nlp_algorithm = 5 and is explained in more detail below.

Multiple algorithms

Setting user option nlp_algorithm = 5 (KN_NLP_ALG_MULTI), allows you to easily run the first four Knitro algorithms. The algorithms will run either sequentially or in parallel depending on the setting of numthreads (see Parallelism).

The user option ma_terminate controls how to terminate the multi-algorithm (“ma”) procedure. If ma_terminate = 0, the procedure will run until all 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 nlp_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 non-deterministic 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 multi-algorithm 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

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 user option. If this parameter 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. 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.

Linear (LP) algorithms

Knitro offers a variety of standard algorithms specific to linear optimization problems (LPs), and these can be chosen using the lp_algorithm option. By default (lp_algorithm =-1), Knitro will automatically choose the algorithm to use for LPs (currently the interior-point/barrier algorithm is always chosen by default for LPs). Primal simplex can be chosen with lp_algorithm =1, dual simplex with lp_algorithm =2, and barrier with lp_algorithm =3.

The primal-dual LP algorithm (PDLP) can be selected by setting lp_algorithm =4. This algorithm is a pure first order method that may be useful on very large-scale problems when the other LP algorithm options struggle. In general, this algorithm takes many iterations to converge and may struggle to converge to high accuracy. However, the iterations are very cheap/fast as they do not require any matrix factorizations, and the algorithm has low memory requirements.

You can also force Knitro to use the more general NLP algorithm specified in nlp_algorithm for LPs by setting lp_algorithm =0.