Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization

A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an ε-feasible point and a second phase to seek optimality while maintaining at least ε-feasibility. A two-phase approach of this kind based on a cubic regularization methodology was recently proposed along with a supporting worst-case iteration complexity analysis. Unfortunately, however, in that approach, the objective function is completely ignored in the first phase when ε-feasibility is sought. The main contribution of the method proposed in this paper is that the same worst-case iteration complexity is achieved, but with a first phase that also accounts for improvements in the objective function. As such, the method typically requires fewer iterations in the second phase, as the results of numerical experiments demonstrate.