(531d) An Algorithm for the Global Optimization of Unconstrained Parameter Estimation Problems

Unconstrained nonlinear least-squares problems have been studied since the development of the first nonlinear optimization algorithms. However, the non-convexity of the sum-of-squared-errors objective in parameter estimation problems often leads to the presence of multiple local minima. Globally optimal parameters are desirable not only from a theoretical point of view, but they may translate to significant differences in accuracy of simulations or economics of processes.

Methods for the global minimization of such problems have been studied only in the more recent past. Though spatial branch-and-bound algorithms have met with success in many cases, there is still significant scope for improvement in terms of times of solution and capacity to solve more complex highly nonlinear problems. The primary objective of this work is to present a novel approach to the global optimization of parameter estimation problems. An equally important objective is to provide access to global optimization algorithms through a software package.

Towards our first objective, we focus on the lower-bounding algorithm that forms the crux of the spatial branch-and-bound method. We hypothesize that the explicit use of first-order optimality conditions will help in constructing tight convex relaxations to factorable programs and hence, significantly expedite convergence to global optimality. First, a motivating example is presented and then, the results obtained from a large number of test cases taken from the statistics and engineering literatures are analyzed. We follow this with a discussion of the successes and limitations of the proposed idea. Our results suggest that our approach allows larger problems to become tractable to a wider bracket of researchers and practitioners.

Towards our second objective, we describe our implementation which, via an R interface, makes our methodology available to the scientific community as an open-source statistical tool.