ISSN:
1573-2916
Keywords:
Random search
;
Monte Carlo optimization
;
algorithm complexity
;
global optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01096737
Permalink
