A novel algorithm is designed to solve nonlinear unconstrained optimization problems, when the derivatives of the objective function can neither be calculated nor be approximated. For the purpose of reducing the amount of calculation of the objective function, we present a hybrid algorithm which combines UOBYQA and multidirectional search method by reconstructing trust region subproblems. A distinguishing feature of the hybrid algorithm is that it solves the two trust region subproblems in the same improved trust region which is fixed by the weight of two descent directions indicated by a triangular simplex. Not only does the hybrid method improve the classic trust region based on multidirectional search method algorithm, but also ensures the adequacy of the interpolation equations by maximizing the Lagrange functions in the improved trust region. The numerical experiment shows that the hybrid method is much more efficient than UOBYQA and other similar algorithms.

multidirectional search method, unconstrained optimization, simplex, quadratic model, Lagrange function.