Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Farkas 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?

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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

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

share|improve this answer
1  
$L_1=1+x$, $L_2=1-x$, and $P=x^2$ is not a counterexample: take all $c_i$ and $c_{ij}$ to be equal to $0$. Many thanks for the references! –  Seva Nov 6 '12 at 7:10
    
You are right, I am sorry for suggesting this counterexample. However, I think that I have now a valid counterexample, see above. –  Markus Schweighofer Nov 6 '12 at 14:50
1  
$L_1=1-x$, $L_2=1+x$, $L_3=1-y$, $L_4=1+y$, and $P=2-x^2-y^2$ is not a counterexample in view of $P=L_1L_2+L_3L_4$. –  Seva Nov 6 '12 at 17:59
    
I am so sorry, you are again right. But if you take a pentagon instead of a square, then it works. Not all of the $L_i L_j$ were strictly positive on at least one of the vertices of the square but for the pentagon this works. –  Markus Schweighofer Nov 6 '12 at 20:12
1  
It does seem to work for a pentagon - thanks for the nice example! –  Seva Nov 6 '12 at 21:16
add comment

Check out Stengle's Positivstellensatz from real semi-algebraic geometry. It can be thought of as a 'polynomial version' of Farka's Lemma which is what it appears you are looking for.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.