Algebraic perspectives on signomial optimization

Mareike Dressler, Riley MurraySIAM J. Appl. Algebra Geom 2021

TL;DR

This paper introduces "signomial rings" to bring the concept of "degree" back into polynomial optimization, enabling the development of complete hierarchies of convex relaxations for signomial optimization problems. This new framework offers significant speedups and improved performance compared to existing global solvers and the Lasserre hierarchy, particularly for problems with irrational exponents and nonconvex constraints.

What Problem Does This Paper Address?

Polynomial optimization, a powerful tool for solving complex problems, has a well-established theory built around the concept of "degree." However, many real-world problems, especially in fields like chemical engineering and aerospace, are modeled using "signomials." Signomials are a generalization of polynomials that allow for arbitrary real exponents, offering greater expressive power but historically sacrificing the organizing principle of degree. This loss of structure makes it challenging to develop efficient and complete optimization algorithms. Specifically, deciding if a signomial is nonnegative on a given set (a fundamental problem in optimization) is generally intractable. This paper aims to bridge this gap by reintroducing algebraic structure to signomial optimization, enabling the development of robust and efficient solution methods.

Methods

The core contribution of this paper is the introduction of signomial rings. These rings provide an algebraic framework that allows for the definition of an "A-degree" for signomials, analogous to the degree of polynomials. This allows the authors to:

  • Develop a Signomial Positivstellensatz: This is a representation theorem that characterizes signomials that are positive on a given compact set. It relies on the concept of "conditional SAGE" (Sums of Arithmetic-Geometric Exponentials) and allows for arbitrary real exponents, even in the presence of nonconvex constraints.
  • Construct Complete Hierarchies of Convex Relaxations: By leveraging the signomial rings and the Positivstellensatz, the authors develop hierarchies of convex programs that provide arbitrarily strong upper and lower bounds for signomial optimization problems. These hierarchies are designed to be efficient and offer improved performance over existing methods.
  • Define Signomial Moment Problems: The paper establishes basic facts on the existence and uniqueness of solutions to signomial moment problems, which are crucial for developing the theoretical underpinnings of their approach.
  • Develop Arbitrarily Strong Outer Approximations: The work also provides methods for constructing arbitrarily strong outer approximations of cones of nonnegative signomials.

The proofs often involve mapping signomial problems to polynomial problems, applying existing polynomial Positivstellensätze (like those by Dickinson and Povh), and then mapping back to signomials.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses examples from existing literature and standard problem formulations for evaluation.

Key Insights and Ideas

  • Reintroducing "Degree" to Signomials: The concept of "signomial rings" and "A-degree" is a key innovation, bringing much-needed algebraic structure to signomial optimization. This allows for the application of powerful tools from real algebraic geometry.
  • Completeness of Convex Hierarchies: The paper demonstrates that their developed hierarchies of convex relaxations are "complete," meaning they can achieve arbitrarily accurate bounds for signomial optimization problems.
  • Handling Nonconvexity and Irrational Exponents: The new framework effectively handles signomial optimization problems with nonconvex constraints and arbitrary real (including irrational) exponents, which are challenging for existing methods.
  • Efficiency Gains: The proposed methods offer significant speedups compared to existing global solvers and the Lasserre hierarchy, particularly for complex problems.
  • Sparsity Exploitation: The framework is designed to exploit sparsity, leading to more efficient computations.

Key Results

  • Theorem 4.1 (Signomial Positivstellensatz): Provides a representation theorem for signomials positive on a compact set, crucial for developing lower bounds.
  • Corollary 5.3: Establishes the completeness of their hierarchy of lower bounds for signomial optimization, guaranteeing convergence to the true minimum.
  • Experimental Results:
    • A factor-500 speedup over the Lasserre hierarchy was observed on a chemical reaction network problem.
  • Their methods outperformed global solvers (SCIP, BARON, ANTIGONE) on a chemical reactor design problem.
  • The proposed hierarchy showed scale invariance, making it robust to the scaling of variables.

Limitations and Future Work

  • Convergence Rates: While the hierarchies are complete, the paper notes that convergence is generally asymptotic, not finite. Future work could involve a detailed study of convergence rates.
  • Choosing the "Best" Ring: The paper suggests that choosing the appropriate signomial ring can significantly impact performance. Developing a theory for selecting the optimal ring is an open question.
  • Dual Formulation Solution Recovery: Efficiently recovering solutions from the dual formulations of their hierarchies, especially when dealing with many dual AGE cones, is an area for further research.
  • Upper Bound Hierarchies: The paper provides a generic construction for upper bound hierarchies. Future work could focus on specific constructions and their convergence properties, particularly for K-SAGE signomials.
  • Noncompact Sets: While the paper discusses some aspects of noncompact sets, further investigation into the behavior of their methods in such scenarios is suggested.

Summary updated

Abstract

Signomials are obtained by generalizing polynomials to allow for arbitrary real exponents. This generalization offers great expressive power, but has historically sacrificed the organizing principle of ``degree'' that is central to polynomial optimization theory. We reclaim that principle here through the concept of signomial rings, which we use to derive complete convex relaxation hierarchies of upper and lower bounds for signomial optimization via sums of arithmetic-geometric exponentials (SAGE) nonnegativity certificates. The Positivstellensatz underlying the lower bounds relies on the concept of conditional SAGE and removes regularity conditions required by earlier works, such as convexity and Archimedeanity of the feasible set. Through worked examples we illustrate the practicality of this hierarchy in areas such as chemical reaction network theory and chemical engineering. These examples include comparisons to direct global solvers (e.g., BARON and ANTIGONE) and the Lasserre hierarchy (where appropriate). The completeness of our hierarchy of upper bounds follows from a generic construction whereby a Positivstellensatz for signomial nonnegativity over a compact set provides for arbitrarily strong outer approximations of the corresponding cone of nonnegative signomials. While working toward that result, we prove basic facts on the existence and uniqueness of solutions to signomial moment problems.
BibTeX
@article{dressler2021algebraic,
  author = {Mareike Dressler and Riley Murray},
  title = {{Algebraic perspectives on signomial optimization}},
  journal = {SIAM J. Appl. Algebra Geom},
  year = {2021},
}
Figure