An exact augmented Lagrangian function exploiting negative curvature directions

In this paper we propose a primal-dual algorithm for the solution of inequality constrained optimization problems. The distinguishing feature of the proposed algorithm is that of exploiting as much as possible the local non-convexity of the problem. In the unconstrained case this task is accomplished by computing a suitable negative curvature direction of the objective function. In the constrained case it is possible to gain analogous information by exploiting the non-convexity of a particular exact merit function. The algorithm employes an adaptive linesearch procedure whose distinguishing feature is that of comparing, at every iteration, the relative effects of two directions and then selecting the more promising one. The first direction conveys first order information on the problem and can be used to define a sequence of points converging toward a KKT pair of the problem. Whereas, the second direction conveys information on the local non-convexity of the problem and can be used to drive the algorithm away from regions of non-convexity. We propose a proper selection rule for these two directions which, under suitable assumptions, is able to generate a sequence of points that is globally convergent to KKT pairs, possibly with superlinear convergence rate.