Group for Research in Decision Analysis


An Interior-Point l1-Penalty Method for Nonlinear Optimization

, , and

A mixed interior/exterior-point method for nonlinear programming is described, that handles constraints by way of 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. If the penalty parameter needs to increase without bound and if feasibility is ultimately attained, a certificate of degeneracy is delivered. Global and fast local convergence of the proposed scheme are established and practical aspects of the method are discussed.

, 39 pages