Abstract
“Hit-and-run is fast and fun” to generate a random point in a high dimensional convex set K (Lovász/Vempala, MSR-TR-2003-05). More precisely, the hit-and-run random walk mixes fast independently of where it is started inside the convex set. To hit-and-run from a point \({x} \varepsilon {\mathcal{R}}^{n}\), a line L through x is randomly chosen (uniformly over all directions). Subsequently, the walk’s next point is sampled from L ∩ K using a membership oracle which tells us whether a point is in K or not.
Here the focus is on black-box optimization, however, where the function \(f:{\mathcal{R}}^{n} \rightarrow \mathcal R\) to be minimized is given as an oracle, namely a black box for f-evaluations. We obtain in an obvious way a direct-search method when we substitute the f-oracle for the K-membership oracle to do a line search over L, and, naturally, we are interested in how fast such a hit-and-run direct-search heuristic converges to the optimum point x * in the search space \({\mathcal{R}}^{n}\).
We prove that, even under the assumption of perfect line search, the search converges (at best) linearly at an expected rate larger (i.e. worse) than 1 − 1/n. This implies a lower bound of 0.5 n on the expected number of line searches necessary to halve the approximation error. Moreover, we show that 0.4 n line searches suffice to halve the approximation error only with an exponentially small probability of \(\exp(-\Omega(n^{1/3}))\). Since each line search requires at least one query to the f-oracle, the lower bounds obtained hold also for the number of f-evaluations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bertsimas, D., Vempala, S.: Solving convex programs by random walks. Journal of the ACM 51(4), 540–556 (2004)
Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems 39(4), 525–544 (2006)
Dyer, M.E., Frieze, A.M., Kannan, R.: A random polynomial time algorithm for approximating the volume of convex bodies. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 375–381. ACM Press, New York (1989)
Fogel, D.B. (ed.): Evolutionary Computation: The Fossil Record. Wiley-IEEE Press, Chichester (1998)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. American Statistical Association Journal 58(301), 13–30 (1963)
Hooke, R., Jeeves, T.A.: ”Direct search” solution of numerical and statistical problems. Journal of the ACM 8(2), 212–229 (1961)
Jägersküpper, J.: Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, Springer, Heidelberg (2003)
Jägersküpper, J.: Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoretical Computer Science 379(3), 329–347 (2007)
Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review 45(3), 385–482 (2004)
Lovász, L., Vempala, S.: Hit-and-run from a corner. SIAM Journal on Computing 35(4), 985–1005 (2006)
Nelder, J.A., Mead, R.: A simplex method for function minimization. The Computer Journal 7, 308–313 (1965)
Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, Chichester (1983)
Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, Heidelberg (2006)
Rechenberg, I.: Cybernetic solution path of an experimental problem. Royal Aircraft Establishment. In: Fogel (ed.) (1965)
Schwefel, H.-P: Kybernetische Evolution als Strategie der experimentellen Forschung in der Strömungstechnik. Diploma thesis, Technische Universität Berlin (1965)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jägersküpper, J. (2007). Lower Bounds for Hit-and-Run Direct Search. In: Hromkovič, J., Královič, R., Nunkesser, M., Widmayer, P. (eds) Stochastic Algorithms: Foundations and Applications. SAGA 2007. Lecture Notes in Computer Science, vol 4665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74871-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-74871-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74870-0
Online ISBN: 978-3-540-74871-7
eBook Packages: Computer ScienceComputer Science (R0)