3.7.64. 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.17 depicts a non-convex set, while partย (B) gives its corresponding convex hull.

Figure 3.7.17. (B)ย Convex hull of a (A)ย non-convex set
ctrs/preface-157-tikz

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 ๐’ฎ.