Adaptive search in quasi-Monte Carlo optimization
HTML articles powered by AMS MathViewer
- by Christian Biester, Peter J. Grabner, Gerhard Larcher and Robert F. Tichy PDF
- Math. Comp. 64 (1995), 807-818 Request permission
Abstract:
Motivated by a linear time-complexity result for an adaptive Monte Carlo algorithm, we propose and analyze an adaptive deterministic algorithm. We restrict a grid search to nested subregions that promise to provide improvement of the current solution, and we obtain an exponential rate of convergence in function evaluations. For proving the main result we restrict ourselves to functions on hypercubes. In a final section we outline how to extend the method to the general case and give some numerical examples.References
-
C. Biester, Zahlentheoretische Simulation von Zufallspunkten mit Anwendungen in der numerischen Analysis, Ph.D. Thesis, Technical University of Vienna, 1991.
- Willi Hock and Klaus Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, Springer-Verlag, Berlin-New York, 1981. MR 611512, DOI 10.1007/BF00934594
- H. Niederreiter, A quasi-Monte Carlo method for the approximate computation of the extreme values of a function, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 523–529. MR 820248
- Harald Niederreiter, Quasi-Monte Carlo methods for global optimization, Mathematical statistics and applications, Vol. B (Bad Tatzmannsdorf, 1983) Reidel, Dordrecht, 1985, pp. 251–267. MR 851058
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- Harald Niederreiter and Paul Peart, Localization of search in quasi-Monte Carlo methods for global optimization, SIAM J. Sci. Statist. Comput. 7 (1986), no. 2, 660–664. MR 833928, DOI 10.1137/0907044
- H. Niederreiter and P. Peart, Quasi-Monte Carlo optimization in general domains, Caribbean J. Math. 4 (1985), no. 2, 67–85. MR 882064
- Nitin R. Patel, Robert L. Smith, and Zelda B. Zabinsky, Pure adaptive search in Monte Carlo optimization, Math. Programming 43 (1989), no. 3, (Ser. A), 317–328. MR 993468, DOI 10.1007/BF01582296
- Klaus Schittkowski, More test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 282, Springer-Verlag, Berlin, 1987. MR 1117683, DOI 10.1007/978-3-642-61582-5
- Zelda B. Zabinsky and Robert L. Smith, Pure adaptive search in global optimization, Math. Programming 53 (1992), no. 3, Ser. A, 323–338. MR 1152257, DOI 10.1007/BF01585710
- R. F. Tichy, Random points on the sphere with applications to numerical analysis, Z. Angew. Math. Mech. 70 (1990), no. 6, T642–T646. Bericht über die Wissenschaftliche Jahrestagung der GAMM (Karlsruhe, 1989). MR 1070175, DOI 10.1016/0377-0427(90)90350-9
- Robert F. Tichy, Random points in the cube and on the sphere with applications to numerical analysis, J. Comput. Appl. Math. 31 (1990), no. 1, 191–197. Random numbers and simulation (Lambrecht, 1988). MR 1068159, DOI 10.1016/0377-0427(90)90350-9
Additional Information
- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp. 64 (1995), 807-818
- MSC: Primary 65C05; Secondary 65K10
- DOI: https://doi.org/10.1090/S0025-5718-1995-1270614-4
- MathSciNet review: 1270614