Activity 1.3.1.
In \(\mathbb{R}^3\text{,}\) describe geometrically what the following represent.
(a)
\(2x-y+3z=4\)
(b)
\(2x-y+3z=0\)
(c)
\(2x-y+3z=-4\)
(d)
\(2x-y+3z\leq 3\)
(e)
\(2x-y+3z\geq -1\)
Section 1.3 Polyhedral Convextiy
In this section, we establish the fundamental geometric notions which underlie our work.
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\) if \(t=0.2\text{?}\)
(b)
What is \(X\) if \(t=0.5\text{?}\)
(c)
What is \(X\) if \(t=0\text{?}\)
(d)
What is \(X\) if \(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 \(\mathbf{P}, \mathbf{Q}\in \mathbb{R}^n\text{,}\) we call the set \(\{t\cdot \mathbf{P}+(1-t)\cdot \mathbf{Q} : t\in [0,1]\}\) the line segment between \(\mathbf{P}\) and \(\mathbf{Q}\text{.}\)
Definition 1.3.4.
Let \(S\subseteq \mathbf{R}^n\text{,}\) we say that \(S\) is convex if given any \(\mathbf{P}, \mathbf{Q}\in S\text{,}\) \(S\) also contains the line segment between \(\mathbf{P}, \mathbf{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).
(e)
\(\mathbb{R}^2\text{.}\)
(f)
\(\emptyset\text{.}\)
Activity 1.3.6.
Let \(S\subseteq \mathbb{R}^n\) be defined by \(S:=\{\mathbf{x}\in \mathbb{R}^n: a_1x_1+a_2x_2+\cdots a_nx_n\leq b\}\) for some \(a_i, b\in \mathbb{R}\) (ie \(S\) is a half-space of \(\mathbb{R}^n\)).
(a)
Let \(f(\mathbf{x}):\mathbb{R}^n\to \mathbb{R}, (x_1, x_2, \ldots, x_n)\mapsto a_1x_1+a_2x_2+\cdots a_nx_n\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 non-strict inequalities) is polyhedral convex.
Example 1.3.10.
The feasible region for Activity 1.2.1 is:
Example 1.3.11.
The feasible region for Activity 1.2.2 is:
Definition 1.3.12.
Given \(\mathbf{x}\) in 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 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 a \(r\geq 0\) such that \(S\subseteq \bar{B}(\mathbf{0}, r)\text{.}\)
Activity 1.3.16.
Which of the problems described in Activity 1.2.1, Activity 1.2.2 have bounded feasible regions?
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 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:
Maximzie \(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}^n\) 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 non-trivial line segment contained in \(S\text{.}\)
Activity 1.3.19.
For each of the following convex sets, find it’s extreme points (if any).
(a)
The feasible region of the problem in Activity 1.3.17.
(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 the moment). At least one of these should seem familiar from calculus.
Theorem 1.3.20. Extreme Value Theorem.
If \(S\subseteq \mathbb{R}^n\) is a closed and bounded region, and \(f:S\to \mathbb{R}\) is a continuous function. Then there are \(\x_1, \x_2\in S\) such that \(f(\x_1)\geq f(\x)\) and \(f(\x_2)\leq f(\x)\) for every \(\x\in S\text{.}\)
(We will assume without proof that linear functions \(f:\mathbb{R}^n\to \mathbb{R}\) are continuous, and that the feasible region of a linear optimization problem is always closed.)
Theorem 1.3.21.
If \(S\) is the feasible region of a canonical problem and is bounded, then \(S\) contains an optimal solution which is an extreme point of \(S\text{.}\)
Theorem 1.3.22.
If \(S\) is the feasible region of a canonical problem and is unbounded:
- If the problem is a maximization problem and if there is a \(M\) so that \(f(s)\leq M\) for all \(s\in S\text{,}\) then \(S\) contains an optimal solution which is an extreme point of \(S\text{.}\)
- If the problem is a minimization problem and if there is a \(M\) so that \(g(s)\geq M\) for all \(s\in S\text{,}\) then \(S\) contains an optimal solution which is an extreme point of \(S\text{.}\)
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\) How many lines are needed to intersect so their intersection is a unique point?
(b)
In \(\mathbb{R}^3\) How many planes are needed to intersect so their intersection is a unique point?
(c)
In \(\mathbb{R}^n\) How many \(n-1\) dimensional hyperplanes are needed to intersect so their intersection is a unique point?
(d)
Suppose a canonical linear programming problem in \(\mathbb{R}^n\) is bounded by the usual \(n\) hyperplanes corresponding to \(x_i\geq 0\) as well as \(k\) additional hyperplanes. How many potential points of intersection could there be?
- \(\displaystyle n.\)
- \(\displaystyle {n\choose k}.\)
- \(\displaystyle {n+k\choose k}.\)
- \(\displaystyle {k\choose n}.\)
- \(\displaystyle {n+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?
