Argonne National Laboratory

Manifold Sampling for Optimization of Nonconvex Functions That Are Piecewise Linear Compositions of Smooth Components

TitleManifold Sampling for Optimization of Nonconvex Functions That Are Piecewise Linear Compositions of Smooth Components
Publication TypeReport
Year of Publication2017
AuthorsKhan, K, Larson, J, Wild, SM
AbstractWe  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 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  zero-order  information  is  competitive  with  algorithms that employ exact subgradient values from f.
PDFhttp://www.mcs.anl.gov/papers/P8001-0817.pdf