Inexact Restoration method for nonlinear optimization without derivatives

Abstract

A derivative-free optimization method is proposed for solving a general nonlinear programming problem. It is assumed that the derivatives of the objective function and the constraints are not available. The new method is based on the Inexact Restoration scheme, where each iteration is decomposed in two phases. In the first one, the violation of the feasibility is reduced. In the second one, the objective function is minimized onto a linearization of the nonlinear constraints. At both phases, polynomial interpolation models are used in order to approximate the objective function and the constraints. At the first phase a derivative-free solver for box constrained optimization can be used. For the second phase, we propose a new method ad-hoc based on trust-region strategy that uses the projection of the simplex gradient on the tangent space. Under suitable assumptions, the algorithm is well defined and convergence results are proved. A numerical implementation is described and numerical experiments are presented to validate the theoretical results.