Sublinear circuits for polyhedral sets

DOI10.1007/S10013-021-00528-1zbMATH Open1487.05046arXiv2103.09102OpenAlexW3203920743MaRDI QIDQ2135087FDOQ2135087

Thorsten Theobald, Helen Naumann

Publication date: 4 May 2022

Published in: Vietnam Journal of Mathematics (Search for Journal in Brave)

Abstract: Sublinear circuits are generalizations of the affine circuits in matroid theory, and they arise as the convex-combinatorial core underlying constrained non-negativity certificates of exponential sums and of polynomials based on the arithmetic-geometric inequality. Here, we study the polyhedral combinatorics of sublinear circuits for polyhedral constraint sets. We give results on the relation between the sublinear circuits and their supports and provide necessary as well as sufficient criteria for sublinear circuits. Based on these characterizations, we provide some explicit results and enumerations for two prominent polyhedral cases, namely the non-negative orthant and the cube $[-1,1{]}^n$.

Full work available at URL: https://arxiv.org/abs/2103.09102

zbMATH Keywords

polyhedronpositive functionnon-negativity certificatesublinear circuitsums of arithmetic-geometric exponentials

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30) Semidefinite programming (90C22) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Real algebraic sets (14P05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lectures on Polytopes
• Forms derived from the arithmetic-geometric inequality
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Newton polytopes and relative entropy optimization
• Relative entropy relaxations for signomial optimization
• Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks
• Polyhedral and algebraic methods in computational geometry
• A unified framework of SAGE and SONC polynomials and its duality theory
• Signomial and polynomial optimization via relative entropy and partial dualization
• SHAPES OF POLYHEDRA, MIXED VOLUMES AND HYPERBOLIC GEOMETRY
• REPOP
• The \(\mathcal{S}\)-cone and a primal-dual view on second-order representability
• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• A second order cone characterization for sums of nonnegative circuits

Cited In (3)

• Algebraic Perspectives on Signomial Optimization
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Sublinear circuits and the constrained signomial nonnegativity problem

Uses Software

• REPOP

This page was built for publication: Sublinear circuits for polyhedral sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2135087)