Argonne National Laboratory

Manifold Sampling for L1 Nonconvex Optimization

TitleManifold Sampling for L1 Nonconvex Optimization
Publication TypeReport
Year of Publication2015
AuthorsLarson, J, Menickelly, M, Wild, SM
Other NumbersANL/MCS-P5392-0915

We provide a new algorithm, called manifold sampling, for the unconstrained minimization of a nonsmooth composite function h ◦ F . By classifying points in the domain of h into what we call manifolds, we adapt search directions within a trust-region framework based on knowl- edge of manifolds intersecting the current trust region. We motivate this idea through a study of l1 functions, where the classification into manifolds using zero-order information about the constituent functions Fi is trivial, and give an explicit statement of a manifold sampling algorithm in that case. We prove that all cluster points of iterates generated by this algorithm are stationary in the Clarke sense. We prove a similar result for a stochastic variant of the algorithm; interestingly, the result is deterministic (not almost sure). Additionally, our algorithm can accept iterates that are points of nondifferentiability and requires only an approximation of gradients of F at the trust-region center. Numerical results presented for different variants of the algorithm show that using manifold information from points near the current iterate can improve practical performance.