MS 00-005 Abstract

A Second Order Trust Region Bundle Method for Nonconvex Nonsmooth Optimization

Andreas Grothey

Technical Report MS 02-001

Bundle methods for the minimization of nonsmooth functions have been around for almost 20 years. Numerous variations have been proposed. But until recently they all suffered from the drawback of only linear convergence or were limited to convex problems. This paper presents a new bundle variant which exploits an analogy with SQP to give rise to a superlinearly convergent bundle method. The presented algorithm features a trust region rather than a line-search strategy. We will prove global convergence of the algorithm and give computational results underpinning the claim of superlinear convergence even for nonconvex problems.

Key words: bundle-methods, nonsmooth optimization, nonconvex optimization, second-order methods
dvi MS 02-001.dvi (~87Kb).
postscript MS (~1.1Mb).
G-Zipped postscript MS (~0.6Mb).