Argonne National Laboratory

Manifold Sampling for Nonconvex Optimization of Piecewise Linear Compositions

TitleManifold Sampling for Nonconvex Optimization of Piecewise Linear Compositions
Publication TypeReport
Year of Publication2017
AuthorsKhan, 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.