Gradient set splitting in nonconvex nonsmooth numerical optimization

GAUDIOSO, MANLIO;GORGONE, ENRICO

2010-01-01

---

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.