In the previous post we have established relation between P vs NP problem and quartic positive polynomial optimization problem. Here I will give some intuition why it is possible that we would be able to decide that quartic polynomial has non-zero global minimum. I’ll give only the short intuition leaving details for professionals. I’m not interested in putting all comas in place.
- NP-complete decision problems
- Non-negative quartic polynomials
- Reznick perturbation lemma
- Sum of squares optimization
- Blekherman beautiful high school exposition about why not all positive quartics are sums of squares
- Extremal polynomials
- Some combinatorics
- Semialgebraic geometry
- NP-complete problems:
Partition problem: Given a multiset of integers is it possible to divide it into complementary multisets having the same sum, i.e. whether there exist such that .
For those who loves 3-SAT: given a set of logical clauses having exactly 3 binary variables (literals) each, decide whether all clauses can be satisfied (evaluated true) at once. To encode it, we want the set of polynomial equation evaluating 0 when clause is true: would be translated into .
Combining together we have for partition problem: ; for 3-SAT: , where is one 3 term clause. The last equation is not always positive, but for large enough it is, when problem is not satisfiable, thanks to third ingredient.
- Reznick perturbation lemma (3.1 in the reference) adapted to quartics:
Given positive polynomial with no zeros at infinity (), condition 1 in the Lemma. If NP-complete problem is not satisfiable , condition 2. Finally, , where are zero set of , a set of where polynomial vanishes. Therefore, there exists that is positive.
It should be noted here that global minimum is polynomially bounded away from 0, and constant c too.
- Both are covered in the previous post. In short the number of coefficients in quadratic polynomials (squared they give quartic sum of squares) is roughly quadratic. It is sufficient to fix the value of quadratic polynomial at quadratic number of points to constrain all coefficients, and therefore to constrain the values at all points in a hypercube of interest. The number of coefficients in quartic polynomial is roughly quartic, therefore there is more freedom in choice of coefficients. It is possible to select quartic coefficient in a way that will constrain all values of quadratic to 0 on hypercube.
- The simple example of quartic polynomial that is not sum of squares is Robinson polynomial: . This is extremal polynomial (Choi, Lam (1977), Reznick (2007) ) – it cannot be non-trivially decomposed into other forms. This polynomial has seven zeros on the hypercube and one non zero value. Therefore, we can independently control value at one vertex of hypercube (1,1,1) by multiplying Robinson polynomial by positive constant.
- Let , i.e. we replace , we say negation (by analogy with binary variables and there translation to polynomials). This is also extremal positive polynimial that controls value at (0,1,1). Same way we can make all extremal polynomials that controls independently all vertices of a hypercube. Let be a linear combination of all Robinson polynomials controlling different vertices of hypercube in 3 variables with positive coefficients (i.e. a point inside the cone of positive polynomials defined by the Robinson polynomials).Now consider polynomial . Once the value of this polynomial at is positive, there exists such that this polynomial is positive! The same is true if we sum up all negations of quartic: . Once values on 16 hypercube vertices are positive there is that for all the polynomial is positive. Note that all 16 vertices are controlled independently.
Now take all the combinations of 4 coordinates/variables/literals out of n dimensions/variables/literals of the problem. Construct the polynomials from the previous paragraph for all combinations and take linear combination of them with positive coefficients. We get positive polynomials (not extreme) that have control over quartic number of points (in the number of variables) which is exactly the number of points required to constraint all coefficients of quartic polynomial. It should be noted that we would not be able to find the global minimum of the polynomial because of the requirement that quartic terms (that are not controlled by the Robinson terms) should be evaluated at positive values, but remember that there is polynomial gap for unsatisfiable problem. Therefore, we can require all vertices to have positive values.
The only missing part here is the estimation on the bound for value. This may be large, but should be polynomial in the number of bits and number of dimensions.
- We actually interested in the positive solution inside hypercube. So, we have additional terms to reduce the complexity of the problem, i.e. semialgebraic bound on the region: for 3-SAT and for partition problem. It adds additional freedom in the choice of variables, and limits the value of being quite small.
Finally we can control values of quartic polynomial in quartic number of points such that differences between given unsatisfiable problem and resulting quartic be sum of squares, including 1. In the later case we have linear program in polynomial number of variables.
I’m not a mathematician, and hate all comas in place. I’m more than happy to unpack unclear points, but will refuse to estimate so no one would claim I solved the problem, in case. And remember, the science is moving forward not because established scientists change their mind, but because young people come.
Update 12 Jan 2016.
I see where the skepticism comes from. The perturbation can be quite strong. We can require quartic polynomial being zero (with zero grdient) at roughly cubic number of generic points. all quadratics would be zero in this space since they have only quadratic number of monomials, so we have over-determined system of linear equations on the coefficients of quadratics. On the other hand we can freely move those cubic points in space (up to infinity) and still get possibly positive polynomials. This is the problem on one hand, on the other hand, this opens a way for continuation methods. By the way by the homogenization the problem of infinity is replaced by the path along unit sphere. Therefore, there is more good than bad. I imagine a continuation method for solving optimization problem by starting with well defined positive polynomials (say sums of squares) and splitting extra solutions from well defined ones(say on a hypecube) toward correct coefficients until we get enough of them (up to a cubic, where by the number of coefficient they will approach extremal polynomials). We can actually have a polynomial number of separate splits with their (conical/non-negative) sum leading to desired optimized polynomial. The big question here is preservation of positivity, which is a global property.
update 24 jan 2016
Rhe following is in words that needs translation to math.
If we start with sums of squares which have clear solution, we can now peak a cubic point around solution (very close) and require the qurtic polynomial to be round at this points (i.e. the value and gradient are zero at these points and Hessian is positive definite ) than this polinomial will be positive and is not sum of squares. More generaly, the quartic polynomial will positive if more than square points (number of monomials in quadratic polinomial of the same dimension) are round and there is continuous path to original sum of squares such that this property holds for every point in the path. That would an alternative ( to Hilbert method) way to construct positive polynomials.