An interior-point l1-penalty method for nonlinear optimization

          Nicholas I. M. Gould, Dominique Orban and Ph. L. Toint

          Report 03/22                    8 December 2003

A mixed interior/exterior-point method for nonlinear programming is described,
that handles constraints by an $\ell_{1}$-penalty function.  A suitable
decomposition of the penalty terms and embedding of the problem into a
higher-dimensional setting leads to an equivalent, surprisingly regular,
reformulation  as a smooth penalty problem only involving inequality
constraints. The  resulting problem may then be tackled using interior-point
techniques  as finding a strictly feasible initial point is trivial.  
The reformulation relaxes the shape of the constraints, promoting larger steps
and easing the nonlinearity of the strictly  feasible set in the neighbourhood
of a solution. If finite multipliers exist, exactness of the penalty function
eliminates the need to drive the corresponding penalty parameter to
infinity. Global and fast local convergence of the proposed scheme are
established and practical aspects of the method are discussed.