What's the best nonlinear programming solver for your problem?

1 Local vs global solvers

One of the main distinctions between NLP solvers is whether they are local or global. Local solvers aim to find a solution that satisfies the first-order optimality conditions, which means that the gradient of the objective function and the constraints are zero or orthogonal at the solution point. However, this does not guarantee that the solution is the best possible one, as there may be other points that have a lower objective value. Global solvers, on the other hand, try to find the global optimum, which is the lowest objective value among all feasible points. However, this is usually more computationally expensive and challenging, especially for non-convex problems.

2 Gradient-based vs derivative-free solvers

Another important difference between NLP solvers is whether they use gradient information or not. Gradient-based solvers require the evaluation of the first or second derivatives of the objective function and the constraints, either analytically or numerically. This can help them converge faster and more accurately, but it also requires more memory and may encounter difficulties if the functions are not smooth or continuous. Derivative-free solvers do not need the gradient information, but only the function values. This can make them more robust and flexible, but also slower and less precise.

3 Trust-region vs line-search methods

A common feature of many gradient-based solvers is that they use either trust-region or line-search methods to determine the step size and direction for each iteration. Trust-region methods define a region around the current point where the model of the objective function is reliable, and then solve a subproblem within that region to find the next point. Line-search methods find the next point by moving along a direction that reduces the objective function, and then adjust the step size by using some criteria, such as the Armijo rule or the Wolfe conditions. Both methods have advantages and disadvantages, depending on the problem characteristics and the solver parameters.

4 Interior-point vs active-set methods

Another common feature of many NLP solvers is that they use either interior-point or active-set methods to handle the constraints. Interior-point methods transform the constrained problem into an unconstrained one by adding penalty or barrier terms to the objective function, and then solve it by using a sequence of points that approach the boundary of the feasible region. Active-set methods identify and update a set of active constraints, which are the ones that are binding at the optimal solution, and then solve a reduced problem with only those constraints. Both methods have trade-offs, depending on the number and type of constraints and the initial point.

5 Specialized solvers

In addition to the general types of NLP solvers, there are also some specialized solvers that are designed for specific classes of problems, such as quadratic programming (QP), mixed-integer nonlinear programming (MINLP), or bilevel programming (BLP). These solvers exploit the structure and properties of these problems to devise more efficient and effective algorithms. For example, QP solvers can use the KKT conditions or the dual problem to find the optimal solution, MINLP solvers can use branch-and-bound or branch-and-cut methods to handle the integer variables, and BLP solvers can use nested optimization or reformulation techniques to deal with the hierarchical structure.

6 How to choose and use a solver

Finding the best NLP solver for your problem is not an easy task, as it depends on many factors, such as the problem formulation, solver availability, settings, and performance. To make a better decision, begin with a simple and clear problem formulation and make sure it meets the solver's assumptions and requirements. Compare different solvers by using benchmarks, test problems, or your own problem instances and assess them based on solution quality, speed of convergence, robustness to noise or errors, and ease of use. Adjust parameters such as tolerance, iteration limit, step size or regularization to improve solver performance and avoid potential issues. Finally, use multiple solvers or options to compare results and verify the consistency and reliability of the solution while identifying any local or global optima.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?