# Can we decompose a polynomial into difference of convex polynomials?

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

-
This sounds very familiar; I think my previous advisor B. Shapiro described this to me, or something very similar. In any case, in more than one variable, it feels like a strong condition to be representable in such a way; so my guess is this is either false, or unsolved. –  Per Alexandersson Feb 10 '14 at 21:37

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.

-
Thanks. Could you please specify how to construct the difference of two convex, given an arbitrary polynomial? –  slwang Feb 11 '14 at 18:07
Ok. Let $Q$ be $(\Sigma x_i^2)$, $S = Q^n + Q$, where $2n > deg$ of your polynomial. $Hess(S) > 0$ and $1/|1/Hess(S)|$ tends to infinity as $C * r^(4n-4)$. For any polynomial $Z$ of degree $\leq 2n$ its true that $|Hess(Z)|$ tends to infinity not faster than $C' * r^(4n-4)$ there exist such $N > 0$ that $|Hess(Z)| < N 1/|1/Hess(S)|$, and, hence, $NS + Z$ is convex. So, for $P = NS + Z$, $Q = NS$ everything holds. –  Lev Soukhanov Feb 13 '14 at 16:20
Wow. Great construction. Thanks very much. –  slwang Feb 14 '14 at 7:37
Hi Lev. Could you please also simply explain why a=>c is obvious, or give me some references? Moreover, in your construction what is the definition of $|1/Hess(S)|$, the determinant of inverse Hessian? –  slwang Feb 18 '14 at 21:27
(a) => (c): Let us take a little ball around an inner point. It linearly spans the vector space. Also |1/Hess(S)| is a norm of the inverse matrix, sum of the squares of matrix elements. –  Lev Soukhanov Feb 19 '14 at 21:15

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.

-