An interior-point L1-penalty method for nonlinear optimization

N. I. M. Gould (n.gouldrl.ac.uk)
D. Orban (orbanpolymtl.ca)
Ph. L. Toint (philippe.tointfundp.ac.be)

Abstract: A mixed interior/exterior-point method for nonlinear programming is described, that handles constraints by an L1-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.

Keywords: Nonlinear programming, L1 penalty, primal-dual interior-point methods, regularization

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report RAL-TR-2003-022 Rutherford Appleton Laboratory Chilton, Oxfordshire, UK, November 2003.

Download: [Compressed Postscript][PDF]

Entry Submitted: 11/18/2003
Entry Accepted: 11/18/2003
Entry Last Modified: 11/18/2003

Modify/Update this entry