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

Sarah Yini Gao, Xindong Tang, Yancheng Yuan · 2026

Read Max-Min Bilinear Completely Positive Programs: A Semidefinite Relaxation with Tightness Guarantees by Sarah Yini Gao, Xindong Tang, Yancheng Yuan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14949.txt.

Description

Gao and colleagues study max-min problems with a bilinear goal, where one side seeks the most and an enemy side seeks the least. This form covers zero-sum games, robust optimization, and learning under attack. They focus on cases whose unknowns sit in the completely positive cone, which captures many mixed-binary quadratic contests.

The team recasts such problems as one linear program over a joined copositive and CP cone. They then build a ladder of semidefinite relaxations from moment and sum-of-squares tools. Flat truncation tests certify exactness. Under mild terms the ladder is shown tight, and on cases of the cyclic Colonel Blotto game it finds the exact mixed-strategy equilibrium.

Catalog record

CREATORSarah Yini Gao, Xindong Tang, Yancheng Yuan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-14949

Browse the full library · About the Tower of Babel