Manifold Sampling for Nonconvex Optimization of Piecewise Linear Compositions
|Title||Manifold Sampling for Nonconvex Optimization of Piecewise Linear Compositions|
|Year of Publication||2017|
|Authors||Khan, K, Larson, J, Wild, SM|
We develop a manifold sampling algorithm for the unconstrained minimization of a nonsmooth composite function f = ψ + h o F when ψ is smooth with known derivatives, h is a 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 zero-order information is competitive with gradient sampling algorithms that are given exact gradient values.