2
$\begingroup$

I'm trying to see if the following sets are convex for all $x$. I proved $S_1$, but having trouble with $S_2$ and $S_3$.

$S_1 = \{x \in R^n : \lVert Ax \rVert \leq 1\} $
$S_2= \{x \in R^n : \lVert Ax \rVert \geq 1\} $
$S_3= \{x \in R^{2n} : \sum_{k=1}^{n} x^2_k \leq \sum_{k=n+1}^{2n} x^2_k \} $

$S_1$:

\begin{equation} \label{eq1} \begin{split} \lVert A(\alpha x + (1 - \alpha)y)\rVert & = \lVert \alpha A x + (1 - \alpha)Ay\rVert \\ & \leq \alpha\lVert A x \rVert +(1 - \alpha)\lVert Ay\rVert \\ & = \alpha(1) + (1-\alpha)(1) = 1 \end{split} \end{equation} Therefore $S_{1}$ is convex because norms cannot be negative and therefore it must be equal to 1.

For $S_2$, intuitively I can see that it is concave. But how can I show this? I would prefer to see a proof rather than a counterexample.

For $S_3$, I don't even know how to start.

Thanks!

$\endgroup$
2
  • $\begingroup$ It may be obvious, but which norm are we considering? A specific one or any norm? $\endgroup$
    – David Cian
    Commented Dec 15, 2019 at 16:23
  • 1
    $\begingroup$ Sorry this the the L2 (euclidian norm). $\endgroup$
    – Eisen
    Commented Dec 15, 2019 at 16:25

1 Answer 1

1
$\begingroup$

Suppose $S_2$ is non-empty, and if $x \in S_2$, then we also have $-x \in S_2$, check that $0 \notin S_2$ and you can make a conclusion.

For $S_3$, let's first consider the special case for $n=1$, then we have $(1,1) \in S_3$ and $(1,-1)\in S_3$, check that their midpoint $(1,0) \notin S_3$. Use this idea to generalize to arbitrary $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .