OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A second-order globally convergent direct-search method and its worst-case complexity

Gratton, Serge and Royer, Clément and Vicente, Luis Nunes A second-order globally convergent direct-search method and its worst-case complexity. (2015) Optimization: A Journal of Mathematical Programming and Operations Research, 65 (6). 1105-1128. ISSN 0233-1934

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1080/02331934.2015.1124271


Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest descent direction, which can be quantified by a first-order criticality (cosine) measure. The use of a set of vectors with a positive cosine measure together with the imposition of a sufficient decrease condition to accept new iterates leads to a convergence result as well as a worst-case complexity bound. In this paper, we present a second-order study of a general class of direct-search methods. We start by proving a weak second-order convergence result related to a criticality measure defined along the directions used throughout the iterations. Extensions of this result to obtain a true second-order optimality one are discussed, one possibility being a method using approximate Hessian eigenvectors as directions (which is proved to be truly second-order globally convergent). Numerically guaranteeing such a convergence can be rather expensive to ensure, as it is indicated by the worst-case complexity analysis provided in this paper, but turns out to be appropriate for some pathological examples.

Item Type:Article
Additional Information:Thanks to Taylor and Francis editor. The original PDF can be found at Optimization (ISSN 0233-1934) website : http://www.tandfonline.com/doi/abs/10.1080/02331934.2015.1124271
HAL Id:hal-01515985
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Universidade de Coimbra (PORTUGAL)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:27 Apr 2017 15:02

Repository Staff Only: item control page