Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Adaptive search in quasi-Monte Carlo optimization


Authors: Christian Biester, Peter J. Grabner, Gerhard Larcher and Robert F. Tichy
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] C. Biester, Zahlentheoretische Simulation von Zufallspunkten mit Anwendungen in der numerischen Analysis, Ph.D. Thesis, Technical University of Vienna, 1991.
  • [2] W. Hock and K. Schittkowski, Test examples for nonlinear programming codes, Springer Lecture Notes in Economics and Mathematical Systems, vol. 187, 1981. MR 611512 (82f:90084)
  • [3] H. Niederreiter, A Quasi-Monte-Carlo-Method for the approximate computation of the extreme values of a function, Studies in Pure Mathematics (P. Erdös, ed.), Birkhäuser, Basel, 1983, pp. 523-529. MR 820248 (86m:11055)
  • [4] -, Quasi-Monte-Carlo-Methods for global optimization, Proc. 4th Pannonian Sympos. Math. Stat., Bad Tatzmannsdorf (Austria), 1983, pp. 251-267. MR 851058 (87m:90092)
  • [5] -, Random number generation and Quasi-Monte-Carlo methods, SIAM Lecture Notes, vol. 63, Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • [6] H. Niederreiter and P. Peart, Localization of search in Quasi-Monte-Carlo-Methods for global optimization, SIAM J. Sci. Statist. Comput. 7 (1986), 660-664. MR 833928 (87h:65017)
  • [7] -, Quasi-Monte-Carlo-Optimization in general domains, Caribbean J. Math. 4 (1985), 67-85. MR 882064 (88b:65011)
  • [8] N. Patel, R. Smith, and Z. Zabinsky, Pure adaptive search in Monte-Carlo-Optimization, Math. Programming 43 (1988), 317-328. MR 993468 (90e:90094)
  • [9] K. Schittkowski, More test examples for nonlinear programming codes, Springer Lecture Notes in Economics and Mathematical Systems, vol. 282, 1987. MR 1117683 (92d:90003)
  • [10] R. Smith and Z. Zabinsky, Pure adaptive search in global optimization, Math. Programming 53 (1992), 323-338. MR 1152257 (93b:90092)
  • [11] R. F. Tichy, Random points on the sphere with applications to numerical analysis, Z. Angew. Math. Mech. 70 (1990), T642-T646. MR 1070175 (91i:65015)
  • [12] -, Random points in the cube and on the sphere with applications to numerical analysis, J. Comput. Appl. Math. 31 (1990), 191-197. MR 1068159 (91j:65009)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C05, 65K10

Retrieve articles in all journals with MSC: 65C05, 65K10


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1995-1270614-4
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society