3.7.61. Convex hull relaxation

Given a non -convex set ๐’ฎ, โ„› is a convex outer approximation of ๐’ฎ if:

  • โ„› is convex,

  • If sโˆˆ๐’ฎ, then sโˆˆโ„›.

Given a non -convex set ๐’ฎ, โ„› is the convex hull of ๐’ฎ if:

  • โ„› is a convex outer approximation of ๐’ฎ,

  • For every ๐’ฏ where ๐’ฏ is a convex outer approximation of ๐’ฎ, โ„›โŠ†๐’ฏ.

Partย (A) of Figureย 3.7.15 depicts a non -convex set, while partย (B) gives its corresponding convex hull.

Figure 3.7.15. Convex hull of a non -convex set
ctrs/convex_hull_relaxation

Within the context of linear programming the convex hull relaxation of a non -convex set ๐’ฎ corresponds to the set of linear constraints characterising the convex hull of ๐’ฎ.