Exercise 2.14

Question

Let $P$ be a bounded polyhedron in $\mathfrak{R}^n$, let $\mathbf{a}$ be a vector in $\mathfrak{R}^n$, and let $b$ be some scalar. We define
$$Q = \left\{\mathbf{x}\in P \mid \mathbf{a}'\mathbf{x} = b\right\}.$$
Show that every extreme point of $Q$ is either an extreme point of $P$ or a convex combination of two adjacent extreme points of $P$.

Elu Thingol · Accepted Answer

By definition, we can write $P$ as $\left\{\mathbf{x} \in \mathfrak{R}^n \mid \mathbf{A}\mathbf{x} = \mathbf{b}ight\}$ for some $m 	imes n$ matrix $A$ and an $m$-dimensional vector $\mathbf{b}$. Since $Q$ is just $P$ with one more additional hyperplane constraint, we can write $Q$ as
$$Q = \left\{\mathbf{x} \in \mathfrak{R}^n \mid \begin{bmatrix}\mathbf{A}\\mathbf{a}\-\mathbf{a}\end{bmatrix}\mathbf{x} = \begin{bmatrix}\mathbf{b}\b\-b\end{bmatrix}ight\}.$$
In other words, the resulting figure $Q$ is another polyhedron inside $P$ and since it always intersects the edges of $P$, its own extreme points will either be the extreme points of $P$ or will strictly lie on the edges of $P$ as demonstrated in the figure below. We formalize this intuition.
\begin{figure}
\includegraphics[width=0.5	extwidth]{bertsimas_linopt_exercise_2-14_1.svg}
\caption{Intersecting a cube with hyperplane results in a polyhedron of lower dimension.}
\end{figure}
\begin{proof}
If $Q$ is empty, the assertion is trivial. Else, let $\mathbf{x}^*$ be an arbitrary extreme point of $Q$. By Definition 2.9, $n$ out of the active constraints in $\mathbf{x}^*$ are active. But $\mathbf{x}^*$ is also an element of $P$; We have two cases.\par
If the newly added condition $\mathbf{a}'\mathbf{x}=b$ is linearly dependent in $\mathbf{x}^*$, then, even after excluding it, $\mathbf{x}^*$ still has $n$ linearly independent active constraints in $P$ as well; thus, $\mathbf{x}^*$ is an extreme point of $P$.\par

If, however, $\mathbf{x}^*\in P$ has $n-1$ linearly independent constraints after excluding the new condition $\mathbf{a}'\mathbf{x}=b$, then all of the vectors $\mathbf{a}_i$, $1 \leq i \leq n-1$, lie in a proper subspace of $\mathfrak{R}^n$ and there exists a nonzero vector $\mathbf{d}\in\mathfrak{R}^n$ such that $\mathbf{a}_i'\mathbf{d} = 0$, for every $1 \leq i \leq n-1$. The scenario is similar to the setting of Theorem 2.6, yet the condition is stronger - $P$ is bounded. We modify the proof a little. Let us consider the line consisting of all points of the form $\mathbf{y} = \mathbf{x}^* \pm \lambda \mathbf{d}$, where $\lambda$ is an arbitrary positive scalar. For $1 \leq i \leq n-1$, we have $\mathbf{a}_i'\mathbf{y} = \mathbf{a}_i'\mathbf{x}^* + \lambda\mathbf{a}_i'\mathbf{d} = \mathbf{a}_i'\mathbf{x}^* = b_i$. Thus, those constraints that are active at $\mathbf{x}^*$ remain active at all points on the line. However, since the polyhedron $P$ is assumed to be bounded, it follows that as we wary $\lambda$ in two directions, some constraints will be eventually violated. At the points where some constraints are about to be violated, a new constraint must become active, and we conclude that there exits some $\lambda^+, \mathbf{a}^+_{n}$ and some $\lambda^-,\mathbf{a}^+_{n}$ such that
$$\mathbf{a}^+_{n}(\mathbf{x}^*+\lambda^+\mathbf{d}) = b_i^+,\qquad
\mathbf{a}^-_{n}(\mathbf{x}^*-\lambda^-\mathbf{d}) = b_i^-.
$$
\begin{figure}
\includegraphics[width=0.4	extwidth]{bertsimas_linopt_exercise_2-14_2.svg}
\caption{Moving from $\mathbf{x}^*$ (green point) to $\mathbf{x}^*+\lambda^+\mathbf{d}$ and $\mathbf{x}^*-\lambda^-\mathbf{d}$ (red points).}
\end{figure}
The obtained columns $\mathbf{a}^+_{n}$ and $\mathbf{a}^-_{n}$ are linearly independent of the vectors $\mathbf{a}_i'$, $1 \leq i \leq n-1$. Indeed, we have $\mathbf{a}'_{n}\mathbf{x}^* 
eq b_n^\pm$ and $\mathbf{a}'_{n}(\mathbf{x}^* + \lambda^\pm ) = b_n^\pm$ (by the definition of $\lambda^+,\lambda^-$). Thus, $\mathbf{a}_j'\mathbf{d}
eq 0$. On the other hand, $\mathbf{a}'_{n}\mathbf{d} = 0$ for every $1 \leq i \leq n-1$ (by definition of $\mathbf{d}$) and therefore, $\mathbf{d}$ is orthogonal to any linear combination of the vectors $\mathbf{a}_i$, $1 \leq i \leq n$. Since $\mathbf{d}$ is not orthogonal to $\mathbf{a}_n^+$ and $\mathbf{a}_n^-$, we conclude that $\mathbf{a}_j$ is not a linear combination of the vectors $\mathbf{a}_i$, $1 \leq i \leq n$. Thus, the points $\mathbf{y}^+ := \mathbf{x}^*+\lambda^+\mathbf{d}$ and $\mathbf{y}^- := \mathbf{x}^*-\lambda^-\mathbf{d}$ are two adjacent vertices of $P$ and we have
$$\mathbf{x}^* = \frac{\lambda^-}{\lambda^-+\lambda^+}\mathbf{y}^+ + \frac{\lambda^+}{\lambda^-+\lambda^+}\mathbf{y}^-.$$
as desired.
\end{proof}

Jannik Friese · Answer

Assume $Q 
eq \emptyset$. Let $A, d$ be a matrix and a vector such that $P=\left\{x \in \mathbb{R}^{n} \mid A x \leq dight\}$. Let $\hat{x}$ be an extreme point of $Q$, equivalently it is a basic feasible solution. Therefore $a^{\prime} \hat{x}=b$ and there are $n$ linearly independent active constraints at $\hat{x}$ (possibly including $a^{\prime} \hat{x}=b$ in these $n$ constraints).\par

If it is possible to find $n$ linearly independent active constraints at $\hat{x}$ all in the collection $A \hat{x} \leq d$, it implies that $\hat{x}$ is an extreme point of $P$ too.\par

Otherwise there are only $n-1$ linearly independent active constraints in the set of constraints $A \hat{x} \leq d$, which means that $\hat{x}$ lies on a face of dimension 1 of $P .$ Let $v \in \mathbb{R}^{n}$ be the direction of the face on which $\hat{x}$ lies. Since $P$ is bounded, there exist scalars $\mu_{1}, \mu_{2}$ such that $\hat{x}+\mu_{1} v$ and $\hat{x}+\mu_{2} v$ are the two vertices (extreme points) of the segment $\hat{x}$ is on. Therefore $\hat{x}$ is a convex combination of these two vectors.

Exercise 2.14

Answers

Comments

Comments

Exercise 2.14

Answers

Comments

Comments

Add answer