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 [29] and for the global convergence theory see [30] . The method implemented in Interior/Direct is described in [197] . The Active algorithm is described in [32] and the global convergence theory for this algorithm is in [33] . An important component of Knitro is the HSL routine MA27 [91] 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 https://www.artelys.com/app/docs/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_opt_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_opt_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:

General options

Derivative options

Termination options

Presolve options

Barrier options

Active-set options