{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T13:49:43Z","timestamp":1789134583971,"version":"build-2803163510"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the optimization problem by repeated optimization over a randomly chosen one-dimensional subspace. This randomized method only uses zeroth-order information about the objective function and does not need any problem-specific parametrization. We prove convergence and give convergence rates for smooth objectives assuming that the one-dimensional optimization can be solved exactly or approximately by an oracle. A convenient property of Random Pursuit is its invariance under strictly monotone transformations of the objective function. It thus enjoys identical convergence behavior on a wider function class. To support the theoretical results we present extensive numerical performance results of Random Pursuit, two gradient-free algorithms recently proposed by Nesterov, and a classical adaptive step size random search scheme. We also present an accelerated heuristic version of the Random Pursuit algorithm which significantly improves standard Random Pursuit on all numerical benchmark problems. A general comparison of the experimental results reveals that (i) standard Random Pursuit is effective on strongly convex functions with moderate condition number and (ii) the accelerated scheme is comparable to Nesterov's fast gradient method and outperforms adaptive step size strategies.<\/jats:p>","DOI":"10.1137\/110853613","type":"journal-article","created":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T11:22:46Z","timestamp":1372332166000},"page":"1284-1309","source":"Crossref","is-referenced-by-count":25,"title":["Optimization of Convex Functions with Random Pursuit"],"prefix":"10.1137","volume":"23","author":[{"given":"S. U.","family":"Stich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. L.","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"G\u00e4rtner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1953.10501200"},{"key":"atypb2","first-page":"3","author":"Auger A.","year":"2009","journal-title":"Berlin"},{"key":"atypb3","first-page":"269","author":"Betro B.","year":"1978","journal-title":"Amsterdam"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"H. G. Beyer,<i>The theory of evolution strategies<\/i> Nat. Comput., Springer-Verlag, New York, 2001.","DOI":"10.1007\/978-3-662-04378-3"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/12\/7\/075008"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.2.244"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.2005.v3.n4.a6"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"A. R. Conn, K. Scheinberg, and L. N. Vicente,<i>Introduction to Derivative-Free Optimization<\/i> MPS\/SIAM Ser. Optim., SIAM, Philadelphia, 2009.","DOI":"10.1137\/1.9780898718768"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/04061115X"},{"key":"atypb10","first-page":"306","author":"Hazan E.","year":"2008","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02927114"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0327055"},{"key":"atypb13","first-page":"453","author":"Igel C.","year":"2006","journal-title":"New York"},{"key":"atypb14","first-page":"356","author":"J\u00e4gersk\u00fcpper J.","year":"2005","journal-title":"Berlin"},{"key":"atypb15","first-page":"118","author":"J\u00e4gersk\u00fcpper J.","year":"2007","journal-title":"Berlin"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(74)90131-1"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/1119084"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(63)90018-9"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1981.1085030"},{"key":"atypb20","first-page":"1135","author":"Kleiner A.","year":"2010","journal-title":"Culotta"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450242889"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0041-5553(83)80028-7"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1080\/02331930903100141"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1177\/003754976600700511"},{"key":"atypb25","first-page":"432","author":"M\u00fcller C. L.","year":"2010","journal-title":"Berlin"},{"key":"atypb26","first-page":"82","volume":"1","author":"Mutseniyeks V. A.","year":"1964","journal-title":"Eng. Cybernetics"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,<i>Introductory Lectures on Convex Optimization<\/i> Kluwer, Boston, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb29","unstructured":"Y. Nesterov,<i>Random Gradient-Free Minimization of Convex Functions<\/i> Technical report, ECORE, 2011."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/080741069"},{"key":"atypb31","unstructured":"B. Polyak,<i>Introduction to Optimization<\/i> Optimization Software, New York, 1987."},{"key":"atypb32","unstructured":"MATLAB R2012a, http:\/\/www.mathworks.ch\/help\/toolbox\/optim\/ug\/fminunc.html (2012)."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1002\/zamm.19890690119"},{"key":"atypb34","first-page":"1337","volume":"24","author":"Rastrigin L. A.","year":"1963","journal-title":"Autom. Remote Control"},{"key":"atypb35","unstructured":"I. Rechenberg,<i>Evolutionsstrategie; Optimierung technischer Systeme nach Prinzipien der biologischen Evolution<\/i> Frommann-Holzboog, Stuttgart-Bad Cannstatt, 1973."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1968.1098903"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"S. U. Stich, C. L. M\u00fcller, and B. G\u00e4rtner,<i>Supporting online material for optimization of convex functions with random pursuit<\/i> arXiv:1111.0194v2, 2012.","DOI":"10.1137\/110853613"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.67"},{"key":"atypb40","unstructured":"S. Vempala,<i>Recent progress and open problems in algorithmic convex geometry<\/i> in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), K. Lodaya and M. Mahajan, eds., Leibniz International Proceedings in Informatics (LIPIcs) 8, Dagstuhl, Germany, 2010, pp. 42-64."},{"key":"atypb41","unstructured":"A. A. Zhigljavsky and A. G. Zilinskas,<i>Stochastic Global Optimization<\/i> Springer-Verlag, Berlin, Germany, 2008."},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"R. Zieli\u0144ski and P. Neumann,<i>Stochastische Verfahren zur Suche nach dem Minimum einer Funktion<\/i> Akademie-Verlag, Berlin, Germany, 1983.","DOI":"10.1515\/9783112733431"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110853613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:06:27Z","timestamp":1787339187000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110853613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110853613"],"URL":"https:\/\/doi.org\/10.1137\/110853613","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}