Max-Min Bilinear Completely Positive Programs: A Semidefinite Relaxation with Tightness Guarantees

Sarah Yini Gao, Xindong Tang, Yancheng YuanarXiv 2026 · DOI · arXiv

TL;DR

This paper introduces a novel framework for solving complex max-min bilinear optimization problems where variables are constrained by the "completely positive" (CP) cone. By reformulating these nested problems into a single-stage linear program over a combined COP-CP cone and applying a hierarchy of semidefinite programming (SDP) relaxations, the authors provide a method that can certify and achieve exact global optima for NP-hard problems in game theory and robust optimization.

What Problem Does This Paper Address?

Max-min bilinear problems are the mathematical backbone of competitive scenarios, such as two-player zero-sum games, robust optimization, and adversarial machine learning. In these models, one agent tries to maximize an objective while an adversary tries to minimize it.

The challenge arises when the decision variables involve discrete choices (like binary variables) or non-convex quadratic constraints. These are often modeled using Completely Positive (CP) programming. While CP programming is powerful, solving a nested max-min problem over CP cones is notoriously difficult. Standard approximation methods for CP cones and their duals, Copositive (COP) cones, typically work in opposite directions—one provides an upper bound while the other provides a lower bound. This makes it nearly impossible to guarantee convergence or "tightness" (finding the exact answer) when they are combined in a max-min setting.

Methods

The authors propose a three-step approach to bridge this gap:

  1. Single-Stage Reformulation: They use Lagrangian duality to transform the nested max-min problem into a single-stage linear program. This new formulation operates over the Cartesian product of the COP and CP cones (the COP-CP program).
  2. Moment-SOS Hierarchy: Since testing membership in these cones is NP-hard, the authors develop a hierarchy of semidefinite relaxations. This is based on Moment-SOS (Sum-of-Squares) theory, which approximates the difficult cones with a sequence of increasingly complex but solvable Semidefinite Programs (SDPs).
  3. Flat Truncation Certification: To move from "approximation" to "exact solution," they employ flat truncation conditions. This is a rank-based check on the moment matrices produced by the SDP. If these conditions are met, the relaxation is guaranteed to be "tight," meaning it has found the exact global optimum of the original NP-hard problem.

Datasets

The paper does not use traditional large-scale datasets. Instead, it evaluates the framework using:

  • Synthetic Toy Examples: Small-scale matrices designed to demonstrate the mechanics of the SDP relaxation and the certification of tightness.
  • The Cyclic Colonel Blotto Game: A newly introduced extension of Borel’s classic resource allocation contest. In this version, locations are arranged in a circle, and the defender can redeploy surplus resources to adjacent locations. This adds a layer of spatial correlation and "complementary effects" that make the game significantly harder to solve than the standard version.

Key Insights and Ideas

  • The COP-CP Duality: The authors show that the complexity of the max-min structure can be "collapsed" into a single stage by leveraging the relationship between CP and COP cones.
  • Provable Tightness: One of the most significant "aha" moments is the proof that the Moment-SOS hierarchy isn't just an asymptotic approximation; under mild conditions (Assumption 3 in the paper), it achieves finite convergence. This means the exact solution is reached at a specific, finite level of the hierarchy.
  • Spatial Strategy in Games: In the Cyclic Blotto game, the CP formulation successfully captures the "complementary effect" of adjacent locations. The results show a fundamental asymmetry: the defender benefits from dispersing resources to exploit redeployment, while the attacker must concentrate force to neutralize that advantage.

Key Results

  • Exact Solutions: In numerical tests, the SDP relaxations consistently met the flat-truncation conditions at low hierarchy orders (usually $k=2$ or $3$), solving the exact mixed-strategy Nash equilibrium for the games.
  • Efficiency for Moderate Scales: For problems with up to 10 locations ($N=10$) and 20 binary variables, the relaxation solves in a few minutes on a standard laptop. For example, an $N=10$ instance with a $253 \times 253$ moment matrix solved in approximately 2,061 seconds.
  • Payoff Recovery: The framework successfully recovered the exact expected payoffs (e.g., a payoff of 0.55 for a specific $N=4$ Blotto instance), which would be impossible to derive using qualitative reasoning alone.

Limitations and Future Work

  • Scalability: The "curse of dimensionality" is the primary hurdle. As the number of locations or resource units grows, the size of the moment matrices in the SDP hierarchy grows combinatorially. Solving very large-scale games (e.g., $N > 20$) would likely require more specialized, sparse SDP solvers or decomposition techniques.
  • Relaxation Gap: While the authors provide conditions for tightness, they acknowledge that quantifying the "gap" when those conditions are not met remains an open theoretical question.
  • Algorithmic Tailoring: The current study uses general-purpose solvers (Mosek). The authors suggest that future work could involve designing tailored algorithms that exploit the specific structure of the COP-CP cone to improve computational speed.

Summary updated

Abstract

Max-min bilinear optimization models, where one agent maximizes and an adversary minimizes a common bilinear objective, serve as canonical saddle-point formulations in optimization theory. They capture, among others, two-player zero-sum games, robust and distributionally robust optimization, and adversarial machine learning. This study focuses on the subclass whose variables lie in the completely positive (CP) cone, capturing a broad family of mixed-binary quadratic max-min problems through the modelling power of completely positive programming. We show that such problems admit an equivalent single-stage linear reformulation over the COP-CP cone, defined as the Cartesian product of the copositive (COP) and CP cones. Because testing membership in COP cones is co-NP-complete, the resulting COP-CP program inherits NP-hardness. To address this challenge, we develop a hierarchy of semidefinite relaxations based on moment and sum-of-squares representations of the COP and CP cones, and flat truncation conditions are applied to certify the tightness. We show that the tightness of the hierarchy is guaranteed under mild conditions. The framework extends existing CP/COP approaches for distributionally robust optimization and polynomial games. We apply the framework to the cyclic Colonel Blotto game, an extension of Borel's classic allocation contest. Across multiple instances, the semidefinite relaxation meets the flat-truncation conditions and solves the exact mixed-strategy equilibrium.
BibTeX
@misc{gao2026max,
  author = {Sarah Yini Gao and Xindong Tang and Yancheng Yuan},
  title = {{Max-Min Bilinear Completely Positive Programs: A Semidefinite Relaxation with Tightness Guarantees}},
  year = {2026},
  eprint = {2602.14949},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.14949},
}
Figure