demonstrating convexity of set defined by quadratic inequality

Question

So i'm trying to solve this problem and I don't have any idea how to proceed.

A is a Positive-definite matrix, $\alpha \in \Bbb R$,

Show that the set $$ S(A,a; \alpha) = \{x \in \Bbb R^n \mid \frac 12 \langle x,Ax \rangle + \langle a,x \rangle \leq \alpha \} $$ is convex.

How?

P.S. I know what convex means , I know what a Positive-definite matrix is , but they don't give me the form of the matrix, no nothing.

Answer 1

What you need to show is that for $x_1, x_2 \in S$ and $0 \leq t \leq 1$, the element $(1-t)x_1 + t x_2$ is also an element of $S$. The only piece of information about $A$ required to show this is that $A$ is positive definite. In particular, if $A$ is positive definite, then the function $f(x) = \sqrt{\langle x,Ax \rangle}$ is a norm over $\Bbb R^n$.

It is also helpful to observe that $$ \langle (x-x_0),A(x-x_0) \rangle = \langle x,Ax\rangle - \langle (A + A^T)x_0,x\rangle + \langle x_0,Ax_0\rangle $$ Now, if we take $x_0 = (A + A^T)^{-1}\alpha$, then we can rewrite the set $S$ as $$ S = \{x \in \Bbb R^n \mid \langle x-x_0, A(x-x_0) \rangle - \langle x_0,Ax_0 \rangle \leq \alpha \} \implies\\ S = \{x \in \Bbb R^n \mid \langle x-x_0, A(x-x_0) \rangle \leq \alpha + \langle x_0,Ax_0 \rangle\} \implies\\ S = \{x \in \Bbb R^n \mid [f(x-x_0)]^2 \leq \beta \} \implies\\ $$ where we have defined $\beta = \alpha + \langle x_0,Ax_0 \rangle$. If $\beta < 0$, $S$ must be empty. If $\beta \geq 0$, we have $$ S = \{x \in \Bbb R^n \mid f(x-x_0) \leq \sqrt{\beta}\} $$ It is now straightforward to show that $S$ is convex using the fact that $f$ is a norm.

Answer 2

The set $S$ is convex as a lower-level set of a convex function $$ f:x\mapsto \frac{1}{2}\langle x,Ax\rangle + \langle\alpha,x\rangle. $$ (If $x,y$ is such that $f(x), f(y) \leq c$, then $f(tx+(1-t)y) \leq tf(x) +(1-t)f(y) \leq c$ for all $0<t<1$.)

To see that $f$ is convex, it suffices to show $$ g:t\in \mathbb{R}\mapsto f(x+ty) $$ is convex for all $x$ and $y\neq 0$. This follows from $$ g''(t) = \langle y, Ay\rangle>0. $$

Answer 3

Consider the epigraph of $f$ which is the set {$(x,a):a\geq\,f(x)$}

The function clearly has a minimum because $\bigtriangledown f(x)=0$ gives: $Ax+a=0$ and since $A$ is positive definite, hence invertible, $x=A^{-1}(-a)$ and $\bigtriangledown^{2}f(x)=A$ which is positive definite, therefore we have a minimum.

Now, i)if $\alpha\,<\,minf(x)$ the set is empty.

ii)If $\alpha\,\geq\,minf(x)$ then the set is the green region which is an intersection of two convex sets and hence convex!!