Convexity of the set $C = \{x \in \Bbb R^n \mid x^T Ax \leq b\}$ where $A \in S^n$, $A \succeq 0$ and $b \geq 0$

Question

I have this question in my homework and neither I nor my colleagues can solve it.

Show that the set $$C = \{x \in \Bbb R^n \mid x^T Ax \leq b\}$$ where $A$ is symmetric and positive semidefinite and $b \geq 0$, is convex.

I personally find it similar to halfspace and was thinking that maybe somehow proving that this is a halfspace we can prove that it is convex too. Do you have any ideas?

Answer 1

Notice that for any $x,y\in\mathbb{R}^n$ we have $(x-y)^TA(x-y):=\langle A(x-y),x-y\rangle\geqslant 0$ where $\langle \cdot,\cdot\rangle$ is the usual inner product in $\mathbb{R}^n$. Let $\alpha\in (0,1)$ and $z:=\alpha x+(1-\alpha)y$ with $x,y\in C$. We want to show that $z\in C$. Note that $$z^TAz=\langle Az,z\rangle=\langle A(\alpha x+(1-\alpha)y),\alpha x+(1-\alpha)y\rangle\\=\alpha^2\langle Ax,x\rangle+\alpha(1-\alpha)(\langle Ax,y\rangle+ \langle Ay,x\rangle)+(1-\alpha)^2\langle Ay,y\rangle$$ Using the observation above that $\langle A(x-y),x-y\rangle\geqslant 0$ which implies $$\langle Ax,x\rangle+\langle Ay,y\rangle\geqslant \langle Ax,y\rangle+\langle Ay,x\rangle$$ yields $$\alpha^2\langle Ax,x\rangle+\alpha(1-\alpha)(\langle Ax,y\rangle+ \langle Ay,x\rangle)+(1-\alpha)^2\langle Ay,y\rangle\\\leqslant \alpha^2\langle Ax,x\rangle+\alpha(1-\alpha)(\langle Ax,x\rangle+\langle Ay,y\rangle)+(1-\alpha)^2\langle Ay,y\rangle\\\leqslant \alpha^2b+\alpha(1-\alpha)(b+b)+(1-\alpha)^2b\\=(\alpha+(1-\alpha))^2b=b$$ hence $z\in C$.

Answer 2

Let $A=BDB^{-1}$ where $D$ is diagonal and note that the diagonal entries are non-negative. Then $C=\{(B^{T})^{-1} y:y^{T}Dy \leq b\}$. When you apply a linear transformation to a convex set you get a convex set. Hence all you have to show is $\{y:y^{T}Dy \leq b\}$ is convex. For this you only need the convexity of the function $t \to t^{2}$ on $\mathbb R$.

Answer 3

Let $r := \mbox{rank} (\mathrm A)$. Since $\mathrm A$ is symmetric and positive semidefinite, there is a matrix $\mathrm Q \in \mathbb R^{r \times n}$ such that $\rm A = Q^\top Q$. Hence,

$$b - \mathrm x^\top \mathrm A \,\mathrm x = b - \mathrm x^\top \mathrm Q^\top \mathrm Q \,\mathrm x \geq 0$$

Using the Schur complement, we obtain the following linear matrix inequality (LMI) in $\mathrm x \in \mathbb R^n$

$$\begin{bmatrix} \mathrm I_r & \mathrm Q \,\mathrm x\\ \mathrm x^\top \mathrm Q^\top & b\end{bmatrix} \succeq \mathrm O_{r+1}$$

Hence, the set is a spectrahedron and, thus, convex.

---

convex-analysis schur-complement linear-matrix-inequality spectrahedra

Answer 4

The function $x \mapsto x^TAx$ is convex. Indeed, the Hessian of this function is $A \succeq 0$. $C$ is just a sublevel set of this function.