3 Algorithms
KNITRO provides 3 state-of-the-art algorithms/solvers for solving problems. Each algorithm addresses the full range of nonlinear optimization problems, and each is constructed for maximal large-scale efficiency.
| Interior-point Direct algorithm applies barrier techniques and directly factorizes the KKT matrix of the nonlinear system. It performs best on ill-conditioned problems. | |
| Interior-point CG algorithm applies barrier techniques using the conjugate gradient method to solve KKT subproblems. It provides an alternative to the Interior-point Direct algorithm when the KKT factorization is impractical or inefficent to form. | |
| Active Set algorithm combines classical active set principles with a novel linear programming subproblem to rapidly discover the set of binding constraints. It's behavior is significantly different from Interior-point algorithms, and it converges precisely to the active set to provide highly accurate sensitivity information. |
Every nonlinear optimization problem is unique, and it can be quite difficult to predict performance of any algorithm on a given problem. Choosing among KNITRO's three algorithms greatly increases the chances of solving your problem efficiently.
|
The figure above compares relative performance of the three KNITRO algorithms on a set of 920 academic and industrial test problems. An algorithm scores a "win" if it outperforms the others on problems that more than one algorithm solves. Each graph shows the winning percentages of the three algorithms based on two different criteria. The graph on the left ("Function Evaluations") compares how often KNITRO requests the application to evaluate functions at a trial point. If your problem is computationally expensive to evaluate (e.g., PDE solvers), then this is the most important criteria. The graph on the right ("CPU Time") compares computation time of the three algorithms. It is clear that no single algorithm dominates, and users are best served by having all three available.
Three algorithms makes KNITRO more robust on difficult problems. For example, on the test set of 920 problems, a solution was found by at least one KNITRO algorithm within a specified time limit in 95.2% cases. By themselves, individual algorithms were successful between 88% and 93% of the time.
Having three algorithms also means that KNITRO Interior-point solutions can "crossover" to the Active Set algorithm for final computation of highly accurate solutions and sensitivities. Some Interior-point products attempt a crossover solution based on heuristics, but only a rigorous Active Set method can determine the correct active set with true confidence.
We recommend trying all three algorithms on your problem to find out what works best. KNITRO attempts to automatically determine the best algorithm based on problem specifications, but it is difficult to predict behavior. Please see the KNITRO User's Manual for more information.
