Advanced Methods
The KNITRO Solver can use the Premium Solver Platform's "multistart" or "clustering" methods for global optimization. It can be automatically run many times from judiciously chosen starting points, and the best solution found will be returned as the optimal solution. For some smooth nonlinear problems, multistart methods will converge in probability to the globally optimal solution. For other problems, they often yield very good solutions in an acceptable amount of time -- and of course, they are far easier to use than a manual exploratory process. And you don't have to change your model at all to take advantage of these new global optimization capabilities! |
|
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
An Interior Point method (also known as a Barrier method) evaluates the Hessian of the Lagrangian of the problem functions at each major iteration. This requires the Hessian matrix of second partial derivatives of each problem function at each iteration. The KNITRO Solver can obtain these derivatives (i) directly from the Premium Solver Platform via second-order automatic differentiation, (ii) by constructing a quasi-Newton (BFGS) approximation based on function gradients obtained from the Platform via first-order automatic differentiation, or even (iii) from estimated first and second derivatives obtained via finite differencing. |
The KNITRO Solver uses the Premium Platform's Branch and Bound method to handle integer variables and "alldifferent" constraints. If your problem includes integer constraints, you can obtain a quick solution of the relaxation (temporarily ignoring the integer constraints) without having to delete these constraints and then re-enter them later.
You can control the number of Branch and Bound subproblems and the number of integer feasible solutions found before the Solver stops. And you can speed up the solution of problems with integer constraints by supplying an integer cutoff value -- often known from a previous run.