by Nitish Shirish Keskar and Andreas Waechter
Paper link: arXiv preprint
The proposed method (NQN) is a limited-memory quasi-Newton method for bound-constrained nonsmooth optimization. It is an active-set method in that it operates iteratively in a two-phase approach of predicting the optimal active-set and computing steps in the identified subspace. The code is written in pure-Python and aims to mimic the calling syntax of scipy.optimize.fmin_l_bfgs_b. In order to replace an existing call to fmin_l_bfgs_b with our code, simply import NQN.py and replace scipy.optimize.fmin_l_bfgs_b to NQN.fmin_l_bfgs_b. In most cases, no changes to the calling arguments should be necessary. We include additional usage details at the end of this README.
Please contact us if you have any questions, suggestions, requests or bug-reports.
If you use this code or our results in your research, please cite:
@article{Keskar2016,
author = {Nitish Shirish Keskar and Andreas Waechter},
title = {A Limited-Memory Quasi-Newton Algorithm for Bound-Constrained Nonsmooth Optimization},
journal = {arXiv:1612.07350},
year = {2016}
}
- Our code is written in pure-Python. Circumstantially, this can be slower than SciPy's L-BFGS-B implementation which is written in Fortran.
- If you set the value of the gradient-sampling memory (M) to be greater than 1, you need the CVXOPT package for solving the QP. This can be easily installed via
pip. However, we do not recommend setting M to be greater than 1 unless you need extremely high-precision solutions. - Please write to us if you need the Python code for the test problems, other solvers/wrappers or scripts for generating figures.
In order to use our code, simply import the NQN.py file and call NQN.fmin_l_bfgs_b with the calling options similar to scipy.optimize.fmin_l_bfgs_b. Concretely, the function signature is
fmin_l_bfgs_b(funObj, x0, gradObj, bounds=None, m=20, M=1, pgtol=1e-5, iprint=-1, maxfun=15000, maxiter=15000, callback=None, factr=0.)
where:
funObj => Function to minimize
x0 => Initial/starting point
gradObj => Gradient of objective function. Unlike L-BFGS-B, for NQN, this *must* be provided
bounds => A tuple of bound constraints. Use (-numpy.inf, numpy.inf) if a a variable in unconstrained
m => L-BFGS memory
M => Gradient sampling memory
pgtol => Scaled 2-norm tolerance for convergence
iprint => Controls output; iprint>0 prints to STDOUT
maxfun => Max. number of function evaluations
maxiter => Max. number of iterations
callback => Any function, called before every iteration
factr => The iteration stops when (f^k - f^{k+1})/max{|f^k|,|f^{k+1}|,1} <= factr * 1E-16
The only additional option we employ over SciPy's L-BFGS-B implementation is the size of the gradient-sampling memory (M) which is initialized to 1. Further, the user can choose to employ a BFGS variant of our code (i.e., retaining BFGS matrices instead of limited-memory curvature pairs) by setting m=numpy.inf.
A sample usage of our code (on the popular Rosenbrock function) is:
import scipy.optimize
import NQN
import numpy
n = 100
funObj = scipy.optimize.rosen
gradObj = func = scipy.optimize.rosen_der
bounds = [(-0.5,0.5) for i in range(n)]
x0 = numpy.zeros(n)
scipy_output = scipy.optimize.fmin_l_bfgs_b(func,x0,fprime=grad,bounds=bounds)
NQN_output = NQN.fmin_l_bfgs_b(func,x0,fprime=grad,bounds=bounds)
Similar to the SciPy L-BFGS-B implementation, we return the final iterate, corresponding function value and an information dictionary. We use different termination flags from SciPy's L-BFGS-B implementation. They are
Termination Flag:
0 => Converged
1 => Reached Maximum Iterations
2 => Reached Maximum Function Evaluations
3 => Converged to Nonstationary Point
4 => Abnormal Termination in Line Search
5 => Iterate Has NaN values
6 => Numerical Issues
7 => FACTR Convergence