Algorithms

Knitro implements four state-of-the-art interior-point and active-set 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	Interior-Point/Direct	Interior-Point/Conjugate-Gradient	Sequential Linear Quadratic Programming	Sequential Quadratic Programming
Large scale	++ (sparse)	++ (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
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 four 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.

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