tr-announce November 2011

tr-announce@lists.rwth-aachen.de

1 Teilnehmer
2 Diskussionen

2011-25: Compiler-Generated Subgradient Code for McCormick Relaxations

von Carsten Fuhs

The following technical report is available from http://aib.informatik.rwth-aachen.de: Compiler-Generated Subgradient Code for McCormick Relaxations Callum Corbett, Michael Maier, Markus Beckers, Uwe Naumann, Amin Ghobeity, Alexander Mitsos AIB 2011-25 McCormick Relaxations are special convex and concave under- and overestimators which are used in the field of nonconvex global optimization. As they are possibly nonsmooth at some points subgradients are used as derivative information. Subgradients are natural extensions of usual derivatives. They may be used to construct linear or piecewise linear relaxations. [Mitsos et al. 2009] developed a corresponding method and the library libMC (written in C++) for propagating relaxations and related subgradients using the tangent-linear mode of Algorithmic Differentiation (also known as Automatic Differentiation) by operator overloading. This report extends [Mitsos et al. 2009] by providing libMC functionality by source transformation in Fortran. The corresponding Fortran module modMC is described. A research prototype of the NAG Fortran compiler has been extended with domain-specific inlining techniques to enable the generation of tangent-linear McCormick code. Speedups by factors of up to four with respect to the runtime of the respective libMC-based implementation can be observed. These results are supported by a number of relevant applications. To perform the numerical experiments, an interface between tangent-linear McCormick code written in Fortran and the existing C++-implementation of the branch-and-bound algorithm has been established.

12 Jahre, 4 Monate

2011-24: Demonstration of a Branch-and-Bound Algorithm for Global Optimization using McCormick Relaxations

von Carsten Fuhs

The following technical report is available from http://aib.informatik.rwth-aachen.de: Demonstration of a Branch-and-Bound Algorithm for Global Optimization using McCormick Relaxations Callum Corbett, Uwe Naumann, Alexander Mitsos AIB 2011-24 This report is meant to demonstrate the actions performed by a branch-and-bound algorithm for global optimization on a simple minimization problem. McCormick relaxations are used to construct piecewise affine underestimators of the objective function.

12 Jahre, 4 Monate

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce November 2011