  


Direct search based on probabilistic descent
S. Gratton(serge.grattonenseeiht.fr) Abstract: Directsearch methods are a class of popular derivativefree 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 ndimensional 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 considerably less than n+1. In this paper, we analyze directsearch 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 almostsure 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 to understand numerical behavior and the choice of the number of polling directions. Keywords: Derivativefree optimization, directsearch methods, polling, positive spanning sets, probabilistic descent, random directions. Category 1: Nonlinear Optimization Category 2: Stochastic Programming Category 3: Convex and Nonsmooth Optimization Citation: S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang, Direct search based on probabilistic descent, preprint 1411, Dept. Mathematics, Univ. Coimbra, 2014. Download: [PDF] Entry Submitted: 03/19/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  