We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial, and (ii) a sum of squares. We establish that the answer to question (i) is positive for univariate plus quadratic polynomials and for convex SPQ polynomials, but negative already for bivariate quartic SPQ polynomials. We use our decomposition result for convex SPQ polynomials to show that convex SPQ polynomial optimization problems can be solved by "small" semidefinite programs. For question (ii), we provide a complete characterization of the answer based on the degree and the number of variables of the SPQ polynomial. We also prove that testing nonnegativity of SPQ polynomials is NP-hard when the degree is at least four. We end by presenting applications of SPQ polynomials to upper bounding sparsity of solutions to linear programs, polynomial regression problems in statistics, and a generalization of Newton's method which incorporates separable higher-order derivative information.
翻译:我们研究的是 separable (SPQ) 和 tudicrical (SPQ) 多元类比, 即多元类比, 是不同变量和二次多元类比的单亚多元类比之和。 我们研究的是, 不可忽略的多元类比(SPQ) 是平方体之和, 我们研究的是, 非否定的 SPQ 多元类比(SPQ) 是 (i) 一种非正反的双向性多面性复数的和, 以及(ii) 平方的和。 我们确定, 问题答案(i) 是对于单异性加二次多面性多面性多面性多面性和二次性多面性多面性多面性非单项性之和性之和, 问题的答案是积极的, 我们用 SPQ 的共性多面性共性求和性共性解决方案的共性共性共性共性共性共性共性之和性之和性, 我们也可以通过 Scialalalalal 的最小半非二次性程序来解算度。