This is a generalization of "A quadratic polynomial is nonnegative for all $x$ if and only if the discriminant is nonpositive" in terms of dimension.
The problem:
Let $A$ be a real symmetric matrix, $b\in \mathbb{R}^n$ and $c\in \mathbb{R}$. I'm trying to show that $p(x)=x^TAx+2b^Tx+c$ is nonnegative if and only if the matrix $M:=\begin{bmatrix}A&b\\b^T&c\end{bmatrix}$ is positive semidefinite.
My attempt:
Define $z=(x,y)\in \mathbb{R}^{n+1}$ and $$q(x,y)=z^TMz=x^TAx+2yb^Tx+y^2c,$$ if $M\succeq 0$, then $q(x,1)=p(x)\geqslant0$ for every $x\in \mathbb{R}^n$.
Alright.
Conversely, if $p(x)\geqslant 0$, then $c=p(0)\geqslant 0$ and $A\succeq 0$, otherwise there would exist $w\in \mathbb{R}^n$ and $\alpha>0$ such that $p(\alpha w)=\alpha^2w^TAw+2\alpha b^Tw+c<0$, which cannot happen.
How can I prove that $q(x,y)$ is bounded below?
Assuming it is, then let us take $(\overline{x},\overline{y})\in \mathbb{R}^n$ such that $q(\overline{x},\overline{y})=\min q(x,y)$, then $$q(\overline{x},\overline{y})=\overline{x}^T(A\overline{x}+\overline{y}b)+(\overline{x}^Tb\overline{y}+\overline{y}^2c)\geqslant 0,$$ because $$\nabla_x q(\overline{x},\overline{y})=2(A\overline{x}+\overline{y}b)=0$$ and $$\frac{\partial}{\partial y} q(\overline{x},\overline{y})=2\overline{x}^Tb+2\overline{y}c=0=\overline{x}^Tb\overline{y}+\overline{y}^2c.$$ Then we are done. Unfortunately, I wasn't able to prove the highlighted statement to conclude my proof.
Any help would be much appreciated.
The first paragraph in your attempt shows one direction: if $M \succeq 0$, then $p(x)$ is nonnegative. It remains to show the other direction: if $p(x)$ is nonnegative, then $M \succeq 0$ (equivalently, that $q(x,y) \ge 0$ for all $x,y$).
If $p(x)$ is nonnegative for all $x$, then $q(x,1)$ is nonnegative for all $x$, which means $q(x,y) = y^2 q(x/y, 1)$ is nonnegative whenever $y \ne 0$.
So it remains to consider $q(x,0) = x^{\mathsf T}\!Ax$.
If there is an $x$ such that $q(x,0) < 0$, then $$ p(tx) = (tx)^{\mathsf T}\!A(tx) + 2b^{\mathsf T}(tx) + c = q(x,0) t^2 + (2b^{\mathsf T}x) t + c $$ is a quadratic polynomial in $t$ whose leading coefficient $q(x,0)$ is negative. As a result, there is some large $t$ for which $p(tx) < 0$.
So, contrapositively, if $p$ is always nonnegative, then $q(x,0)$ should be nonnegative for all $x$, finishing off the other direction of the proof.