Optimization Online


Manifold Sampling for Optimization of Nonconvex Functions that are Piecewise Linear Compositions of Smooth Components

Kamil Khan (kamilkhan***at***mcmaster.ca)
Jeffrey Larson (jmlarson***at***anl.gov)
Stefan M Wild (wild***at***anl.gov)

Abstract: We develop a manifold sampling algorithm for the minimization of a nonsmooth composite function $f \defined \psi + h \circ F$ when $\psi$ 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 zeroth-order information about $F$ is competitive with algorithms that employ exact subgradient values from $\partial f$.

Keywords: Manifold Sampling, Composite Nonsmooth Optimization, Derivative-Free Optimization

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Mathematics and Computer Science Division Preprint ANL/MCS-P8001-0817, September 2017

Download: [PDF]

Entry Submitted: 10/01/2017
Entry Accepted: 10/01/2017
Entry Last Modified: 04/19/2018

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