libMC 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.