Recognizing Signomial Convexity is Hard
Abstract
Signomials---finite sums of generalized monomials with real exponents---are a natural machine learning model, combining parsimonious representations of power laws, inverse relationships, and multiplicative interactions with universal approximation and interpretable parameters. In fact, 45 of the 100 equations in the AI Feynman benchmark admit signomial representations. Moreover, signomial optimization is widely used in engineering design, communications, economics, and machine learning, but is computationally intractable in general. Convexity, the gold standard for efficient optimization, offers three routes to tractability for signomials: a signomial may be convex in its original variables, become convex after a logarithmic change of variables, or, when positive, become convex after additionally taking the logarithm of its value---the structure underlying disciplined geometric programming. We show that recognizing each form is strongly NP-hard, both on compact domains and globally. Our proofs start from gap-promise variants of polynomial convexity and develop polynomial-to-signomial reductions that preserve curvature gaps under the relevant logarithmic transformations.
Related
- Recognizing convergence actions as proper isometric actions on hyperbolic spaces
- Recognizing oriented knots from finite quotients with one marked element
- The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem
- Polynomial convexity and non-polynomial convexity of totally real discs in ℂ2
- The Porous Medium Equation and Convexity
BibTeX
@misc{zheng2026recognizing,
title = {{Recognizing Signomial Convexity is Hard}},
author = {Rui Zheng and Iosif Sakos and Antonios Varvitsiotis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01812},
eprint = {2610.01812},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01812},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Recognizing Signomial Convexity is Hard
AU - Rui Zheng
AU - Iosif Sakos
AU - Antonios Varvitsiotis
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01812
UR - https://arxiv.org/abs/2610.01812
AB - Signomials---finite sums of generalized monomials with real exponents---are a natural machine learning model, combining parsimonious representations of power laws, inverse relationships, and multiplicative interactions with universal approximation and interpretable parameters. In fact, 45 of the 100 equations in the AI Feynman benchmark admit signomial representations. Moreover, signomial optimization is widely used in engineering design, communications, economics, and machine learning, but is computationally intractable in general. Convexity, the gold standard for efficient optimization, offers three routes to tractability for signomials: a signomial may be convex in its original variables, become convex after a logarithmic change of variables, or, when positive, become convex after additionally taking the logarithm of its value---the structure underlying disciplined geometric programming. We show that recognizing each form is strongly NP-hard, both on compact domains and globally. Our proofs start from gap-promise variants of polynomial convexity and develop polynomial-to-signomial reductions that preserve curvature gaps under the relevant logarithmic transformations.
ER -