Prove that a set \(S\subseteq \mathbb{R}^n\) is convex if and only if \(S=\conv(S)\text{.}\)
Prove that every polyhedron is convex.
Prove that if \(\mathcal{C}\) is a collection of convex subsets of \(\mathbb{R}^n\text{,}\) then \(\bigcap_{S\in\mathcal{C}}S\) is convex.
-
Say that a set \(S\subseteq\mathbb{R}^n\) is midpoint convex if for every pair \(x,y\in S\text{,}\) it holds that \(\frac{1}{2}(x+y)\in S\text{.}\)
Prove that if \(S\subseteq\mathbb{R}^n\) is closed and midpoint convex, then \(S\) is convex.
Provide an example of a set \(S\subseteq\mathbb{R}\) that is midpoint convex but not convex.
Let \(z\in \mathbb{R}^n\) be fixed. Define \(S\subseteq\mathbb{R}^{n+1}\) by
\begin{equation*}
S=\left\{(y,r): y\in\mathbb{R}^n, r\in\mathbb{R},\text{ and }\|z-y\|_2\leq r\right\}.
\end{equation*}
Prove that the set \(S\) is convex.
A
convex program is a generalization of a linear program in which a convex objective function of real variables is minimized over a convex set. Let
\(z_1,\dots,z_k\in\mathbb{R}^n\) and write down a convex program for finding the radius of the smallest closed ball in
\(\mathbb{R}^n\) which contains all of the points
\(z_1,\dots,z_k\text{.}\) Hint: Exercise 4 may be helpful.
-
A convex cone is a set \(C\subseteq\mathbb{R}^n\) with the property that for all \(x,y\in C\) and \(\lambda,\mu\geq0\text{,}\) the point \(\lambda x+\mu y\) is in \(C\text{.}\) A linear halfspace is a set of the form \(\{x\in\mathbb{R}^n: c^Tx\leq 0\}\) for some \(c\in \mathbb{R}^n\text{.}\) For a set \(S\subseteq\mathbb{R}^n\text{,}\) define
\begin{equation*}
\cone(S):=\left\{\sum_{i=1}^n\lambda_ix_i: x_1,\dots,x_n\in S, \lambda_1\dots,\lambda_n\geq0\right\}.
\end{equation*}
Prove that if \(S\) is finite and \(z\in \cone(S)\text{,}\) then there exists a set \(T\subseteq S\) such that the vectors in \(T\) are linearly independent and \(z\in \cone(T)\text{.}\)
Prove that if \(S\subseteq\mathbb{R}^n\) is finite and \(z\in \conv(S)\text{,}\) then there exists a set \(T\subseteq S\) of cardinality at most \(n+1\) such that \(z\in \conv(T)\text{.}\)
-
Given a set \(X\subseteq\mathbb{R}^n\text{,}\) define
\begin{equation*}
X^*:=\{y\in\mathbb{R}^n: y^Tx\leq 1\text{ for all }x\in X\}
\end{equation*}
Prove that if \(C\) is a convex cone, then \(C^*\) is a closed convex cone.
Prove that if \(C\) is a closed convex cone, then \((C^*)^*=C\text{.}\)
Suppose that the polytope \(P=\{x: Ax\leq b\}\) is non-empty and let \(C\) be the cone \(\{x: Ax\leq 0\}\text{.}\) Prove that the the value of the linear program
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b
\end{align*}
is finite if and only if \(c\in C^*\text{.}\)
Let \(A\) be an \(m\times n\) real matrix, let \(b\in\mathbb{R}^m\text{.}\) Prove that the polyhedron \(P=\{x\in\mathbb{R}^n: Ax\leq b\}\) has at most \(2^m\) vertices.
Let \(A\) be an \(m\times n\) rational matrix and let \(b\) be a rational vector of length \(m\text{.}\) Prove that every vertex \(z\) of the polyhedron \(P=\{x\in\mathbb{R}^n: Ax\leq b\}\) is an element of \(\mathbb{Q}^n\text{.}\)
Consider two polyhedra \(P=\left\{x\in\mathbb{R}^n: Ax\leq b, Cx\leq d\right\}\) and \(Q=\left\{x\in\mathbb{R}^n: Ax\leq b, Cx=d\right\}\text{.}\) Prove that every vertex of \(Q\) is also a vertex of \(P\text{.}\)
-
An inequality \(c^Tx\leq d\) is said to be valid for a polyhedron \(P\) if every element of \(P\) satisfies the inequality. A face of a polyhedron \(P=\{x:Ax\leq b\}\) is a set of the form \(F=\{x: Ax\leq b\text{ and }c^Tx= d\}\) where \(c^Tx\leq d\) is a valid inequality for \(P\text{.}\)
Prove that a point \(z\) in a polyhedron \(P\) is a vertex of \(P\) if and only if \(\{z\}\) is a face of \(P\text{.}\)
Two distinct vertices
\(w,z\) of a polyhedron
\(P\) are
adjacent if there is a unique way to express their midpoint
\(\frac{1}{2}(w+z)\) as a convex combination of vertices of
\(P\text{.}\) State and prove a version of
Lemma 2.1.10 for classifying pairs of adjacent vertices of a polyhedron.
Prove that two distinct vertices \(w,z\) of a polyhedron \(P\) are adjacent if and only if \(\conv(\{w,z\})\) is a face of \(P\text{.}\)
Come up with an example of a linear program maximizing a function \(c^Tx\) subject to \(Ax\leq b\) where the value of the linear program is equal to \(5\) but there does not exist a vertex of the polyhedron \(\{x: Ax\leq b\}\) which achieves an objective value of \(5\text{.}\)
-
You own a clothing company that is able to produce \(n\) different types of clothing (e.g. shirts, trousers, shoes, etc). Whenever you sell an item of clothing of the \(j\)th type, you get a profit of \(p_j\text{.}\) Your company produces these items of clothing using \(m\) different types of material (e.g. cotton, polyester, leather, etc). The number of square centimeters of material of the \(i\)th type that you have in stock is given by \(b_i\text{.}\) Also, the number of square centimeters of material of the \(i\)th type that is required to produce an item of the \(j\)th type is given by \(a_{i,j}\text{.}\)
Write down a linear program for maximizing the profit that your company can make using the material that you have in stock. For simplicity, assume that it is possible to make a fractional number of items of clothing.
Find the dual of the linear program and provide a natural interpretation of it in words.
Convert the following linear program to Standard Inequality Form and take its dual (but do not solve it):
\begin{align*}
\text{max } \amp \amp 3x_1-x_2+x_3\\
\text{subject to } \amp \amp x_1+x_2-x_3 =43\\
\amp \amp 4x_1+x_2\leq 88\\
\amp \amp x_1+x_3\leq 100\\
\amp \amp 10x_2-x_3\geq 107.
\end{align*}
Prove that the Theorem of the Alternative implies Farkas’ Lemma.
Using Farkas’ Lemma, prove that for every \(A\in\mathbb{R}^{m\times n}\) and \(b\in\mathbb{R}^m\text{,}\) exactly one of the following is true
There exists \(x\in\mathbb{R}^n\) with \(Ax\leq b\) and \(x\geq0\text{.}\)
There exists \(y\in\mathbb{R}^m\) with \(A^Ty\geq 0\text{,}\) \(y\geq0\) and \(b^Ty <0\text{.}\)
Show that, for linear programs, the dual of the dual is the primal. More specifically, starting with a primal LP in Standard Inequality Form, take its dual, convert it into an equivalent linear program in Standard Inequality Form, take the dual again, and show that it is equivalent to the primal.
Consider a linear program in Standard Equality Form
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax= b\\
\amp \amp x\geq 0.
\end{align*}
Convert this LP to an equivalent LP in Standard Inequality Form, find its dual, and then simplify it to obtain a dual for the original linear program which has precisely \(m\) variables and \(n\) constraints.
Prove that if a primal LP in Standard Inequality Form is feasible and its dual is infeasible, then the value of the primal is
\(\infty\text{.}\) Hint: Use an idea from
Subsection 2.1.1 to add a variable to the dual to get a new minimization LP that is feasible and has positive value. Take the dual of this LP and think about why it gives you what you want.
Careful: It is important to use the assumption that the primal is feasible. If the primal is infeasible, then the value of the primal is
\(\max\emptyset = -\infty\text{.}\)
Come up with an example of a primal LP in Standard Inequality Form which is infeasible such that its dual is also infeasible. Explain how this prevents us from generalizing the hypotheses of the Strong Duality Theorem to all linear programs.
Let \(c,d\in\mathbb{R}^n\text{.}\) Show that the maximum of \(\max\{c^Tx,d^Tx\}\) over a polyhedron \(\left\{x\in\mathbb{R}^n: Ax\leq b\right\}\) can be found by solving two linear programs and taking the larger of the two values.
Let \(c,d\in\mathbb{R}^n\text{.}\) Show that the minimum of \(\max\{c^Tx,d^Tx\}\) over a polyhedron \(\left\{x\in\mathbb{R}^n: Ax\leq b\right\}\) can be found by solving a single linear program. Hint: Add some new variables and/or constraints.
Let \(P=\{x: Ax\leq b\}\) be a polyhedron in \(\mathbb{R}^n\) where \(b\in\mathbb{R}^m\text{.}\) Write down a linear program which computes the radius of the largest sphere that fits inside of \(P\text{.}\) Hint: Look up or derive a formula for the distance from a point \(z\in\mathbb{R}^n\) to an affine hyperplane \(a^Tx=b\) where \(a,x\in\mathbb{R}^n\) and \(b\in \mathbb{R}\text{.}\)
-
A collection \(\mathcal{A}\) of sets is an antichain if there does not exist \(A,B\in\mathcal{A}\) such that \(A\subsetneq B\text{.}\) Our goal is to prove the following theorem of Kleitman and Milner.
Theorem (Kleitman and Milner). Let \(n\) and \(k\) be integers such that \(k\leq n/2\text{.}\) If \(\mathcal{A}\) is a collection of subsets of \(\{1,\dots,n\}\) such that \(|\mathcal{A}|\geq \binom{n}{k}\text{,}\) then the average cardinality of a set in \(\mathcal{A}\) is at least \(k\text{.}\)
-
We will prove the theorem using linear programming duality. First, we derive an important constraint called the LYM Inequality
LYM Inequality (Lubell, Yamamoto and Meshalkin). If \(\mathcal{A}\) is a collection of subsets of \(\{1,\dots,n\}\text{,}\) then
\begin{equation*}
\sum_{k=0}^n\frac{|\{A\in\mathcal{A}: |A|=k\}|}{\binom{n}{k}}\leq 1.
\end{equation*}
Prove the LYM Inequality. Hint: Consider a permutation \(\pi\) of \(\{1,\dots,n\}\text{.}\) A prefix of a permutation is a set of elements that appear at the start of the permutation. How many prefixes of \(\pi\) can be in \(\mathcal{A}\text{?}\) For a given set \(A\subseteq\{1,\dots,n\}\text{,}\) how many permutations is \(A\) a prefix of?
Write down a linear program with variables \(x_0,\dots,x_n\) for computing the minimum of the average cardinality of a set in an antichain \(\mathcal{A}\) with \(|\mathcal{A}|\geq\binom{n}{k}\text{.}\) The variable \(x_k\) should represent the quantity \(|\{A\in\mathcal{A}: |A|=k\}|\text{.}\) Your LP should have two constraints: one for the inequality \(|\mathcal{A}|\geq\binom{n}{k}\) and one corresponding to the LYM Inequality.
Take the dual of the linear program that you came up with in the previous part of the exercise. Note that it may be helpful to first convert it into Standard Inequality Form.
Use the Weak Duality Theorem to complete the proof of the theorem. That is, find a feasible point for the dual (and prove that it is feasible) achieving an appropriate value of the dual objective function.
Consider a primal linear program \(\max\{c^Tx: Ax\leq b, x\geq0\}\) in Standard Inequality Form, suppose that \(x\) is a feasible point for it and that \(y\) is a feasible point for the dual. Prove that if there exists a row \(a_j\) of \(A\) such that \(a_jx < b_j\)and \(y_j>0\text{,}\) then \(c^Tx < b^Ty\text{.}\) Hint: Follow the proof of the Weak Duality Theorem.
-
Use the Strong Duality Theorem for linear programming to prove the following theorem.
Complementary Slackness Theorem: Consider a primal linear program \(\max\{c^Tx: Ax\leq b, x\geq0\}\) in Standard Inequality Form, suppose that \(x\) is a feasible point for it and that \(y\) is a feasible point for the dual. Then \(x\) is optimal for the primal and \(y\) is optimal for the dual if and only if the following two conditions hold:
For each \(1\leq j\leq m\text{,}\) either \(y_j=0\) or \(a_jx=b_i\) where \(a_j\) is the \(j\)th row of \(A\text{.}\)
For each \(1\leq i\leq n\text{,}\) either \(x_i=0\) or \(a^T_iy=c_i\) where \(a^T_i\) is the \(i\)th row of \(A^T\text{.}\)
-
Our goal is to reduce the Shortest Path Problem (
Problem 1.3.1) for conservative length functions to solving a linear program. Let
\(D\) be a digraph,
\(\ell:A(D)\to\mathbb{R}\) be a length function and
\(s\) and
\(t\) be two vertices of
\(D\) such that there exists at least one path in
\(D\) from
\(s\) to
\(t\text{.}\) Let
\(x=(x_{uv}: uv\in A(D))\) be a vector of real variables indexed by arcs of
\(D\text{.}\) Consider the following linear program:
\begin{align*}
\text{min } \amp \amp \sum_{uv\in A(D)} \ell(uv)x_{uv}\\
\text{subject to } \amp \amp \sum_{u\in N^+(s)}x_{su}=1,\\
\amp \amp \sum_{u\in N^-(t)}x_{ut}=1,\\
\amp \amp \sum_{u\in N^-(s)}x_{us}=0,\\
\amp \amp \sum_{u\in N^+(t)}x_{tu}=0,\\
\amp \amp \sum_{u\in N^-(v)}x_{uv} - \sum_{u\in N^+(v)}x_{vu}=0\amp \text{ for all } v\in V(D)\setminus\{s,t\},\\
\amp \amp x\geq0
\end{align*}
Prove that there exists an instance of the Shortest Path Problem in which the length function is not conservative (see
Definition 1.3.4) and the value of this linear program is
\(-\infty\text{.}\)
Prove that, if the length function is conservative, then the value of the above linear program is precisely equal to the minimum length of a path from \(s\) to \(t\text{.}\) Hint: Be careful; the variables of the LP in the optimal feasible point may not be integers. How can you deal with that?
Take the dual of the linear program in
Exercise 26. (It may help to solve
Exercise 19 first). What do the variables in the dual LP represent?
