631 TOWARDS SECOND-ORDER METHODS FOR STRUCTURED NONSMOOTH OPTIMIZATION M. Overton, X. Ye, April 1993
Structured nonsmooth optimization objectives often arise in a composite form f = h ffi a, where h is convex (but not necessarily polyhedral) and a is smooth. We consider the case where the structure of the nonsmooth convex function h is known. Specifically, we assume that, for any given point in the domain of h, a parameterization of a manifold \Omega , on which h reduces locally to a smooth function, is given. We discuss two affine spaces: the tangent space to the manifold \Omega at a point, and the affine hull of the subdifferential of h at the same point, and explain that these are typically orthogonal complements. We indicate how the construction of locally second-order methods is possible, even when h is nonpolyhedral, provided the appropriate Lagrangian, modeling the structure, is used. We illustrate our ideas with two important convex functions: the ordinary max function, and the max eigenvalue function for symmetric matrices, and we solicit other interesting examples with genuinely different structure from the community.