Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints
-
Satyajith Amaran [1] ; Nikolaos V. Sahinidis [1]
-
[1] Carnegie Mellon University
Carnegie Mellon University
City of Pittsburgh, Estados Unidos
-
- Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 20, Nº. 1, 2012, págs. 154-172
- Idioma: inglés
- Enlaces
-
Resumen
We study a simple, yet unconventional approach to the global optimization of unconstrained nonlinear least-squares problems. Non-convexity of the sum of least-squares objective in parameter estimation problems may often lead to the presence of multiple local minima. Here, we focus on the spatial branch-and-bound algorithm for global optimization and experiment with one of its implementations, BARON (Sahinidis in J. Glob. Optim. 8(2):201–205, 1996), to solve parameter estimation problems. Through the explicit use of first-order optimality conditions, we are able to significantly expedite convergence to global optimality by strengthening the relaxation of the lower-bounding problem that forms a crucial part of the spatial branch-and-bound technique. We analyze the results obtained from 69 test cases taken from the statistics literature and discuss the successes and limitations of the proposed idea. In addition, we discuss software implementation for the automation of our strategy.
