Avoiding the Maratos Effect by Means of a Nonrnonotone Line Search: I. General Constrained Problems.

Abstract

An essential condition for quasi-Newton optimization methods to converge superlinearly is that a full step of one be taken close to the solution. It is well known that, when dealing with constrained optimization problems, line search schemes ensuring global convergence of such methods may prevent this from occurring (the so called "Maratos effect"). Two types of techniques have been used to circumvent this difficulty. In the watchdog technique, the full step of one is occasionally accepted even when the line search criterion is violated; subsequent backtracking is used if global convergence appears to be lost. In a "bending" technique proposed by Mayne and Polak, backtracking is avoided by performing a search along an arc whose construction requires evaluation of constraint functions at an auxiliary point; along this arc, the full step of one is accepted close to a solution. The main idea in the present paper is to comWne Mayne and Polak's technique with a non-monotone line search proposed by Grippo, Lampariello and Lucidi in the context of unconstrained optimization, in such a way that, asymptotically, function evaluations are no longer performed at auxiliary points. In a companion paper (part II), it is shown that a refinement of this scheme can be used in the context of recently proposed SQP- based methods generating feasible iterates.