1
$\begingroup$

Exercise 2.6 Bertsimas Linear Optimization: Let $A_1,...A_n$ be a collection of vectors in $\mathbb R^m$. Let $$C=\sum_{i=1}^{n}{\lambda_{i} A_{i} \mid \lambda_1,..\lambda_n \geq 0}.$$

Show that any element of $C$ can be expressed in the form: $\sum_{i=1}^{n} \lambda_{i} A_{i}$, with $\lambda_{i} \geq 0$, and with most $m$ of the coefficients $\lambda_{i}$ being nonzero. Hint: consider the polyhedron $$\nabla=\{(\lambda_1,...\lambda_n) \in \mathbb R^n \mid \sum_{i=1}^{n} \lambda_i A_i=y, \lambda_1,...\lambda_n \geq 0\}$$

Attempt at Proof with some thoughts: Clearly the when $n \leq m$ we get the desired result. Now, suppose $n>m$. Consider the polyhedron $$\nabla=\{(\lambda_1,...\lambda_n) \in \mathbb R^n \mid \sum_{i=1}^{n} \lambda_i A_i=y, \lambda_1,...\lambda_n \geq 0\}$$ I want to use that $\nabla$ has a basic feasible solution since it is a polyhedron written in standard form as this will make the proof easier for me. Is this true, however? We haven't made assumption about the rows of $A$ being linearly independent, so I'm not sure if I can state that $\nabla$ has a basic feasible solution. Is it true that $\nabla$ has a basic feasible solution?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.