×

Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints. (English) Zbl 1258.93102

Summary: 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 (see [N. V. Sahinidis, J. Glob. Optim. 8, No. 2, 201–205, (1996; Zbl 0856.90104)]), 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.

MSC:

93E10 Estimation and detection in stochastic control theory
93E24 Least squares and related methods for stochastic control systems
49M05 Numerical methods based on necessary conditions
65D10 Numerical smoothing, curve fitting
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming

Citations:

Zbl 0856.90104

Software:

GiNaC; INTOPT_90; BARON; nlmdl
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bao X, Sahinidis NV, Tawarmalani M (2009) Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim Methods Softw 24:485–504 · Zbl 1179.90252 · doi:10.1080/10556780902883184
[2] Bard Y (1974) Nonlinear parameter estimation. Academic Press, San Diego · Zbl 0345.62045
[3] Bates D, Watts DG (1988) Nonlinear regression analysis and its applications. Wiley, New York · Zbl 0728.62062
[4] Bauer C (2002) Introduction to the GiNaC framework for symbolic computation within the C++ programming language. J Symb Comput 33:1–12 · Zbl 1017.68163 · doi:10.1006/jsco.2001.0494
[5] Concha MJ (1999) Personal communication
[6] Csendes T, Ratz D (1997) Subdivision direction selection in interval methods for global optimization. SIAM J Numer Anal 34:922–938 · Zbl 0873.65063 · doi:10.1137/S0036142995281528
[7] Draper NR, Smith H (1966) Applied regression analysis. Wiley, New York
[8] 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 · doi:10.1021/ie970852g
[9] Gallant AR (1987) Nonlinear statistical models. Wiley, New York · Zbl 0611.62071
[10] Gau CY, Stadtherr MA (2002) New interval methodologies for reliable chemical process modeling. Comput Chem Eng 26:827–840 · doi:10.1016/S0098-1354(02)00005-4
[11] Hentenryck PV, Michel L, Deville Y (1997) Numerica: a modeling language for global optimization. MIT Press, Cambridge
[12] Hooker J (2000) Logic-based methods for optimization: combining optimization and constraint satisfaction. Wiley, New York · Zbl 0974.90001
[13] Horst R, Tuy H (1996) Global optimization: deterministic approaches, 3rd edn. Springer, Berlin · Zbl 0867.90105
[14] Huet S (1986) Statistical tools for nonlinear regression: a practical guide with S-PLUS examples. Springer, New York
[15] Kearfott RB (1996) Rigorous global search: continuous problems. Nonconvex Optim Appl 13 · Zbl 0876.90082
[16] Krĭvy I, Tvrdic J, Krpec R (2000) Stochastic algorithms in nonlinear regression. Comput Stat Data Anal 33:277–290 · Zbl 0990.62052 · doi:10.1016/S0167-9473(99)00059-6
[17] McCormick GP (1983) Nonlinear programming: theory, algorithms and applications. Wiley, New York
[18] Meyer RR, Roth PM (1972) Modified damped least squares: an algorithm for nonlinear estimation. J Inst Math Appl 9:218–233 · Zbl 0243.65003 · doi:10.1093/imamat/9.2.218
[19] Mittelmann HD, Pruessner A (2006) A server for automated performance analysis of benchmarking data. Optim Methods Softw 21:105–120 · Zbl 1181.90309 · doi:10.1080/10556780500065366
[20] NIST (2010) StRD nonlinear least squares regression databases. Available at http://www.itl.nist.gov/div898/strd/nls/nls_main.shtml
[21] Nocedal J, Wright SJ (2006) Global optimization: deterministic approaches, 3rd edn. Springer, Berlin
[22] Ratkowsky DA (1989) Nonlinear regression modelling. Dekker, New York
[23] Sahinidis NV (1996) BARON: a general purpose global optimization software package. J Glob Optim 8(2):201–205 · Zbl 0856.90104 · doi:10.1007/BF00138693
[24] Sahinidis NV, Tawarmalani M (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic, Dordrecht · Zbl 1031.90022
[25] Sahinidis NV, Tawarmalani M (2005) Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. J Glob Optim 32:259–280 · Zbl 1080.90087 · doi:10.1007/s10898-004-2705-8
[26] Seber GAF (1989) Nonlinear regression. Wiley, New York · Zbl 0721.62062
[27] Tawarmalani M, Sahinidis NV (2002) Convex extensions and convex envelopes of lower semi-continuous functions. Math Program 93:247–263 · Zbl 1065.90062 · doi:10.1007/s10107-002-0308-z
[28] Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563–591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[29] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103:225–249 · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[30] Tawarmalani M, Ahmed S, Sahinidis NV (2002) Product disaggregation and relaxations of mixed-integer rational programs. Optim Eng 3:281–303 · Zbl 1035.90064 · doi:10.1023/A:1021043227181
[31] Tranter RL (2000) Design and analysis in chemical research. Sheffield Academic Press, Boca Raton
[32] Tu R, Zheng Q (1993) Integral global optimization method in statistical applications. Comput Math Appl 25:9–17 · Zbl 0779.90073 · doi:10.1016/0898-1221(93)90276-2
[33] Vaia A (2003) Global optimization in least-squares problems in FTIR spectroscopy and X-ray crystallography. PhD thesis, University of Illinois, Urbana-Champaign
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.