I am trying to understand Sums-of-Squares proof systems. A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as $\sum_{i=1}^m g_i(x)p_i(x) = s(x) + 1$ for a some polynomials $g_i$ and a sums-of-squares polynomial $s$ such that $\sum_{i=1}^m g_i(x)p_i(x)$ is of degree at most $d$. Is it true that a degree $1$ Sums-of-Squares refutation proves the infeasibility of a linear program? Then the polynomials in $P$ must all be linear, the polynomials $g_i$ are just constants, but I do not understand the role of $s$ then.
6
-
$\begingroup$ in linear programming, you either have equations with nonnegative variables (something you can control by squaring them), or inequalities - and for these you either need a more general Positivstellensatz, or you'd need to introduce nonnegative slack variables, getting back to the previous case. $\endgroup$– Dima PasechnikCommented Feb 10, 2023 at 22:15
-
$\begingroup$ certainly, in LP with equations and nonnegative variables it could be that the corresponding system of linear equations is infeasible even if you drop non-negativity of variables, but this is a boring special case. $\endgroup$– Dima PasechnikCommented Feb 10, 2023 at 22:23
-
1$\begingroup$ it seems the latter case is indeed as you describe, may be refuted with $s=0$ and $g_i$ not all zero constants, but this is not a refutation for a general LP feasibility problem. $\endgroup$– Dima PasechnikCommented Feb 10, 2023 at 22:50
-
$\begingroup$ Hi, thanks for the comment! So you are saying there is no form of a linear program like $Ax = b$ without constraining $x\geq0$. So far I thought that restricting the polynomials $p_i$ to degree 1 yields a linear program, but thats not true then? Isnt it possible to introduce some slack variables to include $x\geq0$ in $Ax = b$? $\endgroup$– Tom KeatonCommented Feb 11, 2023 at 14:05
-
$\begingroup$ No, you can't really get around nonnegativity by linear equations alone. $\endgroup$– Dima PasechnikCommented Feb 11, 2023 at 14:18
|
Show 1 more comment