VU-Decomposition Derivatives for Convex Max-Functions

For minimizing a convex max-function f we consider, at a minimizer, a space decomposition. That is, we distinguish a subspace V, where f’s nonsmoothness is concentrated, from its orthogonal complement, U. We characterize smooth trajectories, tangent to U, along which f has a second order expansion. We give conditions (weaker than typical strong second order sufficient conditions for optimality) guaranteeing the existence of a Hessian of a related U-Lagrangian. We also prove, under weak assumptions and for a general convex function, superlinear convergence of a conceptual algorithm for minimizing f using VU-decomposition derivatives.