Let $$S := \left\{ x \in \mathbb{R}^n : x^T Q x \leq (a^Tx)^2, a^T x \geq0 \right\}$$ where $Q \in \mathbb{S}_{++}^n$ and $a \in \mathbb{R}^n$. Show that $S$ is a convex cone.
I am aware that for a set to be a convex cone, the following should hold:-
- $x,y \in S$ $\implies$ $x+y \in S$
- $x\in S$ and $\theta \geq 0$ $\implies$ $\theta x \in S$
I attempted to use $x,y \in S$ to get $x+y \in S$ but so far I have been unsuccessful. The squared term on the R.H.S is throwing me off. Any suggestions will be appreciated.
EDIT: I have attempted the following working. Kindly verify if this is correct
$(x+y)^TQ(x+y)=x^TQx+x^TQy+y^TQx+y^TQy \ $ $ \leq \ (a^Tx)^2+(a^Ty)^2+2x^TQy$
$\leq \ (a^Tx)^2+(a^Ty)^2+2a^Tx^TQy$
$\leq (a^T(x+y))^2$
I'm not sure about the second last step. Thanks in advance
EDIT 2:
I believe that the following proof should suffice. Kindly let me know if any errors are found and of any alternate proof that may exist. Thank you.
First I will show that S is convex.
A set S is convex if for $\alpha , \beta \in [0,1]$ , $\alpha + \beta =1$ and $x,y\in S$, we have $\alpha x + \beta y \in S$ If $x \in S$ then $x^TQx \leq (a^Tx)^2$ and $a^Tx \geq 0$
Similarly, if $y \in S$ then $y^TQy \leq (a^Ty)^2$ and $a^Ty \geq 0$
Then, $\alpha x + \beta y \in S \implies (\alpha x + \beta y)^T Q (\alpha x + \beta y) \leq (a^T(\alpha x + \beta y))^2$
Lets focus on the LHS of this inequality.
$(\alpha x + \beta y)^T Q (\alpha x + \beta y) = \alpha^2 x^TQx + \beta y^TQy + 2\alpha \beta x^TQy$
Let's attempt to separate $x$ and $y$ from $x^TQy$
$x^TQy = x^T Q^{1/2} Q^{1/2} y = (Q^{1/2}x)^T(Q^{1/2}y) \ \ $ (since $Q \in S_{++}^n$)
$(Q^{1/2}x)^T(Q^{1/2}y) \leq ||Q^{1/2}x|| \cdot ||Q^{1/2}y|| \ \ $ (Cauchy Schwartz Inequality)
$||Q^{1/2}x|| \cdot ||Q^{1/2}y|| = \sqrt{\langle Q^{1/2}x, Q^{1/2}x \rangle} \sqrt{\langle Q^{1/2}y, Q^{1/2}y \rangle} = \sqrt{x^TQx} \cdot \sqrt{y^TQy}$
By the Arithmetic-Geometric Mean Inequality, we know that $\sqrt{ab} \leq \frac{(a+b)}{2}$ and $\sqrt{ab}=\sqrt{a} \sqrt{b}$ for non-negative reals.
Hence,
$\sqrt{x^TQx} \cdot \sqrt{y^TQy} \leq \frac{1}{2} (x^TQx + y^TQy)$
$\implies \alpha^2 x^TQx + \beta y^TQy + 2 \alpha \beta x^TQy \leq \alpha^2 x^TQx + \beta y^TQy + \alpha \beta (x^TQx + y^TQy)$
Let $\beta = 1 - \alpha$
$\implies \alpha^2 x^TQx + (1-\alpha)^2y^TQy + \alpha (1- \alpha) (x^TQx + y^TQy) $
$= \alpha x^T Q x + (1-\alpha)y^TQy$
$\implies (\alpha x + \beta y)^T Q (\alpha x + \beta y) \leq \alpha x^T Q x + (1- \alpha) y^TQy$
$\leq \alpha (a^Tx)^2 + (1 - \alpha)(a^Ty)^2$
$\leq \alpha (a^Tx)^2 + (1 - \alpha)(a^Ty)^2 + 2 \alpha \beta (a^Tx)(a^Ty)$
$= (a^T(\alpha x + \beta y))^2$
$\implies (\alpha x + \beta y)^T Q (\alpha x + \beta y) \leq (a^T(\alpha x + \beta y))^2 $
Which is what we required. Hence, S is convex.
For S to be a cone, let $\theta \geq 0$ and $x \in S$. Then, $S$ is a cone if $\theta x \in S$
$x \in S \implies x^TQx \leq (a^Tx)^2$
We know that $\theta^2 \geq 0$ so we can multiply on both sides without changing the inequality sign
$\theta ^2 x^TQx \leq \theta^2(a^Tx)^2$
$\theta x^T Q \theta x \leq (a^T \theta x)^2$
$\implies \theta x \in S$
Hence, $S$ is a cone.
Therefore, $S$ is a convex cone.