libMC
ibMC is an open source software library for calculating convex/concave relaxations of factorable functions as well as subgradients of these relaxations. libMC has been succeeded by MC++. For the automatic generation of convex and concave relaxations of a given factorable function, a recursive procedure is first employed to develop an equivalent reformulation in terms of unary and binary operations, the so-called evaluation trace, for which intermediate variables are introduced. Then, libMC calculates enclosures as well as convex and concave relaxations recursively for each of these intermediate variables via interval analysis and McCormick relaxation techniques [3]. Because McCormick relaxations are generally non-smooth, subgradients (as opposed to gradients) need to be computed. This can be done in either one of two ways: the forward mode or the reverse mode of automatic differentiation. In the forward mode, with each elementary operation of convex and concave relaxation, additional variables are introduced which store the subgradient elements. These elements are calculated recursively upon application of the subgradient propagation theory developed in [1]. An alternative approach to the forward mode is the reverse mode, which performs similar recursive operations, but works through the evaluation trace backwards. Only the forward mode of subgradient calculation is currently implemented in libMC. Moreover, subgradients for multi-variable functions are calculated along various seed directions in libMC by matrix products, with the identity being used as the seed matrix. libMC uses an operator overloading approach (as opposed to program transformation techniques) to automate the relaxation and subgradient calculation tasks. Although less efficient than program transformation, it is worth pointing out that a simple overloading approach is perfectly adequate for many small- to medium-size problems, especially those where the relaxation calculation does not account for a high proportion of the runtime requirements.
Keywords for this software
References in zbMATH (referenced in 35 articles , 1 standard article )
Showing results 1 to 20 of 35.
Sorted by year (- Barton, Paul I.; Khan, Kamil A.; Stechlinski, Peter; Watson, Harry A. J.: Computationally relevant generalized derivatives: theory, evaluation and applications (2018)
- Hellemo, Lars; Barton, Paul I.; Tomasgard, Asgeir: Decision-dependent probabilities in stochastic programs with recourse (2018)
- Kazazakis, N.; Adjiman, C. S.: Arbitrarily tight (\alpha\mathrmBB) underestimators of general non-linear functions over sub-optimal domains (2018)
- Khan, Kamil A.: Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions (2018)
- Mitsos, Alexander; Najman, Jaromił; Kevrekidis, Ioannis G.: Optimal deterministic algorithm generation (2018)
- Baharev, Ali; Domes, Ferenc; Neumaier, Arnold: A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations (2017)
- Bongartz, Dominik; Mitsos, Alexander: Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations (2017)
- Harwood, Stuart M.; Barton, Paul I.: How to solve a design centering problem (2017)
- Khan, Kamil A.; Watson, Harry A. J.; Barton, Paul I.: Differentiable McCormick relaxations (2017)
- Rajyaguru, Jai; Villanueva, Mario E.; Houska, Boris; Chachuat, Benoît: Chebyshev model arithmetic for factorable functions (2017)
- Baier, Robert; Farkhi, Elza; Roshchina, Vera: From quasidifferentiable to directed subdifferentiable functions: exact calculus rules (2016)
- Boukouvala, Fani; Misener, Ruth; Floudas, Christodoulos A.: Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO (2016)
- Harwood, Stuart M.; Barton, Paul I.: Efficient polyhedral enclosures for the reachable set of nonlinear control systems (2016)
- Najman, Jaromił; Mitsos, Alexander: Convergence analysis of multivariate McCormick relaxations (2016)
- Ninin, Jordan; Messine, Frédéric; Hansen, Pierre: A reliable affine relaxation method for global optimization (2015)
- Scott, Joseph K.; Barton, Paul I.: Reachability analysis and deterministic global optimization of DAE models (2015)
- Villanueva, Mario E.; Houska, Boris; Chachuat, Benoît: Unified framework for the propagation of continuous-time enclosures for parametric nonlinear ODEs (2015)
- Wechsung, Achim; Scott, Joseph K.; Watson, Harry A. J.; Barton, Paul I.: Reverse propagation of McCormick relaxations (2015)
- Houska, Boris; Chachuat, Benoît: Branch-and-lift algorithm for deterministic global optimization in nonlinear optimal control (2014)
- Misener, Ruth; Floudas, Christodoulos A.: A framework for globally optimizing mixed-integer signomial programs (2014)
Further publications can be found at: http://yoric.mit.edu/biblio