Gradient set splitting in nonconvex nonsmooth numerical optimization

Abstract

We present a numerical bundle-type method for local minimization of a real function of several variables, which is supposed to be locally Lipschitz.

We provide a short survey of some optimization algorithms from the literature, which are able to deal with both nonsmoothness and nonconvexity of the objective function. We focus on possible extensions of classical bundle-type methods, originally conceived to deal with convex nonsmooth optimization. They are all based on a convex cutting plane model which has the property of both minorizing everywhere and interpolating at certain points the objective function. Such properties may be lost whenever nonconvexity is present and the case may be described in terms of possible negative values of certain linearization errors.

We describe some alternative ways the problem is dealt with in the literature.

Here, on the basis of a classification of the limit points of gradient sequences, we define two distinct cutting plane approximations. We derive an algorithm which uses both such models. In particular, only the convex model is primarily adopted to find a tentative displacement from the current stability centre, while the concave one enters into the play only when the convex model has failed in providing a sufficient decrease step.

Termination of the method is proved and the results of some numerical experiments are reported.

Keywords:

• nonsmooth optimization
• cutting planes
• bundle methods

AMS Subject Classification :

• 90C26
• 65K05

Acknowledgements

The authors thank two anonymous referees for a number of valuable suggestions. 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).