Discontinuous piecewise linear optimization

A theoretical framework and a practical algorithm are presented to solve discontinuous piecewise linear optimization problems dealing with functions for which the ridges are known. A penalty approach allows one to consider such problems subject to a wide range of constraints involving piecewise linear functions. Although the theory is expounded in detail in the special case of discontinuous piecewise linear functions, it is straightforwardly extendable, using standard nonlinear programming techniques, to nonlinear (discontinuous piecewise differentiable) functions. The descent algorithm which is elaborated uses active-set and projected gradient approaches. It is a generalization of the ideas used by Conn to deal with nonsmoothness in the l(1) exact penalty function, and it is based on the notion of decomposition of a function into a smooth and a nonsmooth part. The constrained case is reduced to the unconstrained minimization of a (piecewise linear) l(1) exact penalty function. We also discuss how the algorithm is modified when it encounters degenerate points. Preliminary numerical results are presented: the algorithm is applied to discontinuous optimization problems from models in industrial engineering. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.