Quadratic Farkas' Lemma? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T21:59:51Z http://mathoverflow.net/feeds/question/111576 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111576/quadratic-farkas-lemma Quadratic Farkas' Lemma? Seva 2012-11-05T20:13:23Z 2012-11-06T22:42:36Z <p>The <a href="http://en.wikipedia.org/wiki/Farkas%27_lemma" rel="nofollow">Farkas Lemma</a> 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:</p> <blockquote> <p>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$.</p> </blockquote> <p>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$:</p> <blockquote> <p>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$?</p> </blockquote> <p>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).</p> <p>I would expect that this is either false, or should be known. Can anybody construct a counterexample or suggest a reference?</p> http://mathoverflow.net/questions/111576/quadratic-farkas-lemma/111595#111595 Answer by Tony Huynh for Quadratic Farkas' Lemma? Tony Huynh 2012-11-05T22:25:06Z 2012-11-05T22:25:06Z <p>Check out <a href="http://en.wikipedia.org/wiki/Stengle%27s_Positivstellensatz" rel="nofollow">Stengle's Positivstellensatz</a> 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. </p> http://mathoverflow.net/questions/111576/quadratic-farkas-lemma/111612#111612 Answer by Markus Schweighofer for Quadratic Farkas' Lemma? Markus Schweighofer 2012-11-06T04:11:49Z 2012-11-06T22:42:36Z <p>Here is a counterexample: Take $n=2$ variables $X$ and $Y$. Let $L_1,\dots,L_5$ be linear polynomials such that <code>$$S:=\{ (x, y) \in {\mathbb R}^2 ~|~ L_i(x,y) \ge 0\}$$</code> 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$.</p> <p>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$.</p> <p>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...</p> <ul> <li>Marshall: Positive polynomials and sums of squares</li> <li>Prestel: Positive polynomials</li> <li>Bochnak, Coste, Roy: Real algebraic geometry</li> <li>Basu, Pollack, Roy: Algorithms in real algebraic geometry</li> <li>Knebusch, Scheiderer: Einführung in die reelle Algebra</li> <li>Andradas, Bröcker, Ruiz: Constructible sets in real geometry</li> </ul> <p>...and the following articles...</p> <ul> <li><a href="http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf" rel="nofollow">http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf</a></li> <li><a href="http://www.math.uni-konstanz.de/~schweigh/publications/purestates.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/publications/purestates.pdf</a></li> <li><a href="http://www.math.uni-konstanz.de/~schweigh/publications/sosdualsdp.pdf" rel="nofollow">http://www.math.uni-konstanz.de/~schweigh/publications/sosdualsdp.pdf</a></li> </ul> <p>Also the so-called "S-procedure" could be of interest for you.</p>