Piecewise linear approximations in nonconvex nonsmooth optimization

We present a bundle type method for minimizing nonconvex nondifferentiable functions of several variables. The algorithm is based on the construction of both a lower and an upper polyhedral approximation of the objective function. In particular, at each iteration, a search direction is computed by solving a quadratic program aiming at maximizing the difference between the lower and the upper model. A proximal approach is used to guarantee convergence to a stationary point under the hypothesis of weak semismoothness. This research has been partially supported by the Italian “Ministero dell’Istruzione, dell’Università e della Ricerca”, under PRIN project Ottimizzazione Non Lineare e Applicazioni (20079PLLN7_003).