Convexity of the Feasible Region

Establishes that the feasible region of every linear program is convex. Defines convex sets via convex combinations, proves that half-spaces are convex, shows that intersections of convex sets are convex, and concludes that any polyhedral feasible region inherits convexity.

Step 1 of 157%

Tutorial

Convex Sets and Convex Combinations

A set $S \subseteq \mathbb{R}^n$ is convex if for any two points $\mathbf{x}, \mathbf{y} \in S$ and any scalar $\lambda \in [0, 1]$ , the point

\lambda \mathbf{x} + (1 - \lambda) \mathbf{y}

also lies in $S.$ The expression $\lambda \mathbf{x} + (1-\lambda) \mathbf{y}$ is called a convex combination of $\mathbf{x}$ and $\mathbf{y}.$ As $\lambda$ ranges over $[0, 1],$ this convex combination traces out the line segment from $\mathbf{y}$ (at $\lambda = 0$ ) to $\mathbf{x}$ (at $\lambda = 1$ ).

Geometrically, $S$ is convex if the line segment joining any two points of $S$ lies entirely inside $S.$

For example, the closed disk $D = \{(x_1, x_2) : x_1^2 + x_2^2 \leq 1\}$ is convex: every segment between two points of $D$ stays inside $D.$ By contrast, the annulus $A = \{(x_1, x_2) : 1 \leq x_1^2 + x_2^2 \leq 4\}$ is not convex: the points $(1, 0)$ and $(-1, 0)$ both lie in $A,$ but their midpoint $(0, 0)$ does not.