Please use this identifier to cite or link to this item:
Title: Direct search based on probabilistic feasible descent for bound and linearly constrained problems
Authors: Gratton, Serge 
Royer, Clément W
Vicente, Luís Nunes 
Zhang, Zaikun 
Keywords: Derivative-free optimization; Direct-search methods; Bound constraints; Linear constraints; Feasible descent; Probabilistic feasible descent; Worst-case complexity
Issue Date: Jan-2019
Publisher: Springer Verlag
Project: CMUC-UID/MAT/00324/2013 
Serial title, monograph or event: Computational Optimization and Applications
Volume: 72
Abstract: Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region, and typically consist of positive generators of approximate tangent cones (which then renders the corresponding methods globally convergent in the linearly constrained case). One knows however from the unconstrained case that randomly generating the polling directions leads to better complexity bounds as well as to gains in numerical efficiency, and it becomes then natural to consider random generation also in the presence of constraints. In this paper, we study a class of direct-search methods based on sufficient decrease for solving smooth linearly constrained problems where the polling directions are randomly generated (in approximate tangent cones). The random polling directions must satisfy probabilistic feasible descent, a concept which reduces to probabilistic descent in the absence of constraints. Such a property is instrumental in establishing almost-sure global convergence and worst-case complexity bounds with overwhelming probability. Numerical results show that the randomization of the polling directions can be beneficial over standard approaches with deterministic guarantees, as it is suggested by the respective worst-case complexity bounds.
DOI: 10.1007/s10589-019-00062-4
Rights: embargoedAccess
Appears in Collections:I&D CMUC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
l-ds-random-1.pdf580.8 kBAdobe PDFView/Open
Show full item record

Google ScholarTM




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