1

I am trying to determine if the following set is convex

$$\left\{x \in \mathbb{R}^{n}: 2x^Tx \le 1 + \|x\|_2 \right\}.$$

I feel like I am missing something here. My understanding is that both $2x^Tx$ and $\|x\|_2$ evaluate to scalars, and now this is just an inequality of scalars. Is this really as simple as the fact that the norm is the square root of $x^Tx$, so the only way this can be satisfied is if $x^Tx < 1$ and then extrapolate that out for all $x,y \in \mathbb{R}$? I feel like I almost understand it intuitively (unless I am mistaken), but how do I prove it with the definition of complexity?

DMcMor
  • 9,407
Steven White
  • 47

2 Answers2

2

We can indeed rewrite the definition of the set as follows: $$ S = \{x \in \Bbb R^n : 2\|x\|^2 \leq 1 + \|x\|\} $$ But of course, $$ 2\|x\|^2 \leq 1 + \|x\| \iff 2\|x\|^2 - \|x\| - 1 \leq 0 \iff \\ (\|x\|-1)(2\|x\| + 1) \leq 0 \iff\\ \|x\| - 1 \leq 0 $$ So, $S$ is simply the closed ball of radius $1$, which is of course convex.

Ben Grossmann
  • 225,327
1

As you say, the inequality is satisfied precisely when $x^Tx\leq1$, so your set consists of those $x\in\mathbb R^n$ such that $x^Tx\leq1$. This set is indeed convex, and it is easy to show so; but I don't think it is obvious.

Suppose that $x^Tx\leq1$ and$y^Ty\leq1$, and $t\in[0,1]$. Then, using Cauchy-Schwarz to go from the first line to the second one, \begin{align} (tx+(1-t)y)^T(tx+(1-t)y)&=t^2x^Tx+(1-t)^2y^Ty+2t(1-t)y^Tx\\ \ \\ &\leq t^2x^Tx+(1-t)^2y^Ty+2t(1-t)(y^Ty)^{1/2}(x^Tx)^{1/2}\\ \ \\ &\leq t^2+(1-t)^2+2t(1-t)=(t+1-t)^2=1. \end{align} So $tx+(1-t)y$ also belongs to the set.

Martin Argerami
  • 205,756