- Manifold Sampling for L1 Nonconvex Optimization Jeffrey Larson (jmlarsonanl.gov) Matt Menickelly (mjm412lehigh.edu) Stefan Wild (wildanl.gov) Abstract: We present a new algorithm, called manifold sampling, for the unconstrained minimization of a nonsmooth composite function $h\circ F$ when $h$ has known structure. In particular, by classifying points in the domain of the nonsmooth function $h$ into manifolds, we adapt search directions within a trust-region framework based on knowledge of manifolds intersecting the current trust region. We motivate this idea through a study of $\ell_1$ functions, where it is trivial to classify objective function manifolds using zeroth-order information from the constituent functions $F_i$, and give an explicit statement of a manifold sampling algorithm in this 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. Additionally, our algorithm can accept iterates that are points where $h$ is nondifferentiable and requires only an approximation of gradients of $F$ at the trust-region center. Numerical results for several variants of the algorithm show that using manifold information from additional points near the current iterate can improve practical performance. The best variants are also shown to be competitive, particularly in terms of robustness, with other nonsmooth, derivative-free solvers. Keywords: Composite Nonsmooth Optimization, Gradient Sampling, Derivative-Free Optimization Category 1: Nonlinear Optimization Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Unpublished report at Argonne National Laboratory Mathematics and Computer Science Division 9700 South Cass Ave Argonne, IL 60439 September 2015 Report No: ANL/MCS-P5392-0915 Download: [PDF]Entry Submitted: 09/30/2015Entry Accepted: 09/30/2015Entry Last Modified: 09/02/2016Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.