Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/45248
 Title: Direct Search Based on Probabilistic Descent Authors: Gratton, S. Royer, C. W. Vicente, Luís Nunes Zhang, Zaikun Issue Date: 2015 Publisher: Society for Industrial and Applied Mathematics (SIAM) Project: PEst-C/MAT/UI0324/2011 Serial title, monograph or event: SIAM Journal on Optimization Volume: 25 Issue: 3 Abstract: Direct-search methods are a class of popular derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions. When applied to the minimization of smooth functions, the polling directions are typically taken from positive spanning sets, which in turn must have at least n+1 vectors in an $n$-dimensional variable space. In addition, to ensure the global convergence of these algorithms, the positive spanning sets used throughout the iterations are required to be uniformly nondegenerate in the sense of having a positive (cosine) measure bounded away from zero. However, recent numerical results indicated that randomly generating the polling directions without imposing the positive spanning property can improve the performance of these methods, especially when the number of directions is chosen as considerably less than n+1. In this paper, we analyze direct-search algorithms when the polling directions are probabilistic descent, meaning that with a certain probability at least one of them is of descent type. Such a framework enjoys almost-sure global convergence. More interestingly, we will show a global decaying rate of $1/\sqrt{k}$ for the gradient size, with overwhelmingly high probability, matching the corresponding rate for the deterministic versions of the gradient method or of direct search. Our analysis helps us understand numerical behavior and the choice of the number of polling directions. URI: http://hdl.handle.net/10316/45248 Other Identifiers: 10.1137/140961602 DOI: 10.1137/140961602 Rights: openAccess Appears in Collections: I&D CMUC - Artigos em Revistas Internacionais

###### Files in This Item:
File Description SizeFormat
ds-random.pdf384.93 kBAdobe PDF

#### SCOPUSTM Citations

11
checked on Nov 8, 2019

#### WEB OF SCIENCETM Citations

11
checked on Nov 7, 2019

#### Page view(s)

103
checked on Jan 15, 2020

#### Download(s)

56
checked on Jan 15, 2020

Check

#### Altmetric

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.