Quadratic Farkas' Lemma? - MathOverflow

Quadratic Farkas' Lemma?

2012-11-05T20:13:23Z

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?

Answer by Tony Huynh for Quadratic Farkas' Lemma?

2012-11-05T22:25:06Z

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.

Answer by Markus Schweighofer for Quadratic Farkas' Lemma?

2012-11-06T04:11:49Z

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.