  Superlinear convergence has been an elusive goal for black-box nonsmooth
optimization. Even in the convex case, the subgradient method is very slow, and
while some cutting plane algorithms, including traditional bundle methods, are
popular in practice, local convergence is still sluggish. Faster variants
depend either on problem structure or on analyses that elide sequences of
"null" steps. Motivated by a semi-structured approach to optimization and the
sequential quadratic programming philosophy, we describe a new bundle Newton
method that incorporates second-order objective information with the usual
linear approximation oracle. One representative problem class consists of
maxima of several smooth functions, individually inaccessible to the oracle.
Given as additional input just the cardinality of the optimal active set, we
prove local quadratic convergence. A simple implementation shows promise on
more general functions, both convex and nonconvex, and suggests first-order
analogues.
