The 2013 Newton Institute Programme on polynomial optimization

Adam N. Letchford, Jean B. Lasserre, Pablo A. Parrilo, David SteurerMath. Program 2015 · DOI · OpenReview

Introduction

This article serves as the preface to a special issue of Mathematical Programming Series B, documenting the outcomes of the landmark 2013 research program held at the Isaac Newton Institute for Mathematical Sciences. The program, titled "Polynomial Optimization, Efficiency through Convexity," brought together a diverse group of researchers to advance the field of polynomial optimization (PO). By bridging the gap between abstract algebraic geometry and practical computational engineering, the program facilitated the development of twelve seminal papers that represent the state-of-the-art in the field.

Problem Statement

Polynomial optimization involves the minimization or maximization of a polynomial objective function subject to constraints also defined by polynomials. These problems are ubiquitous in modern science and engineering, appearing in fields as varied as quantitative finance, robotics, and structural design. However, PO problems are notoriously difficult to solve because they are frequently non-convex and computationally intensive.

Historically, the study of PO was fragmented, with researchers in operations research, statistics, and engineering often working in isolation. The 2013 Newton Institute program aimed to address this by fostering a unified, interdisciplinary approach. The goal was to integrate high-level mathematical tools—such as commutative algebra, moment theory, and algebraic geometry—into the toolkit of applied optimizers to make these complex problems more tractable.

Methodological Framework

As a preface to a collection of research, this paper summarizes a variety of methodologies employed across the twelve featured studies. Key techniques highlighted include:

  • Semidefinite Programming (SDP) and Sums-of-Squares (SOS): These methods utilize convex relaxations to provide tractable approximations for non-convex polynomial problems.
  • Copositive Programming: This involves reformulating problems over completely positive cones, which is particularly effective for handling "hard" quadratic programs.
  • Algebraic Geometry: Researchers applied local optimality conditions and classified convex sets through a geometric lens to better understand the structure of optimization landscapes.
  • Symmetry Handling: By exploiting extreme symmetry within specific problems, researchers were able to significantly reduce computational complexity.
  • Reformulation-Linearization Technique (RLT): This approach combines classical linearization with innovative cutting-plane methods to solve mixed 0–1 polynomial programs.

Key Insights and Results

The research presented in this special issue offers several critical insights for the optimization community:

The Power of Approximation

Several papers demonstrate that while exact solutions for certain PO problems may be theoretically impossible within a reasonable timeframe, highly accurate "inner and outer" approximations can be constructed. These approximations are computationally efficient and provide practical bounds for real-world applications.

Symmetry as an Advantage

Rather than increasing difficulty, extreme symmetry can be explicitly leveraged to speed up algorithms. For instance, using copositive representations allows for more efficient handling of symmetric structures that would otherwise be computationally prohibitive.

Cross-Pollination of Disciplines

The field is increasingly borrowing from "pure" mathematics. Linking polynomial-time approximation schemes to classical Bernstein polynomials and multinomial distributions has provided a deeper theoretical foundation for why certain algorithms perform effectively.

Geometry of Convexity

There is a growing focus on "convex algebraic geometry," which seeks to understand the specific shapes formed by intersecting semidefinite cones with hyperplanes. This geometric understanding is vital for characterizing the feasible regions of optimization problems.

Practical Outcomes

The twelve submissions represent significant advancements in several areas:

  • Graph Partitioning: New bounding procedures were developed that outperform previous methods while remaining computationally practical.
  • Global vs. Local Optimality: New methods for deriving local optimality conditions allow for the efficient enumeration of local minima in specific cases.
  • Packing Problems: Innovative approaches to discrete geometry packing problems were developed by combining graph theory and topology.
  • Robust Optimization: Techniques were established to construct tractable approximations for convex sets defined by polynomial inequalities, a critical requirement for optimization in uncertain environments.

Discussion and Future Directions

While the 2013 program marked significant progress, the challenge of scalability remains a primary concern. Many of the advanced algebraic methods discussed are powerful but can become computationally expensive as the degree of the polynomials or the number of variables increases.

Future research must focus on refining the tractability of these methods for large-scale industrial applications. Continuing to bridge the gap between abstract mathematical theory and the development of robust numerical software implementation is essential for the continued evolution of polynomial optimization.

Summary updated

BibTeX
@article{letchford2015newton,
  author = {Adam N. Letchford and Jean B. Lasserre and Pablo A. Parrilo and David Steurer},
  title = {{The 2013 Newton Institute Programme on polynomial optimization}},
  journal = {Math. Program.},
  year = {2015},
  doi = {10.1007/s10107-015-0886-1},
}
Figure