A second order cone characterization for sums of nonnegative circuits

Jie Wang, Victor MagronISSAC 2020 · OpenReview

TL;DR

This paper shows that the cone of sums of nonnegative circuits (SONC) can be represented using second-order cones (SOCs). This representation allows for the development of a new algorithm that computes SONC decompositions for certain nonnegative polynomials using SOC programming, offering a more efficient alternative to existing methods for polynomial optimization.

What Problem Does This Paper Address?

Optimizing over convex cones is a fundamental problem in mathematics and computer science. Second-order cones (SOCs) are a particularly attractive class of convex cones because optimization problems involving them (SOCPs) can be solved much more efficiently than those involving semidefinite programming (SDPs). A key question in this area is: which other convex cones can be represented using SOCs? This paper focuses on the cone of sums of nonnegative circuits (SONC), which is a certificate of nonnegativity for polynomials that preserves sparsity, unlike the more common sum of squares (SOS) certificate. The challenge is to find an efficient way to work with SONC polynomials, and this paper addresses this by showing that SONC cones admit an SOC representation, paving the way for SOCP-based algorithms.

Methods

The core contribution of this paper is the constructive proof that the SONC cone admits a second-order cone representation. This is achieved by establishing a key connection between SONC polynomials and sums of binomial squares with rational exponents. This connection is built upon the concept of "A-rational mediated sets," which are a generalization of previously studied "A-mediated sets." By leveraging this link, the authors develop an algorithm that computes SONC decompositions for specific classes of nonnegative polynomials. This algorithm relies on solving second-order cone programs (SOCPs), which are computationally more efficient than semidefinite programs (SDPs) typically used for SOS decompositions. The paper also introduces algorithms for computing simplex covers and rational mediated sets, which are crucial components of their SONC decomposition algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development, with numerical experiments conducted on randomly generated polynomials.

Key Insights and Ideas

  • SONC cones have an SOC representation: This is the central finding, bridging the gap between the expressive power of SONC polynomials and the computational efficiency of SOC programming.
  • Connection to Sums of Binomial Squares: The paper reveals a deep connection between SONC polynomials and sums of binomial squares with rational exponents. This connection is key to constructing the SOC representation.
  • A-rational mediated sets: This novel concept generalizes existing notions and is crucial for building the SONC decomposition algorithm. It allows for a more flexible and computationally tractable construction.
  • SOCP for SONC decomposition: The ability to represent SONC cones using SOCs enables the development of new algorithms for computing SONC decompositions via SOC programming, offering a potential speedup over SDP-based methods.

Key Results

The paper proves that SONC cones admit a second-order cone representation. Based on this, they propose a new algorithm for computing SONC decompositions for certain classes of nonnegative polynomials using SOC programming. Numerical experiments on randomly generated polynomials (up to 40 variables and degree 60) demonstrate the efficiency of their algorithm, with running times generally being satisfactory and relative optimality gaps being competitive, especially for sparse polynomials.

Limitations and Future Work

The authors acknowledge that the quality of the SONC lower bounds obtained can be affected by the choice of simplex cover and the gap between general nonnegative polynomials and SONC PN-polynomials. They suggest future work on designing rounding-projection procedures to obtain exact nonnegativity certificates for polynomials within the interior of the SONC cone. Additionally, they plan to investigate the complexity analysis and software implementation of their hybrid numeric-symbolic scheme and compare it with existing methods based on SDP or geometric programming.

Summary updated

Abstract

The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits an SOC representation. Based on this, we give a new algorithm to compute SONC decompositions for certain classes of nonnegative polynomials via SOC programming. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with a fairly large size (both size of degree and number of variables).
BibTeX
@inproceedings{wang2020second,
  author = {Jie Wang and Victor Magron},
  title = {{A second order cone characterization for sums of nonnegative circuits}},
  booktitle = {ISSAC},
  year = {2020},
  url = {https://openreview.net/forum?id=PzaF3LjZWT6},
}
Figure