McCormick-Ungleichungen

Wir betrachten die Funktion $f(x_1,x_2):=x_1{x}_2$ mit $f:Q:=\left[{\underline{x}}_1,{\bar{x}}_1\right]\times \left[{\underline{x}}_2,{\bar{x}}_2\right]\to \mathbb{R}$ .

Wobei $\underline{x}$ die unteren Schranken und $\bar{x}$ die oberen Schranken darstellen.

Die McCormick-Ungleichungen sind:

1. $w\ge {\underline{x}}_2{x}_1+{\underline{x}}_1{x}_2-{\underline{x}}_1{\underline{x}}_2$
2. $w\ge {\bar{x}}_2{x}_1+{\bar{x}}_1{x}_2-{\bar{x}}_1{\bar{x}}_2$
3. $w\le {\underline{x}}_2{x}_1+{\bar{x}}_1{x}_2-{\bar{x}}_1{\underline{x}}_2$
4. $w\le {\bar{x}}_2{x}_1+{\underline{x}}_1{x}_2-{\underline{x}}_1{\bar{x}}_2$

Wir können damit also konvexe Hüllen von bilinearen Ausdrücken durch Ungleichungen darstellen.

Beweis: Berechnung durch verschiedene Kombinationen von $0\le (x_1-{\underline{x}}_1)(x_2-{\underline{x}}_2)$