Convexification of box-constrained polynomial optimization problems via monomial patterns

Gennadiy Averkov, Benjamin Peters, Sebastian SägerarXiv 2019 · DOI · arXiv

Abstract

Convexification is a core technique in global polynomial optimization. Currently, there are two main approaches competing in theory and practice: the approach of nonlinear programming and the approach based on positivity certificates from real algebra. The former are comparatively cheap from a computational point of view, but typically do not provide tight relaxations with respect to bounds for the original problem. The latter are typically computationally expensive, but do provide tight relaxations. We embed both kinds of approaches into a unified framework of monomial relaxations. We develop a convexification strategy that allows to trade off the quality of the bounds against computational expenses. Computational experiments show very encouraging results.

Introduction

Polynomial Optimization Problems (POPs)—the task of finding the minimum of a polynomial subject to constraints—are notoriously difficult (NP-hard) because they are generally non-convex. To solve them, researchers rely on "relaxations," which replace the difficult problem with a simpler, convex one that provides a lower bound on the true minimum.

Historically, two distinct "schools of thought" have dominated this field:

  1. The Nonlinear Programming (NLP) Community: This group utilizes relatively simple tools like McCormick envelopes. These methods are computationally "cheap" and scale well but often provide weak bounds, necessitating many iterations in a branch-and-bound framework.
  2. The Polynomial Optimization Community: This group uses "positivity certificates" from real algebra, such as Sum-of-Squares (SOS) or Lasserre's moment hierarchy. These provide very tight bounds but are computationally "expensive," often failing to scale as the number of variables or the degree of the polynomial increases.

This paper addresses the lack of a common language between these groups by proposing a unified framework that treats both approaches as different configurations of the same underlying concept.

Methodology: The Monomial Pattern

The core innovation of this research is the monomial pattern. A pattern is defined as a finite set of exponent vectors $P \subset \mathbb{N}^n$ that dictates which monomial variables ($v_\alpha \approx x^\alpha$) are linked by convex constraints. This framework allows for a unified representation where McCormick envelopes, expression trees, Handelman’s hierarchy, and Lasserre’s moment hierarchy can all be expressed as specific types of monomial patterns.

Visualization of different exponent sets $A_1, A_2, A_{ex}$ used to evaluate the connectivity and performance of monomial patterns.

As shown in the figure above, the framework was tested on various exponent sets ($A_1, A_2, A_{ex}$) to understand how the structure of the pattern affects the relaxation. A key insight is that connectivity is king: the quality of a relaxation depends heavily on how well the pattern connects the original exponents of the problem. If a pattern family doesn't "connect" these exponents, the resulting bounds will be poor, regardless of the complexity of the underlying mathematics.

To bridge the gap between speed and tightness, the authors introduced novel pattern types:

  • Truncated Submonoids: These allow for localized algebraic relaxations.
  • Chains and Shifted Chains: These provide structured connectivity for sparse or adversarial problems.
  • Lifting: By introducing auxiliary monomial variables (lifting the problem into a higher-dimensional space), the description of the "moment body" is simplified, making it easier to convexify.

Experimental Setup and Datasets

The authors evaluated their framework using a newly introduced Random POP Benchmark Library containing 13 different types of finite exponent sets, including dense, sparse, and specially structured "adversary" sets. They benchmarked their monomial patterns against industry standards, including BARON (global optimization), YALMIP (SOS relaxations), and CS-TSSOS (sparsity-exploiting SOS).

Key Results

The experiments demonstrated that monomial patterns allow for a systematic trade-off between speed and tightness:

  • Speed vs. Tightness: On dense exponent sets ($n=4, d=10$), the proposed "Multilinear" (M) and "Hybrid" (H) patterns produced bounds significantly tighter than standard root-node relaxations in BARON while remaining orders of magnitude faster than full SOS methods.
  • Scaling: The "Truncated Submonoid" (T) strategy successfully computed non-trivial bounds for sparse instances with up to 80 variables, a regime where standard SOS solvers typically crash due to memory limits.
  • Adversarial Success: In cases where standard multilinear relaxations failed (adversary sets), specific patterns like chains proved essential.
A chain-based monomial pattern applied to the adversarial set $A_{ex}$, demonstrating how specific structures can bridge gaps in connectivity.

As illustrated above, the "Chain" (C) and "Shifted Chain" (S) patterns matched the reference global solution almost perfectly with minimal computational overhead in adversarial conditions.

Conclusion and Future Work

By selecting specific sets of exponent vectors, researchers can now systematically trade off computational speed for bound quality, enabling the solution of large-scale problems that were previously intractable. While the current work focuses on box-constrained problems, future research will aim to extend this to general polynomial inequalities. Additionally, the authors envision integrating these pattern-based relaxations into existing global solvers like SCIP or COUENNE and developing hypergraph-based heuristics to automate the selection of optimal patterns for new problems.

Summary updated

Abstract

Convexification is a core technique in global polynomial optimization. Currently, there are two main approaches competing in theory and practice: the approach of nonlinear programming and the approach based on positivity certificates from real algebra. The former are comparatively cheap from a computational point of view, but typically do not provide tight relaxations with respect to bounds for the original problem. The latter are typically computationally expensive, but do provide tight relaxations. We embed both kinds of approaches into a unified framework of monomial relaxations. We develop a convexification strategy that allows to trade off the quality of the bounds against computational expenses. Computational experiments show very encouraging results.
BibTeX
@misc{averkov2019convexification,
  author = {Gennadiy Averkov and Benjamin Peters and Sebastian Säger},
  title = {{Convexification of box-constrained polynomial optimization problems via monomial patterns}},
  year = {2019},
  eprint = {1901.05675},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.05675},
}
Figure