Publication: Adjoint Mode Computation of Subgradients for McCormick Relaxations
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Adjoint Mode Computation of Subgradients for McCormick Relaxations

- incollection -
 

Author(s)
Markus Beckers , Viktor Mosenkis , Uwe Naumann

Published in
Recent Advances in Algorithmic Differentiation

Editor(s)
Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, Andrea Walther

Year
2012

Publisher
Springer

Abstract
In Mitsos et al. (SIAM Journal on Optimization 20(2):573–601, 2009), a method similar to Algorithmic Differentiation (ad) is presented which allows the propagation of, in general nondifferentiable, McCormick relaxations (McCormick, Mathematical Programming 10(2):147–175, 1976; Steihaug, Twelfth Euro ad Workshop, Berlin, 2011) of factorable functions and of the corresponding subgradients in tangent-linear mode. Subgradients are natural extensions of “usual” derivatives which allow the application of derivative-based methods to possibly nondifferentiable convex and concave functions. The software package libMC (Mitsos et al. SIAM Journal on Optimization 20(2):573–601, 2009) performs the automatic propagation of the relaxation and of corresponding subgradients based on the principles of tangent-linear mode ad by overloading. Similar ideas have been ported to Fortran yielding modMC as part of our ongoing collaboration with the authors of Mitsos et al. (SIAM Journal on Optimization 20(2):573–601, 2009). In this article an adjoint method for the computation of subgradients for McCormick relaxations is presented. A corresponding implementation by overloading in Fortran is provided in the form of amodMC. The calculated subgradients are used in a deterministic global optimization algorithm based on a branch-and-bound method. The superiority of adjoint over tangent-linear mode is illustrated by two examples.

Cross-References
Forth2012RAi

BibTeX
@INCOLLECTION{
         Beckers2012AMC,
       title = "Adjoint Mode Computation of Subgradients for {M}c{C}ormick Relaxations",
       doi = "10.1007/978-3-642-30023-3_10",
       author = "Markus Beckers and Viktor Mosenkis and Uwe Naumann",
       abstract = "In Mitsos et al. (SIAM Journal on Optimization 20(2):573–601, 2009), a
         method similar to Algorithmic Differentiation (AD) is presented which allows the propagation of, in
         general nondifferentiable, McCormick relaxations (McCormick, Mathematical Programming
         10(2):147–175, 1976; Steihaug, Twelfth Euro AD Workshop, Berlin, 2011) of factorable
         functions and of the corresponding subgradients in tangent-linear mode. Subgradients are natural
         extensions of “usual” derivatives which allow the application of
         derivative-based methods to possibly nondifferentiable convex and concave functions. The software
         package libMC (Mitsos et al. SIAM Journal on Optimization 20(2):573–601, 2009) performs
         the automatic propagation of the relaxation and of corresponding subgradients based on the
         principles of tangent-linear mode AD by overloading. Similar ideas have been ported to Fortran
         yielding modMC as part of our ongoing collaboration with the authors of Mitsos et al. (SIAM Journal
         on Optimization 20(2):573–601, 2009). In this article an adjoint method for the
         computation of subgradients for McCormick relaxations is presented. A corresponding implementation
         by overloading in Fortran is provided in the form of amodMC. The calculated subgradients are used in
         a deterministic global optimization algorithm based on a branch-and-bound method. The superiority of
         adjoint over tangent-linear mode is illustrated by two examples.",
       pages = "103--113",
       crossref = "Forth2012RAi",
       booktitle = "Recent Advances in Algorithmic Differentiation",
       series = "Lecture Notes in Computational Science and Engineering",
       publisher = "Springer",
       address = "Berlin",
       volume = "87",
       editor = "Shaun Forth and Paul Hovland and Eric Phipps and Jean Utke and Andrea Walther",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2012"
}


back
  

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