一种新的直接搜索法及其收敛性

A NEW DIRECT SEARCH ALGORITHM AND ITS CONVERGENCE

本文中的算法利用了差商和强迫矩阵正定的Cholesky 分解算法,设f(x)和~2f(x)分别为f(x)的梯度和Hessian矩阵,分别简记为f和~2f.用△f(x,s)和△~2f(x,s)分别表示f和~2f的近似,分别简记为△f和△~2f.当x=x^k,s=s_k时,它们分别简记为f^k、~2f^k、△f^k和△~2f^k.下面给出△f、△~f和强迫矩阵正定的Cholesky分解算法.

A new direct search algorithm for unconstrained optimization is given in this paper. Itproduces step by step a set of search directions from a given direction P_0, when it is appliedto a positive definite quadratic function. We'll get n mutually conjugate search directions after(n-1) iterations and the procedure will terminate at a minimum in finite iterations. Mo-reover, the number of function value evaluations is about 2/3 of that of Powell's and the numberof linear searches is about one half. Furthermore, the convergence, superlinear convergence andsecond order convergence are shown for different hypotheses. Many numerical examples showthat the algorithm is more efficient than Powell's, and in many cases also more efficient thansome analytical methods.