Abstract
Improving Hit-and-Run is a random search algorithm for global optimization that at each iteration generates a candidate point for improvement that is uniformly distributed along a randomly chosen direction within the feasible region. The candidate point is accepted as the next iterate if it offers an improvement over the current iterate. We show that for positive definite quadratic programs, the expected number of function evaluations needed to arbitrarily well approximate the optimal solution is at most O(n5/2) wheren is the dimension of the problem. Improving Hit-and-Run when applied to global optimization problems can therefore be expected to converge polynomially fast as it approaches the global optimum.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Abramowitz and I. A. Stegun, eds. (1961),Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (National Bureau of Standards, Applied Mathematics Series 55, June 1964).
C. J. P. Bélisle, H. E. Romeijn, and R. L. Smith (1993), Hit-and-Run Algorithms for Generating Multivariate Distributions, to appear inMathematics of Operations Research.
C. J. P. Bélisle, H. E. Romeijn, and R. L. Smith (1990), Hide-and-Seek: A Simulated Annealing Algorithm for Global Optimization, Technical Report 90-25, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, September 1990.
H. C. P. Berbee, C. G. E. Boender, A. H. G. Rinnooy Kan, C. L. Scheffer, R. L. Smith, and J. Teigen (1987), Hit-and-Run Algorithms for the Identification of Nonredundant Linear Inequalities,Mathematical Programming 37 184–207.
A. Boneh (1983), A Probabilistic Algorithm for Identifying Redundancy by a Random Feasible Point Generator (RFPG), in M. H. Karwan, V. Lotfi, J. Teigen, and S. Zionts, eds.,Redundancy in Mathematical Programming (Springer-Verlag, Berlin).
H. Cramér (1946),Mathematical Methods of Statistics (Princeton University Press).
L. C. W. Dixon and G. P. Szegö, eds. (1975),Towards Global Optimization (North-Holland, Amsterdam).
L. C. W. Dixon and G. P. Szegö, eds. (1978),Towards Global Optimization 2 (North-Holland, Amsterdam).
W. Feller (1971),An Introduction to Probability Theory and Its Applications, Volume 2, 2nd Edition (John Wiley and Sons, New York).
I. S. Gradshteyn and I. M. Ryzhik, eds. (1980), translated by Alan Jeffrey,Table of Integrals, Series, and Products (Academic Press, New York).
M. H. Karwan, V. Lotfl, J. Teigen, and S. Zionts, eds. (1983),Redundancy in Mathematical Programming (Springer-Verlag, Berlin), 108–134.
D. E. Knuth (1969),The Art of Computer Programming, Vol. 2 (Addison-Wesley, Reading, Massachusetts), p. 116.
J. P. Lawrence III and K. Steiglitz (1972), Randomized Pattern Search,IEEE Transactions On Computers C-21, 382–385.
K. G. Murty (1983),Linear Programming (John Wiley and Sons, New York).
V. A. Mutseniyeks and L. Rastrigin (1964), Extremal Control of Continuous Multi-Parameter Systems by the Method of Random Search,Engineering Cybernetics 1, 82–90.
N. R. Patel, R. L. Smith, and Z. B. Zabinsky (1988), Pure Adaptive Search In Monte Carlo Optimization,Mathematical Programming 43, 317–328.
L. A. Rastrigin (1960), Extremal Control by the Method of Random Scanning,Automation and Remote Control 21, 891–896.
L. A. Rastrigin (1963), The Convergence of the Random Method in the Extremal Control of a Many-Parameter System,Automation and Remote Control 24, 1337–1342.
S. M. Ross (1983),Stochastic Processes (John Wiley and Sons, New York).
L. E. Scales (1985)Introduction to Non-Linear Optimization (Macmillan).
G. Schrack and N. Borowski (1972), An Experimental Comparison of Three Random Searches, in F. Lootsma, ed.,Numerical Methods for Nonlinear Optimization (Academic Press, London), pp. 137–147.
G. Schrack and M. Choit (1976), Optimized Relative Step Size Random Searches,Mathematical Programming 10, 270–276.
M. A. Schumer and K. Steiglitz (1968), Adaptive Step Size Random Search,IEEE Transactions On Automatic Control AC-13, 270–276.
R. L. Smith (1984), Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions,Operations Research 32, 1296–1308.
F. J. Solis and R. J.-B. Wets (1981), Minimization by Random Search Techniques,Mathematics of Operations Research 6, 19–30.
A. Sommerfeld (1949),Partial Differential Equations in Physics (Academic Press, New York).
Z. B. Zabinsky (1985),Computational Complexity of Adaptive Algorithms in Monte Carlo Optimization (Ph.D. Dissertation from The University of Michigan, Ann Arbor MI).
Z. B. Zabinsky and R. L. Smith (1992), Pure Adaptive Search in Global Optimization,Mathematical Programming 53, 323–338.
Z. B. Zabinsky, D. L. Graesser, M. E. Tuttle, and G. I. Kim (1992), Global Optimization of Composite Laminates Using Improving Hit-and-Run, in C. A. Floudas and P. M. Pardalos, eds.,Recent Advances in Global Optimization, Princeton University Press.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Zabinsky, Z.B., Smith, R.L., McDonald, J.F. et al. Improving Hit-and-Run for global optimization. J Glob Optim 3, 171–192 (1993). https://doi.org/10.1007/BF01096737
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01096737