Determining convex set

Question

$S=\left\{x \in R^{n}: x=A^{\top}y , y \in R^{m}, y \geqslant 0\right\}$ where $A \in R^{m \times n}$

Solution-

Takng two points in $S ;\left(x_{1}, y_{1}\right) \in S,\left(x, y_{2}\right) \in S$

To prove set $s$ is convex, we prove that any point $z=\lambda x+(1-\lambda x), \lambda \in[0,1]$

$$ \begin{array}{l} \ \ \\ x_{1}=A^{\top} y_{1} \quad(1) \\ x_{2}=A^{\top} y_{2} \quad(2) \\ \qquad \end{array} $$ Multiplying (1) with $\lambda$ and (2) with $(1-\lambda)$ $$ \begin{array}{l} \lambda x_{1}=A^{\top} y_{1} \lambda \\ (1-\lambda) x_{2}=A^{\top} y_2 (1-\lambda) \end{array} $$ Adding the above - $$ \lambda x_{1}+(1-\lambda) x_{2}=A^{\top}\left(\lambda y_{1}+(1-\lambda) y_{2}\right) $$

I can't seen to further simplify the equation, is it fair to say the set isn't convex?

Answer 1

I am not quite sure what the "$y\geq0$" in your definition of $S$ refers to. But we know that $\mathbb{R}^m$ is convex, so you know that $\lambda y_1+(1-\lambda)y_2\in\mathbb{R}^m$.

Thus you have found a representation of $z=\lambda x_1+(1-\lambda)x_2$ in terms of $A^{\top}y$ with $y=\lambda y_1+(1-\lambda)y_2\in\mathbb{R}^m$ for any $\lambda\in\left[ 0,1\right]$, which gives you $z\in S$.

Thus $S$ is convex and no further simplification is needed.

Answer 2

Let $f(y) = A^{\top}y$. Then, $\mathcal{S}$ can be written as $\mathcal{S} =f(\mathbf{R}^{m}_{+}) = \{f(y)\mid y \in \mathbf{R}^{m}_{+}\}$. $\mathcal{S}$ is the image of $\mathbf{R}^{m}_{+}$ under $f: \mathbf{R}^{m} \rightarrow \mathbf{R}^{n} $. Since $f$ is an affine function and $\mathbf{R}^{m}_{+}$ is convex, $\mathcal{S}$ is convex too. See Boyd chapter 2.3.2 for more information.