Exercise 2.6 (Carathéodory's theorem)

Question

Let $\mathbf{A}_1,\ldots,\mathbf{A}_n$ be a collection of vectors in $\mathfrak{R}^m$.
ewline
\begin{enumerate}[label=(\alph*)]
\item Let 
$$C = \left\{\sum_{i=1}^{n}\lambda_i\mathbf{A}_i \big| \lambda_1,\ldots,\lambda_n \geq 0 ight\}.$$
Show that any element of $C$ can be expressed in the form $\sum_{i=1}^{n} \lambda_i \mathbf{A}_i$, with $\lambda_i \geq 0$ and with at most $m$ of the coefficients $\lambda_i$ being nonzero.

\item Let $P$ be the convex hull of the vectors $\mathbf{A}_i$:
$$P = \left\{\sum_{i=1}^{n}\lambda_i\mathbf{A}_i \left| \sum_{i=1}^{n} \lambda_i = 1, \ \lambda_1,\ldots,\lambda_n \geq 0 ight.ight\}.$$
Show that any element of $P$ can be expressed in the form $\sum_{i=1}^{n}\lambda_i\mathbf{A}_i$, where $\sum_{i=1}^{n} \lambda_i = 1$ and $\lambda_i \geq 0$ for all $i$, with at most $m+1$ of the coefficients $\lambda_i$ being nonzero. \end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item Following the theorem assertion, let $\mathbf{y}$ be an arbitrary element of $C$. Consider the set of all other $\lambda'_1,\ldots,\lambda_n'$ under which the linear combination of $\mathbf{A}_1,\ldots,\mathbf{A}_n$ also equals to $\mathbf{y}$:
$$\Lambda_{\mathbf{y}} := \left\{ \begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} \in \mathfrak{R}^n\ \left|\ \mathbf{A}\begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} = \mathbf{y},\, \begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} \geq 0 ight.ight\}.$$
Obviously, this is a polyhedron in the standard form, and it is nonempty as it at least contains $\mathbf{y}$. By Corollary 2.2, every nonempty polyhedron in standard form has at least one basic feasible solution $(\lambda^{*}_1,\ldots,\lambda^{*}_m)$. By Theorem 2.4, we can find columns $\mathbf{A}_{B(1)},\ldots,\mathbf{A}_{B(m)}$ that are linearly independent; in other words, using elementary linear algebra, we conclude that there exists a collection $\lambda^{*}_1,\ldots,\lambda^{*}_m \in \mathfrak{R}$ such that
$$\lambda^{*}_1 \mathbf{A}_{B(1)} + \ldots + \lambda^{*}_m\mathbf{A}_{B(m)} = \lambda_1\mathbf{A}_{1} + \ldots + \lambda_n\mathbf{A}_{n} \in \mathfrak{R}^m.$$

\item Just as in the previous part, any $\mathbf{y} \in P$ is related to a polyhedron of coefficients in $\mathfrak{R}^n$ defined by
$$\Lambda_{\mathbf{y}} := \left\{ \begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} \in \mathfrak{R}^n\ \left|\ \begin{bmatrix} \mathbf{A} \ \mathbf{1}_{1 	imes n} \end{bmatrix} \begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} = \begin{bmatrix} \mathbf{y} \ 1 \end{bmatrix},\, \begin{bmatrix} \lambda_1 \ \vdots \ \lambda_n \end{bmatrix} \geq 0 ight.ight\}.$$
Again, this is a nonempty standard polyhedron which is why it must have an extreme point (Corollary 2.2). This time, however, we have got $m+1$ rows; by Theorem 2.4 we find $m+1$ linearly independent columns $\mathbf{A}_{B(1)},\ldots,\mathbf{A}_{B(m+1)}$, which means that $\mathbf{y}$ can be represented using only $m+1$ associated coefficients $\lambda^{*}_1,\ldots,\lambda^{*}_{m},\lambda^{*}_{m+1}$.
\end{enumerate}

Prakash Anand · Answer

(a) If $n \leq m$, then the result is trivial. Now suppose $n>m$. Let $y \in C$. Consider the polyhedron $$\Lambda=\left\{\left(\lambda_{1}, \ldots, \lambda_{n}\right) \in \mathbb{R}^{n} \mid \sum_{i=1}^{n} \lambda_{i} A_{i}=y, \quad \lambda_{1}, \ldots, \lambda_{n} \geq 0\right\}.$$ This is a polyhedron in standard form, so by theorem there exists a basic feasible solution $\lambda^{*}=\left(\lambda_{1}^{*}, \ldots, \lambda_{n}^{*}\right)$. Note that we can have at most $m$ linearly independent vectors out of the family $A_{i}$. Thus, a basic feasible solution has at least $n-m$ zero components, which means there are at most $m$ non-zero components in $\lambda^{*}$. Thus, $\sum_{i=1}^{n} \lambda_{i}^{*} A_{i}$ is an expression of $y$ with at most $m$ of the coefficients being non-zero.\par

(b) If $n \leq m+1$, then the result is trivial. Now suppose $n>m+1$. Let $y \in P$. Consider the polyhedron
$$\Lambda=\left\{\left(\lambda_{1}, \ldots, \lambda_{n}\right) \in \mathbb{R}^{n} \mid \sum_{i=1}^{n} \lambda_{i} A_{i}=y, \sum_{i=1}^{n} \lambda_{i}=1, \quad \lambda_{1}, \ldots, \lambda_{n} \geq 0\right\}.$$
This is a polyhedron in standard form, so by theorem there exists a basic feasible solution $\lambda^{*}=\left(\lambda_{1}^{*}, \ldots, \lambda_{n}^{*}\right)$. Note that there are $m+1$ equality constraints in the polyhedron, so we can have at most $m+1$ linearly independent equality constraints. Thus, the basic feasible solution have at least $n-(m+1)$ zero components, which means $\lambda^{*}$ has at most $m+1$ non-zero components. Thus, $\sum_{i=1}^{n} \lambda_{i}^{*} A_{i}$ is an expression of $y$ with at most $m+1$ of the coefficients being non-zero.

Exercise 2.6 (Carathéodory's theorem)

Answers

Comments

Comments

Exercise 2.6 (Carathéodory's theorem)

Answers

Comments

Comments

Add answer