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 23 articles , 1 standard article )
Showing results 1 to 20 of 23.
Sorted by year (- 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)
- 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.: ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations (2014)
- Misener, Ruth; Floudas, Christodoulos A.: A framework for globally optimizing mixed-integer signomial programs (2014)
- Tsoukalas, A.; Mitsos, A.: Multivariate McCormick relaxations (2014)
- Wechsung, Achim; Barton, Paul I.: Global optimization of bounded factorable functions with discontinuities (2014)
- Bompadre, Agustín; Mitsos, Alexander; Chachuat, Beno{^ı}t: Convergence analysis of Taylor models and McCormick-Taylor models (2013)
- Scott, Joseph K.; Barton, Paul I.: Convex and concave relaxations for the parametric solutions of semi-explicit index-one differential-algebraic equations (2013)
- Scott, Joseph K.; Barton, Paul I.: Improved relaxations for the parametric solutions of ODEs using differential inequalities (2013)
- Beckers, Markus; Mosenkis, Viktor; Naumann, Uwe: Adjoint mode computation of subgradients for McCormick relaxations (2012)
- Bompadre, Agustín; Mitsos, Alexander: Convergence rate of McCormick relaxations (2012)
- Skjäl, A.; Westerlund, T.; Misener, R.; Floudas, C.A.: A generalization of the classical $\alpha $BB convex underestimation via diagonal and nondiagonal quadratic terms (2012)
- Li, Xiang; Tomasgard, Asgeir; Barton, Paul I.: Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs (2011)
- Sahlodin, Ali M.; Chachuat, Beno{^i}t: Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs (2011)
Further publications can be found at: http://yoric.mit.edu/biblio