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 \triangleq \psi + h \circ F$ 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 f$.