Convexity and positive semidefinitness .

Question

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

Answer 1

Assume that $P$ is a set with a non-empty relative interior, i.e. $\exists x_0\in\text{ri}\,P$.

1. 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.
2. 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}. $$
3. 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$.

Answer 2

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