A set $S \subset \mathbb{R}^m \times \mathbb{R}^n$ is convex. Using the fact that affine maps preserves convexity prove that $S(y) = \{x \in \mathbb{R}^m\mid (x,y)\in S \}$ and $\hat{S} = \{ x \in \mathbb{R}^m \mid \exists y \in \mathbb{R}^n, \ (x,y) \in S \}$ are convex sets.

In Boyd's book, Chapter 2.3.2. says:

The projection of a convex set onto some of its coordinates is convex: if $S \subseteq \mathbb{R}^m \times \mathbb{R}^n$ is convex, then $$T = \{x_1 \in \mathbb{R}^m\mid(x_1,x_2)\in S \text{ for some } x_2 \in \mathbb{R}^n \} $$ is convex.

Does this mean the question I have is somehow showing a projection can be written as an affine map? Is this very straightforward, or am I missing something?

  • 2
    $\begingroup$ Here is a hint: Suppose $x \in \mathbb{R}^n, y \in \mathbb{R}^m$, then given some point $P = (x_1, y_1) \in \mathbb{R}^{n+m}$, if you wanted to project P onto the X-space, you can simply obtain the projection of $P$ i.e. ($Proj_{X}(P)$) by multiplying $[I_{n} ; [0]_{n \times m}] P$, where $I_{n}$ is the $n \times n$ identity matrix, and $[0]_{n \times m}$ is the $n \times m$ 0 matrix. The $n \times (n+m)$ matrix $[I_{n} ; [0]_{n \times m}]$ can be thought of as the affine map. $\endgroup$ – batwing Jan 21 '20 at 16:11
  • $\begingroup$ Thank you @batwing! I think your answer is very nice for $\hat{S}$. What about $S(y)$ though? How can I show this for the parametrized setting $\endgroup$ – independentvariable Jan 21 '20 at 17:36
  • $\begingroup$ I think for $\hat{S}$ the argument is that we will first fix points with the same $y$ value and apply the affine transformation for these points. Now the question is: 'are the elements of $S$ with the same $y$ value giving a convex set?' and yes, it does; this is easy to see! $\endgroup$ – independentvariable Jan 21 '20 at 17:47
  • 1
    $\begingroup$ Oops, sorry I did not read the question carefully the first time. Just FYI, in literature, $S(y)$ is analogous to the restriction of set $S$ to $Y = y$, while $\hat{S}$ is the projection onto X-axis. As I hinted earlier, $\hat{S}$ is convex. To see why $S(y)$ is convex, you can think of it as the projection onto the X-axis of the intersection of 2 convex sets, namely $S$ and the affine plane $Y = y$. Since you already can see projection is related to affine maps, I think you be able to develop it fully to a proof. $\endgroup$ – batwing Jan 21 '20 at 18:49
  • $\begingroup$ Many thanks for clarification! $\endgroup$ – independentvariable Jan 21 '20 at 20:00

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.