5

Question:

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?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
independentvariable
  • 3,980
  • 10
  • 36
  • 2
    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. – batwing Jan 21 '20 at 16:11
  • 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 – independentvariable Jan 21 '20 at 17:36
  • 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! – independentvariable Jan 21 '20 at 17:47
  • 1
    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. – batwing Jan 21 '20 at 18:49
  • Many thanks for clarification! – independentvariable Jan 21 '20 at 20:00

0 Answers0