Convexity and positive semidefinitness . There is a question that just popped up in my mind:
Let $P$ be a polyhedron and $f: \Bbb R^n \to \Bbb R $ be a quadratic function, i.e., $f$ admits the representation  $$f(x) = x^t Q x + b^t x + \alpha $$ where $Q$ is a $n \times n$ matrix. Assume $f$ is convex on $P$. Then can we find a positive semidefinite matrix $A$ and vector $a$ and scalar $\beta$  such that $$f(x) = x^t A x + a^t x + \beta  \quad \quad \forall x \in P$$
a) I guess no, looking for an example?  What if  $\mbox{int} \, P \ne \emptyset$?
 A: If $P$ has an interior point $x$, then
$$\frac{d^2}{dt^2}\bigg|_{t=0} \ f(x+tv) =(v,Qv)$$ for all $|v|=1$.
Since $f$ is convex, then $Q$ is a positive semidefinite matrix.
That is, $f$ is a convex function on $\mathbb{R}^n$.
A: Assume that $P$ is a set with a non-empty relative interior, i.e. $\exists x_0\in\text{ri}\,P$.


*

*Make a translation $P_0=\{\xi\colon \xi=x-x_0,\,x\in P\}$ and
$$
f(x)=f(x_0+\xi)=\phi(\xi).
$$
We have that $0\in\text{ri}\,P_0$ and
$$
f(x)=x^TQx+\langle\ldots\rangle\ \text{ is convex on }P \iff \phi(\xi)=\xi^TQ\xi+\langle\ldots\rangle \text{ is convex on }P_0.
$$
Here $\langle\ldots\rangle$ denotes linear and constant terms which do not affect convexity.

*Let ${\cal M}$ denote the linear span of $P_0$ and ${\mathbb P}_{\cal M}$ the orthogonal projection on ${\cal M}$. Since $\phi$ is convex on $P_0$ that has non-empty interior in ${\cal M}$ we have
$$
\xi^TQ\xi\ge 0,\quad\forall\xi\in{\cal M}\ \iff \ {\mathbb P}_{\cal M}Q{\mathbb P}_{\cal M}\text{ pos.semidef}.
$$

*Now define $A={\mathbb P}_{\cal M}Q{\mathbb P}_{\cal M}$ and
$$
\psi(\xi)=\phi({\mathbb P}_{\cal M}\xi)=\xi^TA\xi+\langle\ldots\rangle.
$$
Translating back
$$
q(x)=\psi(x-x_0)=x^TAx+\langle\ldots\rangle
$$
to get for $x\in P$
$$
f(x)=\phi(\xi)=\phi({\mathbb P}_{\cal M}\xi)=q(x)
$$
and $q$ is convex in ${\mathbb R}^n$.

