A subclass of generating set search with convergence to second-order stationary points

作者：Abramson Mark A^*; Frimannslund Lennart; Steihaug Trond

来源：Optimization Methods and Software, 2014, 29(5): 900-918.

DOI：10.1080/10556788.2013.808198

• derivative-free optimization
• second-order optimality conditions
• generating set search
• convergence analysis
• directional direct search

In generalized pattern search algorithms for linearly constrained optimization, certain limit points have been shown to satisfy a pseudo-second-order necessary condition, in which positive semidefiniteness of the Hessian is achieved only with respect to an orthonormal basis. Satisfaction of the full second-order condition can only be ensured if the finite set of positive spanning directions includes the eigenvectors of the Hessian at the limit point. Of course, this is generally not possible in practice, due to the unavailability of derivatives. The present work takes advantage of a chief feature of the more general parent class of generating set search algorithms - that of allowing the use of an infinite (non-dense) set of directions in the limit. If approximate second derivative information is gathered during the iteration process, then the normalized eigenvectors of the approximate Hessian can be used to construct the set of 2n orthonormal directions used by the algorithm. If the Hessian approximation converges in the limit to the true Hessian (or a matrix in the generalized Hessian), then the full second-order optimality conditions can be achieved. Two approaches for generating such a convergent approximate Hessian are described. Numerical examples show the effectiveness of the approach.

• 出版日期2014