Optimal Newton-Type Algorithms for Large-Scale Nonlinear Optimization

Summary of project findings

1) We considered smooth nonconvex unconstrained optimization problems and have found that Adaptive Regularization with Cubics (ARC) methods are optimal from a worst-case evaluation complexity viewpoint amongst a large class of second-order methods, thus being more efficient than Newton's method and other state-of-the-art methods such as trust-region and line-search, for generating an approximate local solution of the problem.

2) We have analysed the worst-case complexity of constrained optimization problems and were able to devise both first- and second-order methods for this class that have the same worst-case evaluation complexity as in the unconstrained case, a surprising find given that constrained problems are generally more challenging to solve than unconstrained ones. The second-order methods we developed in this context extend ARC algorithms to the constrained case.

3) Using key ideas from ARC methods, we have developed a novel parallel branch-and-bound algorithm for global optimization problems (where it is crucial to find the global minimum/maximum not just a local solution), called oBB (Overlapping Branch-and-Bound). It employs novel bounding and branching mechanisms, both inspired by the cubic model and its properties and the availability of Lipschitz derivative information. We have tested oBB on state-of-the-art test problems with promising results. We have written appropriate documentation and made the resulting code freely available on a dedicated website https://pypi.python.org/pypi/oBB



Pathways to Exploitation

Our work on the worst-case complexity of algorithms gives a novel understanding of optimization methods and their efficiency, of interest to both researchers and users of optimization algorithms. Our global optimization algorithm oBB can be downloaded freely and used by anyone with a need to solve a small to medium size global optimization problem, in serial or in parallel. This includes both academia and industry users of optimization. As nonlinear

optimization is an essential component of computational science, engineering and operations research, the potential use of our code is ubiquitous. To make our code more accessible and visible, we have recently submitted it to be reviewed for and if successful, posted on one of the most prominent software repositories in optimization and operations-research, COIN-OR.



Potential Use in Non-Academic Contexts

Our software oBB can be downloaded for free from a dedicated website and employed by industry users in need of solving global optimization problems. These problems abound in computational science and engineering, and the demand for efficient software is significant. To make our code more accessible and visible, we have had it reviewed for and successfully accepted to become

part of COIN-OR, one of the most prominent software repositories in optimization and operations-research that is also open-source. The COIN-OR

dedicated page to oBB is https://projects.coin-or.org/oBB/

URL https://pypi.python.org/pypi/oBB(https://pypi.python.org/pypi/oBB)