1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'd say $\;A\;$ is a matrix...yet I can't tell what $\;A\in S^n\;$ is, since $\;S^n\;$ usually denotes the sphere in $\;\Bbb R^{n+1}\;$ ... $\endgroup$ – DonAntonio Apr 5 '18 at 8:50
1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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 test for positive semidefiniteness, we then 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.