Name
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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01096737 | J. Global Optimization |
Keywords | DocType | Volume |
Random search,Monte Carlo optimization,algorithm complexity,global optimization | Journal | 3 |
Issue | ISSN | Citations |
2 | 0925-5001 | 24 |
PageRank | References | Authors |
5.02 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zelda B. Zabinsky | 1 | 430 | 55.93 |
| Robert L. Smith | 2 | 664 | 123.86 |
| J. Fred McDonald | 3 | 24 | 5.02 |
| H. Edwin Romeijn | 4 | 769 | 83.88 |
| David E. Kaufman | 5 | 53 | 7.29 |