Shape-Constrained Regression Using Sum of Squares Polynomials

Mihaela Curmei () and Georgina Hall ()
Additional contact information
Mihaela Curmei: Department of Electrical Engineering and Computer Science, University of California, Berkeley, California 94720
Georgina Hall: Decision Sciences, INSEAD, Fontainebleau 77300, France

Operations Research, 2025, vol. 73, issue 1, 543-559

Abstract: We present a hierarchy of semidefinite programs (SDPs) for the problem of fitting a shape-constrained (multivariate) polynomial to noisy evaluations of an unknown shape-constrained function. These shape constraints include convexity or monotonicity over a box. We show that polynomial functions that are optimal to any fixed level of our hierarchy form a consistent estimator of the underlying shape-constrained function. As a by-product of the proof, we establish that sum of squares-convex polynomials are dense in the set of polynomials that are convex over an arbitrary box. A similar sum-of-squares-type density result is established for monotone polynomials. In addition, we classify the complexity of convex and monotone polynomial regression as a function of the degree of the polynomial regressor. Whereas our results show NP-hardness of these problems for degree three or larger, we can check numerically that our SDP-based regressors often achieve a similar training error at low levels of the hierarchy. Finally, on the computational side, we present an empirical comparison of our SDP-based convex regressors with the convex least squares estimator introduced in Hildreth [ Hildreth C (1954) Point estimates of ordinates of concave functions. J. Amer. Statist. Assoc. 49(267):598–619] and Holloway [ Holloway CA (1979) On the estimation of convex functions. Oper. Res. 27(2):401–407] and show that our regressor is valuable in settings in which the number of data points is large and the dimension is relatively small. We demonstrate the performance of our regressor for the problem of computing optimal transport maps in a color transfer task and that of estimating the optimal value function of a conic program. A real-time application of the latter problem to inventory management contract negotiation is presented.

Keywords: Optimization; polynomial regression; convex regression; semidefinite programming; consistency of statistical estimators; optimal transport (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0383 (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:oropre:v:73:y:2025:i:1:p:543-559

Access Statistics for this article

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