NonOpt

NonOpt is an open-source C++ software package for solving unconstrained optimization problems of the form \[ \min_{x \in \mathbb{R}^n} f(x) \] where \(f : \mathbb{R}^n \to \mathbb{R}\) is locally Lipschitz. The objective function \(f\) may be nonconvex and/or nonsmooth.

NonOpt can be obtained on GitHub here (link). A direct link to its user manual is here (link).

NonOpt contains a suite of algorithms for solving locally Lipschitz (potentially nonconvex and/or nonsmooth) minimization problems. It is not guaranteed to find a global minimizer of the objective function. Rather, it employs local-search techniques based on (generalized) derivative computations in order to improve as best as it can upon an initial solution estimate.

To use NonOpt, a user only needs to provide a method for evaluating an objective function and a (generalized) gradient for it at any given solution estimate. (Various examples are provided that a user can follow to implement their own problem.) NonOpt's default parameters have been chosen as those that often allow the software to find a good solution estimate relatively quickly. A user can adjust these parameters through options in the software in order to push the solver to try to find solutions of higher accuracy. For further information about how to adjust input parameters, please see the User's Manual here (link).

The algorithms implemented in NonOpt are based on three main methodologies, namely, the quasi-Newton, proximal-bundle, and gradient-sampling methodologies. For further information about each of these methodologies, please see the (forthcoming) book ``Practical Nonconvex Nonsmooth Optimization'' here (link). Here we provide only brief descriptions.

Quasi-Newton techniques were first designed for the setting of minimizing smooth functions. They involve using first-order derivatives in order to approximate second-order derivatives through iterative updates. In particular, given first-order derivatives at solution estimates indexed by \(k\) and \(k+1\), call these estimates \(x_k\) and \(x_{k+1}\), the foundational idea of any quasi-Newton method is to approximate the second-order derivative (i.e., Hessian matrix) of the objective function at \(x_{k+1}\), call it \(H_{k+1}\), in such a way that the resulting second-order approximation of the objective at \(x_{k+1}\) has a derivative that matches the derivative of the original objective at \(x_k\). This is known as the secant equation; see the figure below, where by satisfying the secant equation the resulting second-order approximation of the objective at \(x_{k+1}\) (purple curve) has a derivative that matches the derivative of the objective function (blue curve) at \(x_k\). Despite the fact that this foundational idea was first developed for the setting of smooth optimization, quasi-Newton techniques turn out to be extremely powerful when solving nonsmooth minimization problems as well. All algorithms in NonOpt use quasi-Newton techniques.

The default algorithm that NonOpt employs is based on the proximal-bundle methodology (equipped with a quasi-Newton technique) for computing search directions. Proximal-bundle methods build on the classic cutting-plane methodology for approximating a function through point-wise maxima over sets of affine approximations. For convex functions, these cutting planes underestimate the objective function at every point in the domain. Combined with the proximal-point methodology, the resulting piecewise-quadratic approximations no longer underestimate the objective function, but they approximate it sufficiently well for the purpose of computing search directions. See the figure below, where on the left the quadratic approximation of the objective, namely, \(q_{\cal{B}_{k,j}}\), is constructed using only one cutting plane, whereas on the right the piecewise quadratic approximation is constructed with two cutting planes. Convergence guarantees for the algorithm are based on tying the resulting approximations to a function known as the Moreau envelope, which is shown as \(\tilde{f}\) in the illustrations below.

The other main algorithm available in NonOpt is based on the gradient-sampling methodology. The fundamental idea of the gradient-sampling methodology is to approximate, at each solution estimate, a steepest-descent direction through the random sampling of points and computation of gradients of the objective function at those points. The computed search direction is then the minimum-norm element of the convex hull of these available gradients from nearby points. If the points that are sampled surround a minimizer, such as on the left in the figure below, then the search direction may be zero, in which case the algorithm adaptively decreases the radius over which the points are sampled. This can lead to a situation such as that illustrated on the right below, where a nonzero search direction can equivalently be described as being computed by minimizing a piecewise-quadratic approximation of the objective function at the solution estimate \(x_{k+1}\).

These are only very brief descriptions of the algorithmic methodologies underlying NonOpt. We encourage any user that is interested to check out the (forthcoming) book ``Practical Nonconvex Nonsmooth Optimization'' here (link) for much more in-depth discussions about these methodologies and their use for locally Lipschitz minimization.