libMC

Author:
Benoit C. Chachuat
Version:
0.1.1
Date:
2006-2007
Bug:
No known bugs.
libMC.so.0.1.1 is a library defining a C++ class for calculating the McCormick relaxation of a nonconvex function on a box, as well as valid subgradients of these relaxations. Any function can be considered, provided it is factorable.

The relaxation is calculated based on the operator overloading and function overloading capabilities of C++. The overloaded operators are: `+', `-', `*', and `/'; the overloaded functions are: `exp', `log', `pow', 'sqrt', 'fabs', and 'xlog'. (Trigonometric functions such as `cos', `sin' and `tan' aren't currently supported.)

Future versions of libAD will allow dealing with a wider variety of mathematical functions. In particular, trigonometric functions such as `cos', `sin' and `tan' shall be implemented. Also, only the forward mode of AD is implemented presently, and future versions will also allow using the reverse mode of AD for relaxation calculation.

How to Calculate the Value of a McCormick Relaxation?

Suppose one is interested in calculating the value of the McCormick relaxation of the real-valued function $f(x,y)=x(\exp(x)-y)^2$ for $(x,y)\in [-2,1]^2$, at the point $(x,y)=(0,0)$.

First, we shall define the variables $x$ and $y$. This is done as follows:

McCormick X( -2., 1., 0. );

McCormick Y( -2., 1., 0. );

Essentially, the first line means that X is a variable of class McCormick, that it belongs to the interval $[-2,1]$, and that its current value is $0$. The same holds for the McCormick variable Y.

Once $x$ and $y$ have been defined, the McCormick's convex and concave relaxations of $f(x,y)$ at $(0,0)$ are simply calculated as

McCormick Z = X*pow(exp(X)-Y,2);

In particular, the value of the McCormick's convex underestimator and the McCormick's concave overestimator of $f(x,y)$ on $[-2,1]^2$ at $(0,0)$ are obtained as

double Zcvx = Z.cv();

double Zccv = Z.cc();

Likewise, a lower bound and an upper bound for the values of $f(x,y)$ on $[-2,1]^2$ are obtained as

double Zlb = Z.l();

double Zub = Z.u();

How to Calculate a Subgradient of a McCormick Relaxation?

The calculation of a subgradient of a McCormick relaxation requires that the number of variables be specified. E.g., for the previous example, the problem has two variables ($x$ and $y$), so we shall define

McCormick::np(2);

Then, the variables $x$ and $y$ are declared as before, except that the component index is now specified for the variables. For example, if $x$ and $y$ are considered to be components $0$ and $1$, respectively, we write

McCormick X( -2., 1., 0., 0 );

McCormick Y( -2., 1., 0., 1 );

The McCormick's convex and concave relaxations of $f(x,y)$ at $(0,0)$, as well as a subgradient of these relaxations, are simply calculated as

McCormick Z = X*pow(exp(X)-Y,2);

Finally, a subgradient of the McCormick's convex underestimator of $f(x,y)$ on $[-2,1]^2$ at $(0,0)$ is obtained as

const double* dZcvx = Z.dcvdp();

Alternatively, the components of this subgradient can be obtained separately as

double dZcvx_X = Z.dcvdp(0);

double dZcvx_Y = Z.dcvdp(1);

Analogously, a subgradient of the McCormick's concave overestimator of $f(x,y)$ on $[-2,1]^2$ at $(0,0)$ is obtained as

const double* dZccv = Z.dccdp();

double dZccv_X = Z.dccdp(0);

double dZccv_Y = Z.dccdp(1);

Note that whenever a McCormick relaxation is differentiable at a point, then the components of the subgradient correspond to the partial derivatives of the relaxation at that point.

Errors Encountered during Calculation of a McCormick Relaxation?

Errors are managed based on the exception handling mechanism of the C++ language. Each time an error is encountered, a class object of type MC_Excp is thrown, which contains the type of error. It is the user's responsibility to test whether an exception was thrown during a McCormick relaxation, and then make the appropriate changes. Should an exception be thrown and not caught by the calling program, the execution will stop.

Possible errors encountered during the calculation of a McCormick relaxation are:

Errors during Calculation of a McCormick relaxation
Number Description
1 The size of the problem has changed (number of parameters)
2 Error during the relaxation of a division term (division by zero)
3 Error during the relaxation of an inverse function (zero in range)
4 Error during the relaxation of a logarithm function (negative values in range)
5 Error during the relaxation of a square root function (non positive values in range)
6 Error during the relaxation of an Arrhenius-like function (negative values in range, or negative coefficient)


Generated on Sat Sep 8 20:04:36 2007 for libMC by  doxygen 1.4.6