Sums of Separable and Quadratic Polynomials

Amir Ali Ahmadi (), Cemil Dibek () and Georgina Hall ()
Additional contact information
Amir Ali Ahmadi: Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08540
Cemil Dibek: Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08540
Georgina Hall: Decision Sciences, INSEAD, 77305 Fontainebleau Cedex, France

Mathematics of Operations Research, 2023, vol. 48, issue 3, 1316-1343

Abstract: We study separable plus quadratic (SPQ) polynomials, that is, 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 that incorporates separable higher order derivative information.

Keywords: Primary: 90C23; secondary: 90C22; 14Q99; 90C26; nonnegative and sum of squares polynomials; semidefinite programming; polynomial optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1295 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:3:p:1316-1343

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().