Signomial and polynomial optimization via relative entropy and partial dualization

Riley Murray, Venkat Chandasekaran, Adam WiermanMath. Program. Comput 2021 · DOI · OpenReview

Abstract

Global optimization of signomials and polynomials is a fundamental challenge in engineering and data science, traditionally addressed through Sums-of-Squares (SOS) hierarchies. However, SOS methods often struggle with scalability and the preservation of problem sparsity. This paper introduces a framework for global optimization using SAGE (Sums-of-AM/GM Exponential) certificates combined with partial dualization. By leveraging relative entropy-based nonnegativity certificates, the proposed method provides a computationally efficient alternative that excels in sparse, high-dimensional settings.

Introduction

Optimization serves as the underlying engine for diverse applications ranging from structural engineering to neural network training. Finding the global minimum in a landscape characterized by local optima is notoriously difficult (NP-hard). For decades, Sums-of-Squares (SOS) programming has been the standard approach for these problems. SOS transforms global optimization into Semidefinite Programs (SDP), but this transformation is often "dense," destroying the inherent sparsity of the original problem and leading to prohibitive memory requirements as the number of variables increases.

In "Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization," Murray, Chandrasekaran, and Wierman present a shift in this paradigm. Their approach utilizes SAGE certificates, which rely on the Arithmetic-Mean/Geometric-Mean (AM/GM) inequality rather than the eigenvalue-based logic of SOS. This shift allows for the use of Exponential Cone Programming (ECP), which is better suited for maintaining sparsity and handling the signomial functions common in engineering design.

Methodology

SAGE Certificates and X-SAGE Cones

The core of the framework is the SAGE certificate, which proves a function's non-negativity by decomposing it into simpler "AGE" (Arithmetic-Geometric-Exponential) functions. The authors extend this by defining Conditional SAGE Cones ($X$-SAGE). This allows researchers to certify non-negativity over specific constrained sets $X$—such as boxes, spheres, or polytopes—rather than requiring global non-negativity across all space.

Relative Entropy and Partial Dualization

Unlike SOS, which is powered by semidefinite solvers, the SAGE framework is driven by a relative entropy engine. This formulation maps naturally to the exponential cone, which is often more efficient for sparse problems. To handle complex constraints, the authors employ partial dualization. This strategy bifurcates constraints: some are kept within the set description while others are treated via dual variables. This "best of both worlds" approach allows the SAGE framework to integrate seamlessly with classical convex duality.

Solution Recovery

A significant contribution of this work is a novel algorithm for solution recovery. By analyzing the dual variables within the relative entropy constraints, the authors can extract the actual optimal coordinates ($x^*$). This process is more robust than traditional methods because the dual variables in SAGE relaxations correspond to "conditional moments," providing a clearer path from the relaxation back to the original problem space.

Experimental Results

The methodology was validated against a suite of 51 problems from global optimization literature, including engineering benchmarks, signomial libraries, and polynomial test sets.

  • Optimality and Coverage: The SAGE approach recovered best-known solutions for 23 out of 29 signomial problems, with 17 of those being certified as globally optimal.
  • Computational Efficiency: In comparative benchmarks, SAGE demonstrated significant speed advantages. For instance, in a specific polynomial test case (Example 4), SAGE reached the global minimum in approximately 3 seconds, whereas the competing BSOS method required over 80 seconds.
  • Scalability: The authors introduced a benchmark of random sparse quartics to test high-dimensional performance. SAGE successfully scaled to problems with up to 40 variables, a regime where traditional SOS methods frequently fail due to memory exhaustion.

To facilitate adoption, the authors have released sageopt, a Python-based software package that implements these techniques, allowing users to solve complex signomial and polynomial problems with minimal boilerplate code.

Discussion and Future Work

While the SAGE framework offers a powerful alternative to SOS, it is not without limitations. The authors noted that high-level hierarchies can lead to numerical instabilities in current exponential cone solvers like MOSEK or ECOS. Furthermore, the maturity of ECP solvers currently lags behind that of SDP solvers, particularly when dealing with extreme rays of the exponential cone.

Future research directions include the integration of SAGE certificates into branch-and-bound algorithms. Such a hybrid approach could potentially establish a new standard for global optimization in engineering design, combining the rigorous bounds of SAGE with the exhaustive search capabilities of combinatorial optimization.

Summary updated

Abstract

We describe a generalization of the Sums-of-AM/GM-Exponential (SAGE) methodology for relative entropy relaxations of constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE certificates conveniently and transparently blend with convex duality, in a way which enables partial dualization of certain structured constraints. This more general approach retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), and inspires a projective method of solution recovery which respects partial dualization. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package.
BibTeX
@article{murray2021signomial,
  author = {Riley Murray and Venkat Chandasekaran and Adam Wierman},
  title = {{Signomial and polynomial optimization via relative entropy and partial dualization}},
  journal = {Math. Program. Comput.},
  year = {2021},
  doi = {10.1007/s12532-020-00193-4},
}
Figure