Can we decompose a polynomial into difference of convex polynomials?

Question

Given a multivariate polynomial $p(x_1, ..., x_n)$ on $\mathbb{R}^n$, can we always decompose it into the difference of two convex polynomials? i.e., is there a pair of convex polynomials $f$ and $g$, such that: $\forall (x_1, ..., x_n) \in \mathbb{R}^n$, $p(x_1, ..., x_n) = f(x_1, ..., x_n) - g(x_1, ..., x_n)$?

If given a bounded region $\mathbb{N}$ which is a convex subset of $\mathbb{R}^n$, can we then decompose polynomial $p(x_1, ..., x_n)$ such that in $\forall (x_1, ..., x_n) \in \mathbb{N}$ , $p(x_1, ..., x_n) = f(x_1, ..., x_n) - g(x_1, ..., x_n)$ where $f$ and $g$ are convex polynomials.

If we can (no matter under the unbounded or bounded case), is there any constructive method to find such a pair of $f$ and $g$ for a given $p$?

Answer 1

Polynomials of degree $n$ which are convex in the given domain form a cone (subset which is closed under "+" and multiplication on nonnegative numbers) in the finite-dimensional space of polynomials of degree $n$.

Lemma For a given cone $C$ in a vector space $V$ the following statements are equivalent

(a) $C$ contains an inner point

(b) $\forall v \in V \exists s, t \in C$ such that $s-t=v$

(c) linear span of $C$ is $V$

Proof

(b)<=>(c) obvious

(a)=>(c) obvious

(c)=>(a) pick a basis $(e_1, ..., e_n)$ in $C$ and take $e_1 + ... + e_n$, its inner

---

For the bounded region, theorem follows obviously, because slight deformation of strictly convex polynomial is convex in the bounded domain.

For the unbounded region it can be done as follows: solve it for the homogeneous polynomials (where you can restrict to the unit sphere and use that it is compact) and then take the homogeneous convex polynomial which is inner and add the standard quadratic form.

Answer 2

For a bounded convex region as the domain, the answer is yes.

Let $ Hess(p) $ be the hessian matrix of p (the matrix of the second derivatives by each pair of variables). This is an $ n\times n $ symmetric matrix each of whose elements is a real polynomial. The elements of this matrix are bounded functions on N, say the absolute value of each element is at most m everywhere in N. Define

$$ f(x_1, \dots, x_n) := nm(x_1^2 + \dots + x_n^2) $$

Then f is convex, and $ Hess(f) = 2nmE $ where E is the identity matrix of size n. Now $ g := f - p $ is a polynomial, and $ Hess(g) = Hess(f) - Hess(p) $ at any point in N is a symmetric real matrix whose diagonal elements are at least $ 2nm - m $ but other elements have absolute value at most m so it is postive definite. This implies that g is convex in N.

I don't know if a similar argument could work in the unbounded case.

Edit: mentioned the matrix being symmetric, which I used implicitly.