DISCONTINUOUS PIECEWISE-LINEAR OPTIMIZATION

A theoretical framework and a practical algorithm are presented to sol ve discontinuous piecewise linear optimization problems dealing with f unctions for which the ridges are known. A penalty approach allows one to consider such problems subject to a wide range of constraints invo lving 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 program ming 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 fun ction, and it is based on the notion of decomposition of a function in to a smooth and a nonsmooth part. The constrained case is reduced to t he unconstrained minimization of a (piecewise linear) l(1) exact penal ty function. We also discuss how the algorithm is modified when it enc ounters degenerate points. Preliminary numerical results are presented : the algorithm is applied to discontinuous optimization problems from models in industrial engineering. (C) 1998 The Mathematical Programmi ng Society, Inc. Published by Elsevier Science B.V.