Choice of Advanced Solution Methods
The KNITRO Solver offers a choice
of three solution methods: An Interior Point CG method
where the linear system for the search direction is solved using a
projected conjugate gradient method; an Interior Point Direct
method where the linear system is solved using direct factorization;
and an Active Set (SLQP) method, which creates and solves
linear programming (LP) and equality constrained quadratic
programming (EQP) subproblems on its major iterations. A
fourth choice allows the KNITRO Solver to select the solution method
automatically based on the characteristics of the problem.
Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity
in large models, where subsets of the constraints typically
depend on only a small subset of the variables. For example, the Jacobian
matrix (the matrix of partial derivatives of the objective and
constraints with respect to the variables) for a problem with 2,000
variables and 2,000 constraints would take about 32 megabytes for
matrix storage using dense storage methods, but if this problem has
the sparsity typical of larger models, it would take as little as 1
to 1.5 megabytes using the sparse storage methods in the KNITRO Solver.
Improved Methods for Numerical Stability
Large nonlinear models require hundreds of
thousands to millions of floating-point arithmetic calculations.
Because of the finite precision inherent in computer arithmetic, small
numerical errors occur in these calculations. Nonlinear models
are particularly susceptible to the cumulative effect of these
errors, which can lead to a numerically unstable or ill-conditioned
matrix representation of the problem.
The KNITRO Solver uses several advanced
methods to deal with numerical stability, including methods for
estimating the conditioning of the Jacobian and Hessian
matrix, special methods for dealing with degeneracy, and
advanced methods for selecting changes in the basis (which
represents the currently binding constraints in the problem). Thanks
to these methods, the KNITRO Solver can find very good or
optimal solutions to problems that could not be solved at all with
more primitive nonlinear optimizers.
Options for Derivatives and Mixed-Integer Nonlinear Problems
