Sum-of-squares relaxations for polynomial min-max problems over simple sets

Francis R. BachMath. Program 2025 · OpenReview

Introduction

Min-max optimization is a cornerstone of robust optimization and game theory, formulated as finding a point $x$ that minimizes a function which is itself the result of a maximization over another variable $y$: $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} g(x, y)$. While polynomial optimization has seen significant advances through the Lasserre hierarchy and sum-of-squares (SOS) relaxations, min-max problems present a unique challenge. Even when the objective $g(x, y)$ is a polynomial, the "inner" function $f(x) = \max_{y \in \mathcal{Y}} g(x, y)$ is generally non-polynomial and non-smooth.

This paper introduces a novel one-stage primal-dual approach to solve these problems over "simple" sets—such as hypercubes, Euclidean spheres, or balls—leveraging matrix-valued SOS polynomials to achieve superior convergence properties compared to traditional methods.

The Limitations of Two-Stage Approaches

Existing techniques for polynomial min-max problems typically rely on a "two-stage" strategy. In the first stage, the non-polynomial function $f(x)$ is approximated by a high-degree polynomial upper bound. In the second stage, this bound is minimized. While theoretically sound, this approach is often computationally prohibitive. The approximations converge slowly, requiring very high-degree polynomials to achieve accuracy, which leads to massive semi-definite programs (SDPs) that are difficult to solve.

A One-Stage Primal-Dual Formulation

The core innovation of this work is the transition from a two-stage approximation to a unified one-stage primal-dual framework. This is achieved through several key steps:

  1. Probabilistic Reformulation: The problem is recast in the space of probability measures. Instead of optimizing over points $x$ and $y$, the author treats the problem as a convex-concave game between two distributions.
  2. Matrix-Valued SOS Relaxations: To make the measure-based problem tractable, the author employs matrix-valued SOS polynomials. This allows the inner maximization to be parameterized directly within the optimization framework, casting the entire min-max problem as a single SDP.
  3. Kernelization: To mitigate the "curse of dimensionality" inherent in polynomial bases, the method utilizes kernel methods. By working with function evaluations at specific sample points rather than explicit monomial coefficients, the algorithm remains efficient even as the problem dimension increases.

This approach is specifically tailored for "simple sets" where SOS representations are well-characterized and computationally efficient, such as the unit ball or the hypersphere.

Empirical Performance and Theoretical Insights

The method was evaluated on synthetic benchmarks, including univariate and bivariate trigonometric polynomials and geometric sets like hypercubes and Euclidean spheres.

Finite Convergence

A significant finding is the observation of finite convergence. While the paper provides a rigorous proof for asymptotic convergence (as the degree of the polynomial relaxation tends toward infinity), empirical tests show that the exact global optimum is often reached at relatively low degrees. This stands in stark contrast to two-stage methods, which typically produce "blunt" bounds that only slowly sharpen.

The Putinar Connection

The paper establishes a theoretical link between this min-max formulation and Putinar’s Positivstellensatz, a famous result in algebraic geometry. The maximization component of the proposed algorithm effectively serves as a "feasibility certificate." It can prove the non-existence of solutions for certain polynomial inequalities, providing a bridge between optimization and algebraic geometry.

Conclusion and Future Directions

By integrating matrix-valued SOS relaxations with a primal-dual perspective, this work provides a more direct and efficient path for solving polynomial min-max problems. The use of kernelization ensures that the resulting SDPs are solvable using standard tools, scaling with sample points rather than monomials.

However, challenges remain. The current framework is restricted to simple sets; extending these results to general semi-algebraic sets defined by arbitrary inequalities is a primary goal for future research. Additionally, while finite convergence is observed in practice, the theoretical conditions that guarantee it remain an open question. Future work may also explore first-order solvers to improve scalability beyond the limits of generic SDP toolboxes.

Summary updated

Abstract

We consider min–max optimization problems for polynomial functions, where a multivariate polynomial is maximized with respect to a subset of variables, and the resulting maximal value is minimized with respect to the remaining variables. When the variables belong to simple sets (e.g., a hypercube, the Euclidean hypersphere, or a ball), we derive a sum-of-squares formulation based on a primal-dual approach. In the simplest setting, we provide a convergence proof when the degree of the relaxation tends to infinity and observe empirically that it can be finitely convergent in several situations. Moreover, our formulation leads to an interesting link with feasibility certificates for polynomial inequalities based on Putinar’s Positivstellensatz.
BibTeX
@inproceedings{bach2025sum,
  author = {Francis R. Bach},
  title = {{Sum-of-squares relaxations for polynomial min-max problems over simple sets}},
  booktitle = {Math. Program},
  year = {2025},
  url = {https://openreview.net/forum?id=488SZWVyzF},
}
Figure