The [Farkas Lemma](http://en.wikipedia.org/wiki/Farkas%27_lemma) says that if a system of linear inequalities implies
yet another linear inequality, then this last inequality can be obtained by
taking a positive linear combination of the inequalities from the system. The
precise statement is as follows:



> 
> Let $L\_1,\dotsc,L\_m$ and $P$ be linear polynomials in the $n$-dimensional real variable $x=(x\_1,\dotsc,x\_n)$, and suppose that the set of all those $x$ with $L\_1(x)\ge 0,\dotsc,L\_m(x)\ge 0$ is non-empty. If $P(x)\ge 0$ for each $x$ from this set, then there exist $c\_1\ge 0,\dotsc,c\_m\ge 0$ with $P\ge cL\_1+\dotsb+cL\_m$.
> 
> 
> 


For $P$ quadratic this may fail: consider, for instance, $L\_1(x)=x$, $L\_2(x)=1-x$, and $P(x)=x(1-x)$. I wonder, however, whether the assertion stays true if we allow summands of the form $L\_iL\_j$:



> 
> Suppose that $L\_1,\dotsc,L\_m$ are linear, and $P$ a quadratic polynomial in the
>  $n$-dimensional real variable $x=(x\_1,\dotsc,x\_n)$. Given that $P(x)\ge 0$
>  whenever $L\_1(x)\ge 0,\ldots,L\_m(x)\ge 0$ (and the set of all such $x$ is
>  non-empty), must there exist $c\_i,c\_{ij}\ge 0$ with $P\ge \sum c\_iL\_i+\sum
> c\_{ij} L\_iL\_j$?
> 
> 
> 


I was able to settle some particular cases; most notably, that where $n=1$ (one variable), and also that where $m=1$ (one constraint). Perhaps, with some effort I can also resolve the case $m=n=2$ (from which the case of $m=2$ and $n$ arbitrary will follow, if I am not mistaken).


I would expect that this is either false, or should be known. Can anybody construct a counterexample or suggest a reference?



Quadratic Farkas' Lemma?
Here is a counterexample: Take $n=2$ variables $X$ and $Y$. Let $L\_1,\dots,L\_5$ be linear polynomials such that
$$S:=\{ (x, y) \in {\mathbb R}^2 ~|~ L\_i(x,y) \ge 0\}$$ is a pentagon inscribed in the unit circle. Furthermore set $P:=1-X^2-Y^2$. Assume we could write $P$ as the sum of a globally nonnegative quadratic polynomial $Q$ and nonnegative linear combinations of the $L\_i$ and $L\_iL\_j$. Now $P$ vanishes at the vertices of the pentagon and each $L\_i$ is nonnegative at these vertices. Therefore $Q$ vanishes also at the vertices. But being a nonnegative quadratic polynomial, $S$ is a sum of squares of linear polynomials which all have also to vanish at the vertices and therefore are identically zero. This shows that $S$ is the zero polynomial. Now notice that each of the $L\_i$ and $L\_iL\_j$ is strictly positive on at least one of the vertices of the pentagon (at which $P$ vanishes, of course). Since $P$ is a nonnegative linear combination of the $L\_i$ and $L\_iL\_j$, this shows that $P=0$.


If the set $S$ defined by the $L\_i$ has non-empty interior, then the convex cone of quadratic polynomials which can be written as a globally nonnegative quadratic polynomial $Q$ and nonnegative linear combinations of the $L\_i$ and $L\_iL\_j$ is closed. In fact, this follows from a much more general result on truncated quadratic modules, see e.g. the book of Marshall cited below (Lemma 4.1.4). This implies that, in the above counterexample, even $P+\varepsilon$ for small $\varepsilon>0$ will fail though this polynomial is strictly positive on $S$.


However, there are a lot theorems going into the direction of what you want. You might want to have a look at the following books...


* Marshall: Positive polynomials and sums of squares
* Prestel: Positive polynomials
* Bochnak, Coste, Roy: Real algebraic geometry
* Basu, Pollack, Roy: Algorithms in real algebraic geometry
* Knebusch, Scheiderer: Einführung in die reelle Algebra
* Andradas, Bröcker, Ruiz: Constructible sets in real geometry


...and the following articles...


* <http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf>
* <http://www.math.uni-konstanz.de/~schweigh/publications/purestates.pdf>
* <http://www.math.uni-konstanz.de/~schweigh/publications/sosdualsdp.pdf>


Also the so-called "S-procedure" could be of interest for you.


