Optimization Online


Manifold Sampling for Nonconvex Optimization of Piecewise Linear Compositions

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 unconstrained minimization of a nonsmooth composite function f , ψ + h ◦ 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.

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: 10/02/2017

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