Publication: Enumeration of subdifferentials of piecewise linear functions with abs-normal form
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Enumeration of subdifferentials of piecewise linear functions with abs-normal form

- Article in a journal -
 

Author(s)
Koichi Kubota

Published in
Special issue of Optimization Methods & Software: Advances in Algorithmic Differentiation Optimization Methods & Software

Editor(s)
Bruce Christianson, Shaun A. Forth, Andreas Griewank

Year
2018

Publisher
Taylor & Francis

Abstract
The directional derivatives of a piecewise smooth function at a given point can be computed with Griewank's absolute normal form (ANF). When the given point is a non-differentiable point, the resulting derivative by ordinary algorithmic differentiation is included in the subdifferential. In this paper, with ANF, a method for computing and enumerating the elements of the limiting subdifferential at a given non-differential point is described with branch and bound search. Using such an enumeration, we can compute the values of limiting derivatives and, if required, we can check the first-order optimality of the piecewise linear function derived by the piecewise smooth function given by the form of the evaluation procedure, when the sophisticated algorithm for checking the optimalities is known. The worst-case complexity of the proposed algorithm is exponential in general, but we show that there may be some cases in which computational work may be reduced using the branch and bound search with numerical examples.

Cross-References
Christianson2018Sio

BibTeX
@ARTICLE{
         Kubota2018Eos,
       crossref = "Christianson2018Sio",
       author = "Koichi Kubota",
       title = "Enumeration of subdifferentials of piecewise linear functions with abs-normal form",
       journal = "Optimization Methods \& Software",
       volume = "33",
       number = "4--6",
       pages = "1156--1172",
       year = "2018",
       publisher = "Taylor \& Francis",
       doi = "10.1080/10556788.2018.1458848",
       url = "https://doi.org/10.1080/10556788.2018.1458848",
       eprint = "https://doi.org/10.1080/10556788.2018.1458848",
       abstract = "The directional derivatives of a piecewise smooth function at a given point can be
         computed with Griewank's absolute normal form (ANF). When the given point is a
         non-differentiable point, the resulting derivative by ordinary algorithmic differentiation is
         included in the subdifferential. In this paper, with ANF, a method for computing and enumerating the
         elements of the limiting subdifferential at a given non-differential point is described with branch
         and bound search. Using such an enumeration, we can compute the values of limiting derivatives and,
         if required, we can check the first-order optimality of the piecewise linear function derived by the
         piecewise smooth function given by the form of the evaluation procedure, when the sophisticated
         algorithm for checking the optimalities is known. The worst-case complexity of the proposed
         algorithm is exponential in general, but we show that there may be some cases in which computational
         work may be reduced using the branch and bound search with numerical examples.",
       booktitle = "Special issue of Optimization Methods \& Software: Advances in
         Algorithmic Differentiation",
       editor = "Bruce Christianson and Shaun A. Forth and Andreas Griewank"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)