# 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 `par_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.