Convergence results for generalized pattern search algorithms are tight

作     者：Audet, C 

作者机构：Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada 

出 版 物：《OPTIMIZATION AND ENGINEERING》 (最优化与工程学)

年 卷 期：2004年第5卷第2期

页      面：101-122页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 

主　　题：pattern search algorithms convergence analysis unconstrained optimization non-smooth analysis Clarke derivatives 

摘      要：The convergence theory of generalized pattern search algorithms for unconstrained optimization guarantees under mild conditions that the method produces a limit point satisfying first order optimality conditions related to the local differentiability of the objective function. By exploiting the flexibility allowed by the algorithm, we derive six small dimensional examples showing that the convergence results are tight in the sense that they cannot be strengthened without additional assumptions, i.e., that certain requirement imposed on pattern search algorithms are not merely artifacts of the proofs. In particular, we first show the necessity of the requirement that some algorithmic parameters are rational. We then show that, even for continuously differentiable functions, the method may generate infinitely many limit points, some of which may have non-zero gradients. Finally, we consider functions that are not strictly differentiable. We show that even when a single limit point is generated, the gradient may be non-zero, and zero may be excluded from the generalized gradient, therefore, the method does not necessarily produce a Clarke stationary point.