MANIFOLD SAMPLING FOR OPTIMIZATION OF NONCONVEX FUNCTIONS THAT ARE PIECEWISE LINEAR COMPOSITIONS OF SMOOTH COMPONENTS

摘要

We develop a manifold sampling algorithm for the minimization of a nonsmooth composite function f (sic) psi+hoF when psi is smooth with known derivatives, h is a known, nonsmooth, piecewise linear function, and F is smooth but expensive to evaluate. The trust-region algorithm classifies points in the domain of h as belonging to different manifolds and uses this knowledge when computing search directions. Since h is known, classifying objective manifolds using only the values of F is simple. We prove that all cluster points of the sequence of the manifold sampling algorithm iterates are Clarke stationary; this holds although points evaluated by the algorithm are not assumed to be differentiable and when only approximate derivatives of F are available. Numerical results show that manifold sampling using zeroth-order information about F is competitive with algorithms that employ exact subgradient values from partial derivative f.