Optimization Online


Manifold Sampling for L1 Nonconvex Optimization

Jeffrey Larson (jmlarson***at***anl.gov)
Matt Menickelly (mjm412***at***lehigh.edu)
Stefan Wild (wild***at***anl.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/2015
Entry Accepted: 09/30/2015
Entry Last Modified: 09/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society