Skip to main content
Logo image

Linear Optimization A Geometric Inquiry Course

Tien Chih

Section 1.3 Polyhedral Convextiy

In this section, we establish the fundamental geometric notions which underlie our work.
🔗

Activity 1.3.1.

In \(\mathbb{R}^3\text{,}\) describe geometrically what the following represent.
🔗
🔗

Activity 1.3.2.

Let \(\p =(-3,1), \q =(2,-5)\text{.}\) Let \(\x =t\cdot \p +(1-t)\cdot \q\) for some \(0\leq t\leq 1\text{.}\)
🔗

(a)

What is \(\x \) when \(t=0.2\text{?}\)
🔗
🔗

(b)

What is \(\x\) when \(t=0.5\text{?}\)
🔗
🔗

(c)

What is \(\x\) when \(t=0\text{?}\)
🔗
🔗

(d)

What is \(\x\) when \(t=1\text{?}\)
🔗
🔗

(e)

Describe the set of points \(\{t\cdot \p+(1-t)\cdot \q : t\in [0,1]\}\text{.}\)
🔗
🔗

(f)

Let \(\p =(2,1,0), \q=(0, -3, 1)\text{.}\) Describe the set of points \(\{t\cdot \p+(1-t)\cdot \q : t\in [0,1]\}\text{.}\)
🔗
🔗
🔗

Definition 1.3.3.

Given \(\p, \q\in \mathbb{R}^m\text{,}\) we call the set \(\{t\cdot \p+(1-t)\cdot \q : t\in [0,1]\}\) the line segment between \(\p\) and \(\q\text{.}\)
🔗
🔗

Definition 1.3.4.

Let \(S\subseteq \mathbf{R}^m\text{,}\) we say that \(S\) is convex if given any \(\p, \q\in S\text{,}\) \(S\) also contains the line segment between \(\p, \q\text{.}\)
🔗
🔗

Activity 1.3.5.

For each of the following subsets of \(\mathbb{R}^2\text{,}\) sketch the region, decide if it is convex or not.
🔗

(a)

\(\{(x,y): 2x+3y\leq 4\}\text{.}\)
🔗
🔗

(b)

\(\{(x,y): y=2\text{ and }x< 4 \}\text{.}\)
🔗
🔗

(c)

\(\{(r,\theta): 0\leq r \leq 1, \theta\in [0, \pi/4]\}\) (in polar coordinates).
🔗
🔗

(d)

\(\{(r,\theta): 0\leq r \leq 1, \theta\in [\pi/4, 2\pi]\}\) (in polar coordinates).
🔗
🔗
🔗

Activity 1.3.6.

Let \(S\subseteq \mathbb{R}^m\) be defined by \(S:=\{\mathbf{x}\in \mathbb{R}^m: a_1x_1+a_2x_2+\cdots a_mx_m\leq b\}\) for some \(a_i, b\in \mathbb{R}\) (i.e. \(S\) is a half-space of \(\mathbb{R}^m\)).
🔗

(a)

Let \(f(\mathbf{x}):\mathbb{R}^m\to \mathbb{R}, (x_1, x_2, \ldots, x_m)\mapsto a_1x_1+a_2x_2+\cdots a_mx_m\text{.}\) Explain why \(f(c\mathbf{x})=cf(\mathbf{x})\) for any \(c\in \mathbb{R}\text{.}\)
🔗
🔗

(b)

Show that for any \(\mathbf{x}=(x_1, x_2, \ldots, x_n), \mathbf{y} = (y_1, y_2, \ldots, y_n)\text{,}\) that \(f(\mathbf{x}+\mathbf{y}) = f(\mathbf{x})+f(\mathbf{y})\text{.}\)
🔗
🔗

(c)

Let \(\mathbf{x}, \mathbf{y}\in S\text{,}\) that is, there are \(k_x, k_y\) such that \(f(\mathbf{x})=a_1x_1+a_2x_2+\cdots a_nx_n = k_x, f(\mathbf{y})= a_1y_1+a_2y_2+\cdots a_ny_n =k_y\) and \(k_x, k_y\leq b\text{.}\) Show that \(f(t\mathbf{x}+(1-t)\mathbf{y})\leq b\) for \(t\in [0,1]\text{.}\)
🔗
🔗

(d)

Conclude that \(S\) is convex.
🔗
🔗
🔗

Activity 1.3.7.

Let \(S_1, S_2\) be convex sets.
🔗

(a)

Show that \(S_1\cap S_2\) is convex.
🔗
Hint.
Let \(P, Q\in S_1\cap S_2\text{.}\) Why is the line segment between them contained in \(S_1\text{?}\) \(S_2\text{?}\)
🔗
🔗
🔗

(b)

Sketch an induction argument to show that if \(S_i\) is convex, \(\bigcap_{i=1}^n S_i\) is convex.
🔗
🔗

(c)

Prove or find a counterexample to the following statement: If \(S_1, S_2\) are convex sets, then \(S_1\cup S_2\) is convex.
🔗
🔗
🔗

Activity 1.3.8.

Prove that the feasible region of a canonical linear programming problem is convex.
🔗
🔗

Definition 1.3.9.

A convex set \(S\) that is equal to a finite intersection of half-spaces (defined by either strict or nonstrict inequalities) is polyhedral convex.
🔗
🔗

Definition 1.3.12.

Given \(\mathbf{x}\in \mathbb{R}^n\) we define the norm of \(\mathbf{x}\) to be
\begin{equation*} \|\mathbf{x}\|=\sqrt{x_1^2+x_2^2+\cdots x_n^2}. \end{equation*}
🔗
🔗

Definition 1.3.13.

Given \(\mathbf{x}\in \mathbb{R}^n\) we define the closed ball of radius \(r\) centered at \(\mathbf{x}\) to be
\begin{equation*} \bar{B}(\mathbf{x}, r):=\{\mathbf{y}:\|\mathbf{x}-\mathbf{y}\|\leq r\}. \end{equation*}
🔗
The open ball centered at \(\mathbf{x}\) with radius \(r\) is similarly defined. What do you think it is?
🔗
🔗

Activity 1.3.14.

Describe \(\bar{B}(\mathbf{0}, r)\) for \(\mathbb{R}, \mathbb{R}^2, \mathbb{R}^3\text{.}\)
🔗
🔗

Definition 1.3.15.

A set \(S\) is bounded if there is \(r\geq 0\) such that \(S\subseteq \bar{B}(\mathbf{0}, r)\text{.}\)
🔗
🔗

Activity 1.3.17.

Let \(S\subseteq \mathbb{R}^2\) be the feasible region of of a canonical maximization linear programming problem, let \(f(x_1, x_2) = 2x_2+3x_2\) be the objective function.
🔗

(a)

Consider the point \((1,1)\text{.}\) Which direction would increase the value of \(f\) the most? The least? Keep \(f\) the same?
🔗
(Recall the properties of the dot product.)
🔗
🔗

(b)

Let \(\mathbf{x}\in S\) such that there is a \(r > 0\) so that \(B(\mathbf{x}, r)\subseteq S\text{.}\) Explain why \(\mathbf{x}\) cannot be a maximizer of \(f\text{.}\)
🔗
🔗

(c)

On the other hand, suppose \(\mathbf{x}^*\in S\) is a maximizer of \(f\text{,}\) what must be true about \(\mathbf{x}^*\text{?}\)
🔗
🔗

(d)

Consider the canonical maximization linear programming problem:
🔗
Maximize \(f(x,y)=3x+2y\) subject to:
\begin{align*} x+y\amp \leq 8\\ 2x+y\amp \leq 10\\ x, y\amp \geq 0. \end{align*}
🔗
How do the statements you’ve made above apply here? Where is \(f\) maximized? Is it consistent with what you said before?
🔗
🔗
🔗

Definition 1.3.18.

Let \(S\subseteq \mathbb{R}^m\) be a convex set. We say \(\mathbf{e}\in S\) is an extreme point of \(S\) if there are no \(\mathbf{x}, \mathbf{y}\in S\) so that \(\mathbf{e}\in \{t\cdot \mathbf{x}+(1-t)\cdot \mathbf{y} : t\in (0,1)\}\text{.}\)
🔗
In other words, \(\mathbf{e}\) does not lie on any nontrivial line segment contained in \(S\text{.}\)
🔗
🔗

Activity 1.3.19.

For each of the following convex sets, find its extreme points (if any).
🔗

(b)

\(\{(x,y):\|(x,y)\|\leq 1\}\subseteq \mathbb{R}^2\text{.}\)
🔗
🔗

(c)

\(\{(x,y):y\geq 0\}\subseteq \mathbb{R}^2\text{.}\)
🔗
🔗
🔗
We present the following theorems without proof. At least one of these should seem familiar from calculus.
🔗
(We will assume without proof that linear functions \(f:\mathbb{R}^m\to \mathbb{R}\) are continuous, and that the feasible region of a linear optimization problem is always closed.)
🔗

Activity 1.3.23.

(a)

Let \(f(x,y)=x+y\) be the objective function for a canonical maximization problem, subject to:
\begin{align*} x+4y \amp\leq 26 \\ 2x+2y \amp\leq 16 \\ 4x+y \amp\leq 24 \\ x, y \amp\geq 0. \end{align*}
Find a maximal solution that is not a corner point. Why doesn’t this contradict Theorem 1.3.21?
🔗
🔗

(b)

Let \(\mathbf{x}_1, \mathbf{x}_2 \in S\) be optimal solutions of a canonical linear programming problem, giving optimal solution \(f(\mathbf{x}_1) = f^* =f(\mathbf{x}_2)\text{.}\) Show that for any \(t\in [0,1]\text{,}\) \(f(t\mathbf{x}_1+(1-t)\mathbf{x}_2)=f^*\) and that \(t\mathbf{x}_1+(1-t)\mathbf{x}_2\in S\text{.}\)
🔗
🔗

(c)

Let \(f(x,y)=x\) be the objective function for a canonical maximization problem. Find a set of constraints so that the feasible region is unbounded but there is a maximal solution. Why doesn’t this contradict Theorem 1.3.22?
🔗
🔗
🔗

Activity 1.3.24.

So, we see that the hunt for optimal solutions boils down to a hunt for extreme points.
🔗

(a)

In \(\mathbb{R}^2\text{,}\) how many lines are needed to intersect so their intersection is a unique point?
🔗
🔗

(b)

In \(\mathbb{R}^3\text{,}\) how many planes are needed to intersect so their intersection is a unique point?
🔗
🔗

(c)

In \(\mathbb{R}^m\text{,}\) how many \(m-1\) dimensional hyperplanes are needed to intersect so their intersection is a unique point?
🔗
🔗

(d)

Suppose a canonical linear programming problem in \(\mathbb{R}^m\) is bounded by the usual \(m\) hyperplanes corresponding to \(x_i\geq 0\) as well as \(k\) additional hyperplanes. How many potential points of intersection could there be?
🔗
  1. \(\displaystyle n\)
    🔗
    🔗
  2. \(\displaystyle {m\choose k}\)
    🔗
    🔗
  3. \(\displaystyle {m+k\choose k}\)
    🔗
    🔗
  4. \(\displaystyle {k\choose m}\)
    🔗
    🔗
  5. \(\displaystyle {m+k\choose n}\)
    🔗
    🔗
🔗

(e)

So for a canonical linear programming problem in \(\mathbb{R}^{10}\) bounded by an additional 15 hyperplanes, how many potential extreme points are there?
🔗
🔗
🔗
🔗
PrevTopNext