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:
- 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.
- 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.
- 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