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
| CREATOR | Sarah Yini Gao, Xindong Tang, Yancheng Yuan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-14949