Study of multiscale global optimization based on parameter space partition. (English) Zbl 1208.90138
Summary: Inverse problems in geophysics are usually described as data misfit minimization problems, which are difficult to solve because of various mathematical features, such as multi-parameters, nonlinearity and ill-posedness. Local optimization based on function gradient can not guarantee to find globally optimal solutions, unless a starting point is sufficiently close to the solution. Some global optimization methods based on stochastic searching mechanisms converge in the limit to a globally optimal solution with probability 1. However, finding the global optimum of a complex function is still a great challenge and practically impossible for some problems so far. This work develops a multiscale deterministic global optimization method which divides the definition space into sub-domains. Each of these sub-domains contains the same local optimal solution. Local optimization methods and attraction field search algorithms are combined to determine the basin of attraction near the local solution at different function smoothness scales. With the multiscale parameter space partition method, all attraction fields are determined after finite steps of parameter space partition, which can prevent redundant searching near the known local solutions. Numerical examples demonstrate the efficiency, global searching ability and stability of this method.
MSC:
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Bomze I.M., Csendes T., Horst R., Pardalos P.M.: Developments in Global Optimization: Nonconvex Optimization and Its Applications. Kluwer, Dordrecht (1997) · Zbl 0865.00047 |
| [2] | Gray, P., Hart, W., Painton, L., et al.: A Survey of Global Optimization Methods. Technical report, Sandia National Laboratories (1997) |
| [3] | Scales J.A., Smith M.L., Fischer T.L: Global optimization methods for multimodal inverse problems. J. Comput. Phys. 103, 258–268 (1992) · Zbl 0765.65062 · doi:10.1016/0021-9991(92)90400-S |
| [4] | Deng, L.H., Scales, J.A.: Estimating the Topography of Multi-dimensional Fitness Functions. Colorado School of Mines (1999) |
| [5] | Rothman D.H.: Nonlinear inversion, statistical-mechanics, and residual statics Estimation. Geophysics 50, 2784–2796 (1985) · doi:10.1190/1.1441899 |
| [6] | Rothman D.H.: Automatic estimation of large residual statics corrections. Geophysics 51, 332–346 (1986) · doi:10.1190/1.1442092 |
| [7] | Kirkpatrick S., Gelatt C.D., Vecchi M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [8] | Holland J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975) · Zbl 0317.68006 |
| [9] | Goldberg D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989) · Zbl 0721.68056 |
| [10] | Stoffa P.L., Sen M.K.: Nonlinear multiparameter optimization using genetic algorithms–inversion of plane-wave seismograms. Geophysics 56, 1794–1810 (1991) · doi:10.1190/1.1442992 |
| [11] | Sambridge M., Drijkoningen G.: Genetic algorithms in seismic wave-form inversion. Geophys. J. Int. 109, 323–342 (1992) · doi:10.1111/j.1365-246X.1992.tb00100.x |
| [12] | Gallagher K., Sambridge M., Drijkoningen G.: Genetic algorithms–an evolution from Monte-Carlo methods for strongly nonlinear geophysical optimization problems. Geophys. Res. Lett. 18, 2177–2180 (1991) · doi:10.1029/91GL02368 |
| [13] | Gallagher K., Sambridge M.: Genetic algorithms–a powerful tool for large-scale nonlinear optimization problems. Comput. Geosci. 20, 1229–1236 (1994) · doi:10.1016/0098-3004(94)90072-8 |
| [14] | Sen M., Stoffa P.L.: Global Optimization Methods in Geophysical Inversion. Elsevier, Amsterdam (1995) · Zbl 0871.90107 |
| [15] | Gill P.E., Murray W., Wright M.H.: Practical Optimization. Academic Press, New York (1981) |
| [16] | Granville V., Krivanek M., Rasson J.P.: Simulated annealing–a proof of convergence. IEEE Trans. Pattern Anal. Mach. Intell. 16, 652–656 (1994) · doi:10.1109/34.295910 |
| [17] | Greenhalgh D., Marshall S.: Convergence criteria for genetic algorithms. SIAM J. Comput. 30, 269–282 (2000) · Zbl 0959.68103 · doi:10.1137/S009753979732565X |
| [18] | Locatelli M.: Convergence and first hitting time of simulated annealing algorithms for continuous global optimization. Math. Methods Oper. Res. 54, 171–199 (2001) · Zbl 1031.90071 · doi:10.1007/s001860100149 |
| [19] | Locatelli M.: Convergence of a simulated annealing algorithm for continuous global optimization. J. Glob. Optim. 18, 219–234 (2000) · Zbl 1039.90100 · doi:10.1023/A:1008339019740 |
| [20] | Locatelli M.: Simulated annealing algorithms for continuous global optimization: convergence conditions. J. Optim. Theory Appl. 104, 121–133 (2000) · Zbl 0970.90102 · doi:10.1023/A:1004680806815 |
| [21] | Locatelli M.: Convergence properties of simulated annealing for continuous global optimization. J. Appl. Probab. 33, 1127–1140 (1996) · Zbl 0879.60007 · doi:10.2307/3214991 |
| [22] | Belisle C.J.P.: Convergence theorems for a class of simulated annealing algorithms on R(D). J. Appl. Probab. 29, 885–895 (1992) · Zbl 0765.65059 · doi:10.2307/3214721 |
| [23] | Fallat M.R., Dosso S.E.: Geoacoustic inversion via local, global, and hybrid algorithms. J. Acoust. Soc. Am. 105, 3219–3230 (1999) · doi:10.1121/1.424651 |
| [24] | Liu P.C., Hartzell S., Stephenson W.: Nonlinear multiparameter inversion using a hybrid global search algorithm–applications in reflection seismology. Geophys. J. Int. 122, 991–1000 (1995) · doi:10.1111/j.1365-246X.1995.tb06851.x |
| [25] | Cary P.W., Chapman C.H.: Automatic 1-D waveform inversion of marine seismic refraction data. Geophys. J. Int. 93, 527–546 (1988) · Zbl 0637.73028 · doi:10.1111/j.1365-246X.1988.tb03879.x |
| [26] | Gerstoft P.: Inversion of acoustic data using a combination of genetic algorithms and the Gauss–Newton approach. J. Acoust. Soc. Am. 97, 2181–2190 (1995) · doi:10.1121/1.411943 |
| [27] | Hibbert D.B.: A hybrid genetic algorithm for the estimation of kinetic-parameters. Chemometr. Intell. Lab. 19, 319–329 (1993) · doi:10.1016/0169-7439(93)80031-C |
| [28] | Chunduru R.K., Sen M.K., Stoffa P.L.: Hybrid optimization methods for geophysical inversion. Geophysics 62, 1196–1207 (1997) · doi:10.1190/1.1444220 |
| [29] | Calderon-Macias C., Sen M.K., Stoffa P.L.: Artificial neural networks for parameter estimation in geophysics. Geophys. Prospect. 48, 21–47 (2000) · doi:10.1046/j.1365-2478.2000.00171.x |
| [30] | Chelouah R., Siarry P.: A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions. Eur. J. Oper. Res. 161, 636–654 (2005) · Zbl 1071.90035 · doi:10.1016/j.ejor.2003.08.053 |
| [31] | Gil C., Marquez A., Banos R. et al.: A hybrid method for solving multi-objective global optimization problems. J. Glob. Optim. 38, 265–281 (2007) · Zbl 1179.90300 · doi:10.1007/s10898-006-9105-1 |
| [32] | Olensek J., Burmen A., Puhan J., Tuma T.: DESA: a new hybrid global optimization method and its application to analog integrated circuit sizing. J. Glob. Optim. 44, 53–77 (2009) · Zbl 1172.90494 · doi:10.1007/s10898-008-9307-9 |
| [33] | Yiu K.F.C., Liu Y., Teo K.L.: A hybrid descent method for global optimization. J. Glob. Optim. 28, 229–238 (2004) · Zbl 1114.90163 · doi:10.1023/B:JOGO.0000015313.93974.b0 |
| [34] | Xu P.L.: A hybrid global optimization method: the multi-dimensional case. J. Comput. Appl. Math. 155, 423–446 (2003) · Zbl 1020.65033 |
| [35] | Hedar A.R., Fukushima M.: Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim. Methods Softw. 17, 891–912 (2002) · Zbl 1065.90081 · doi:10.1080/1055678021000030084 |
| [36] | Barhen J., Protopopescu V., Reister D.: TRUST: a deterministic algorithm for global optimization. Science 276, 1094–1097 (1997) · Zbl 1226.90073 · doi:10.1126/science.276.5315.1094 |
| [37] | Basso P.: Iterative methods for the localization of the global maximum. SIAM J. Numer. Anal. 19, 781–792 (1982) · Zbl 0483.65038 · doi:10.1137/0719054 |
| [38] | Shubert B.O.: Sequential method seeking global maximum of a function. SIAM J. Numer. Anal. 9, 379–388 (1972) · Zbl 0251.65052 · doi:10.1137/0709036 |
| [39] | Floudas C.: Global Optimization: Theory, Methods and Applications. Kluwer, Dordrecht (2000) |
| [40] | Hansen E.: Global optimization using interval-analysis–the multidimensional case. Numer. Math. 34, 247–270 (1980) · Zbl 0442.65052 · doi:10.1007/BF01396702 |
| [41] | Hansen E.R.: Global optimization using interval analysis– one-dimensional case. J. Optim. Theory Appl. 29, 331–344 (1979) · Zbl 0388.65023 · doi:10.1007/BF00933139 |
| [42] | Hansen E.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (1992) · Zbl 0762.90069 |
| [43] | Ichida K., Fujii Y.: Interval arithmetic method for global optimization. Computing 23, 85–97 (1979) · doi:10.1007/BF02252616 |
| [44] | Kearfott R.B.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht (1996) · Zbl 0876.90082 |
| [45] | Ratschek H., Rokne J.: New Computer Methods for Global Optimization. Ellis Horwood, Chichester (1988) · Zbl 0648.65049 |
| [46] | Tarvainen M., Tiira T., Husebye E.S.: Locating regional seismic events with global optimization based on interval arithmetic. Geophys. J. Int. 138, 879–885 (1999) · doi:10.1046/j.1365-246x.1999.00920.x |
| [47] | Land A.H., Doig A.G.: An automatic method for solving discrete programming problems. Econometrica 28, 497–520 (1960) · Zbl 0101.37004 · doi:10.2307/1910129 |
| [48] | Clausen, J.: Branch and bound algorithms–principles and examples. In: Department of Computer Science, University of Copenhagen (1999, March) |
| [49] | Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Boston (2002) · Zbl 1031.90022 |
| [50] | Khajavirad, A., Michalek, J.J.: A deterministic Lagrangian-based global optimization approach for quasiseparable nonconvex mixed-integer nonlinear programs. J. Mech. Design 131, 051009 (8pp) |
| [51] | Qu S.J., Ji Y., Zhang K.C.: A deterministic global optimization algorithm based on a linearizing method for nonconvex quadratically constrained programs. Math. Comput. Model. 48, 1737–1743 (2008) · Zbl 1187.90212 · doi:10.1016/j.mcm.2008.04.004 |
| [52] | Jiao H.W., Chen Y.Q.: A note on a deterministic global optimization algorithm. Appl. Math. Comput. 202, 67–70 (2008) · Zbl 1154.65048 · doi:10.1016/j.amc.2008.01.021 |
| [53] | Wu Y., Lai K.K., Liu Y.J.: Deterministic global optimization approach to steady-state distribution gas pipeline networks. Optim. Eng. 8, 259–275 (2007) · Zbl 1175.90080 · doi:10.1007/s11081-007-9018-y |
| [54] | Long C.E., Polisetty P.K., Gatzke E.P.: Deterministic global optimization for nonlinear model predictive control of hybrid dynamic systems. Int. J. Robust Nonlinear Control 17, 1232–1250 (2007) · Zbl 1266.93045 · doi:10.1002/rnc.1105 |
| [55] | Lin Y.D., Stadtherr M.A.: Deterministic global optimization of nonlinear dynamic systems. AICHE J. 53, 866–875 (2007) · doi:10.1002/aic.11101 |
| [56] | Ji Y., Zhang K.C., Qu S.H.: A deterministic global optimization algorithm. Appl. Math. Comput. 185, 382–387 (2007) · Zbl 1114.65062 · doi:10.1016/j.amc.2006.06.101 |
| [57] | Lin Y., Stadtherr M.A.: Deterministic global optimization for parameter estimation of dynamic systems. Ind Eng Chem Res 45, 8438–8448 (2006) · doi:10.1021/ie0513907 |
| [58] | Long C.E., Polisetty P.K., Gatzke E.P.: Nonlinear model predictive control using deterministic global optimization. J. Process Control 16, 635–643 (2006) · doi:10.1016/j.jprocont.2005.11.001 |
| [59] | Lin Y.D., Stadtherr M.A.: Deterministic global optimization of molecular structures using interval analysis. J. Comput. Chem. 26, 1413–1420 (2005) · doi:10.1002/jcc.20285 |
| [60] | Sun, W.T., Shu, J.W., Zheng, W.M.: Deterministic global optimization with a neighbourhood determination algorithm based on neural networks. In: Advances in Neural Networks–ISNN 2005, Pt 1, Proceedings, vol. 3496, pp. 700–705 (2005) · Zbl 1082.68705 |
| [61] | Messine F.: Deterministic global optimization using interval constraint propagation techniques. Rairo Oper. Res. 38, 277–293 (2004) · Zbl 1114.90156 · doi:10.1051/ro:2004026 |
| [62] | Adjiman C.S., Papamichail I.: A deterministic global optimization algorithm for problems with nonlinear dynamics. Front. Glob. Optim. 74, 1–23 (2004) · Zbl 1165.49306 |
| [63] | Gau C.Y.T., Schrage L.E.: Implementation and testing of a branch-and-bound based method for deterministic global optimization: operations research applications. Front. Glob. Optim. 74, 145–164 (2004) · Zbl 1165.90687 |
| [64] | Lin Y., Stadtherr M.A.: Advances in interval methods for deterministic global optimization in chemical engineering. J. Glob. Optim. 29, 281–296 (2004) · Zbl 1065.65076 · doi:10.1023/B:JOGO.0000044770.73245.14 |
| [65] | Bartholomew-Biggs M.C., Parkhurst S.C., Wilson S.R.: Global optimization–stochastic or deterministic?. Stoch. Algorithms Found. Appl. 2827, 125–137 (2003) · Zbl 1161.90409 · doi:10.1007/978-3-540-39816-5_12 |
| [66] | Sambridge M.: Geophysical inversion with a neighbourhood algorithm–II. Appraising the ensemble. Geophys. J. Int. 138, 727–746 (1999) · doi:10.1046/j.1365-246x.1999.00900.x |
| [67] | Sambridge M.: Geophysical inversion with a neighbourhood algorithm–I. Searching a parameter space. Geophys. J. Int. 138, 479–494 (1999) · doi:10.1046/j.1365-246X.1999.00876.x |
| [68] | Sambridge M., Braun J., Mcqueen H.: Geophysical parametrization and interpolation of irregular data using natural neighbors. Geophys. J. Int. 122, 837–857 (1995) · doi:10.1111/j.1365-246X.1995.tb06841.x |
| [69] | Locatelli M., Wood G.R.: Objective function features providing barriers to rapid global optimization. J. Glob. Optim. 31, 549–565 (2005) · Zbl 1093.90093 · doi:10.1007/s10898-004-9965-1 |
| [70] | Locatelli M.: On the multilevel structure of global optimization problems. Comput. Optim. Appl. 30, 5–22 (2005) · Zbl 1130.90035 · doi:10.1007/s10589-005-4561-y |
| [71] | Daubechies I., Mallat S., Willsky A.S.: Special issue on wavelet transforms and multiresolution signal analysis–introduction. IEEE Trans. Inf. Theory 38, 529–531 (1992) |
| [72] | Daubechies I.: The wavelet transform, time-frequency localization and signal analysis. IEEE Trans. Inf. Theory 36, 961–1005 (1990) · Zbl 0738.94004 · doi:10.1109/18.57199 |
| [73] | Daubechies I.: Ten Lectures on Wavelets. SIAM, Philadelphia (1992) · Zbl 0776.42018 |
| [74] | Mallat S.: A theory for multiresolution signal decomposition: the wavelet representation. IEEE Trans. Pattern Anal. Mach. Intell. 11, 674–693 (1989) · Zbl 0709.94650 · doi:10.1109/34.192463 |
| [75] | Meyer, Y.: Principle d’incertitude, basis Hilbertiennes et algebras d’operateurs. In: Bourbaki Seminar (1885–1986) |
| [76] | Daubechies I.: Orthonormal bases of compactly supported wavelets. Commun. Pure Appl. Math. 41, 909–996 (1988) · Zbl 0644.42026 · doi:10.1002/cpa.3160410705 |
| [77] | Daubechies I., Paul T.: Time frequency localization operators–a geometric phase-space approach 2. The use of dilations. Inverse Probl. 4, 661–680 (1988) · Zbl 0701.42004 · doi:10.1088/0266-5611/4/3/009 |
| [78] | Kalantari B., Rosen J.B.: Construction of large-scale global minimum concave quadratic test problems. J. Optim. Theory Appl. 48, 303–313 (1986) · Zbl 0559.90066 · doi:10.1007/BF00940675 |
| [79] | Floudas C., Pardalos P.M.: A collection of test problems for constrained global optimization algorithms. In: Goos GaH, J. Lecture Notes in Computer Science, Springer, Berlin (1990) · Zbl 0718.90054 |
| [80] | Khoury B.N., Pardalos P.M., Du D.Z.: A test problem generator for the Steiner problem in graphs. ACM Trans. Math. Softw. 19, 509–522 (1993) · Zbl 0885.90110 · doi:10.1145/168173.168420 |
| [81] | Schoen F.: A wide class of test functions for global optimization. J. Glob. Optim. 3, 133–137 (1993) · Zbl 0772.90072 · doi:10.1007/BF01096734 |
| [82] | Mathar R., Zilinskas A.: A class of test functions for global optimization. J. Glob. Optim. 5, 195–199 (1994) · Zbl 0809.90119 · doi:10.1007/BF01100693 |
| [83] | Facchinei F., Judice J., Soares J.: Generating box-constrained optimization problems. ACM Trans. Math. Softw. 23, 443–447 (1997) · Zbl 0903.65056 · doi:10.1145/275323.275331 |
| [84] | Gaviano R., Lera D.: Test functions with variable attraction regions for global optimization problems. J. Glob. Optim. 13, 207–223 (1998) · Zbl 0912.90254 · doi:10.1023/A:1008225728209 |
| [85] | Gaviano M., Kvasov D.E., Lera D., Sergeyev Y.D.: Algorithm 829: software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29, 469–480 (2003) · Zbl 1068.90600 · doi:10.1145/962437.962444 |
| [86] | Mishra, S.: Some new test functions for global optimization and performance of repulsive particle swarm method. In: MPRA (2006) |
| [87] | Addis B., Locatelli M.: A new class of test functions for global optimization. J. Glob. Optim. 38, 479–501 (2007) · Zbl 1180.90302 · doi:10.1007/s10898-006-9099-8 |
| [88] | Jones D.R., Perttunen C.D., Stuckman B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993) · Zbl 0796.49032 · doi:10.1007/BF00941892 |
| [89] | Liang, J.J., Suganthan, P.N., Deb, K.: Novel composition test functions for numerical global optimization. In: 2005 IEEE Swarm Intelligence Symposium, Pasadena, pp. 68–75. IEEE Press (2005) |
| [90] | Schwefel H.-P.: Numerical Optimization of Computer Models. Wiley, New York (1981) · Zbl 0451.65043 |
| [91] | Ackley D.H.: A Connectionist Machine for Genetic Hillclimbing. Springer, Boston (1987) |
| [92] | Conn A.R., Gould N.I.M., Toint P.L.: Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50, 399–430 (1988) · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3 |
| [93] | Branch M.A., Coleman T.F., Li Y.Y.: A subspace, interior, and conjugate gradient method for large-scale bound-constrained minimization problems. SIAM J. Sci. Comput. 21, 1–23 (1999) · Zbl 0940.65065 · doi:10.1137/S1064827595289108 |
| [94] | Dixon L.C.W., Szego G.P.: The optimization problem: an introduction. In: Dixon, L.C.W., Szego, G.P. (eds) Towards Global Optimization II, North Holland, New York (1978) |
| [95] | Goldstei A.A., Price J.F.: Descent from local minima. Math. Comput. 25, 569–574 (1971) · Zbl 0223.65020 · doi:10.1090/S0025-5718-1971-0312365-X |
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.
