Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bao X, Sahinidis NV, Tawarmalani M (2009) Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim Methods Softw 24:485–504
Bard Y (1974) Nonlinear parameter estimation. Academic Press, San Diego
Bates D, Watts DG (1988) Nonlinear regression analysis and its applications. Wiley, New York
Bauer C (2002) Introduction to the GiNaC framework for symbolic computation within the C++ programming language. J Symb Comput 33:1–12
Concha MJ (1999) Personal communication
Csendes T, Ratz D (1997) Subdivision direction selection in interval methods for global optimization. SIAM J Numer Anal 34:922–938
Draper NR, Smith H (1966) Applied regression analysis. Wiley, New York
Esposito WR, Floudas CA (1998) Global optimization in parameter estimation of nonlinear algebraic models via the error-in-variables approach. Ind Eng Chem Res 37:1841–1858
Gallant AR (1987) Nonlinear statistical models. Wiley, New York
Gau CY, Stadtherr MA (2002) New interval methodologies for reliable chemical process modeling. Comput Chem Eng 26:827–840
Hentenryck PV, Michel L, Deville Y (1997) Numerica: a modeling language for global optimization. MIT Press, Cambridge
Hooker J (2000) Logic-based methods for optimization: combining optimization and constraint satisfaction. Wiley, New York
Horst R, Tuy H (1996) Global optimization: deterministic approaches, 3rd edn. Springer, Berlin
Huet S (1986) Statistical tools for nonlinear regression: a practical guide with S-PLUS examples. Springer, New York
Kearfott RB (1996) Rigorous global search: continuous problems. Nonconvex Optim Appl 13
Krĭvy I, Tvrdic J, Krpec R (2000) Stochastic algorithms in nonlinear regression. Comput Stat Data Anal 33:277–290
McCormick GP (1983) Nonlinear programming: theory, algorithms and applications. Wiley, New York
Meyer RR, Roth PM (1972) Modified damped least squares: an algorithm for nonlinear estimation. J Inst Math Appl 9:218–233
Mittelmann HD, Pruessner A (2006) A server for automated performance analysis of benchmarking data. Optim Methods Softw 21:105–120
NIST (2010) StRD nonlinear least squares regression databases. Available at http://www.itl.nist.gov/div898/strd/nls/nls_main.shtml
Nocedal J, Wright SJ (2006) Global optimization: deterministic approaches, 3rd edn. Springer, Berlin
Ratkowsky DA (1989) Nonlinear regression modelling. Dekker, New York
Sahinidis NV (1996) BARON: a general purpose global optimization software package. J Glob Optim 8(2):201–205
Sahinidis NV, Tawarmalani M (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic, Dordrecht
Sahinidis NV, Tawarmalani M (2005) Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. J Glob Optim 32:259–280
Seber GAF (1989) Nonlinear regression. Wiley, New York
Tawarmalani M, Sahinidis NV (2002) Convex extensions and convex envelopes of lower semi-continuous functions. Math Program 93:247–263
Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563–591
Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103:225–249
Tawarmalani M, Ahmed S, Sahinidis NV (2002) Product disaggregation and relaxations of mixed-integer rational programs. Optim Eng 3:281–303
Tranter RL (2000) Design and analysis in chemical research. Sheffield Academic Press, Boca Raton
Tu R, Zheng Q (1993) Integral global optimization method in statistical applications. Comput Math Appl 25:9–17
Vaia A (2003) Global optimization in least-squares problems in FTIR spectroscopy and X-ray crystallography. PhD thesis, University of Illinois, Urbana-Champaign
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amaran, S., Sahinidis, N.V. Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints. TOP 20, 154–172 (2012). https://doi.org/10.1007/s11750-011-0178-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-011-0178-8