Paperlane

no. 16 · Tuesday 17 November 2026

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

Sarah Yini Gao, Xindong Tang and Yancheng Yuan

math.OC · v2 · 34 pp

Abstract

We study max-min bilinear completely positive (CP) programs and their associated min-max programs. We establish reformulations of these problems as linear optimization over the product of the CP cone and the copositive (COP) cone, namely, the COP-CP programs. A hierarchy of coupled Moment-SOS type semidefinite relaxations is proposed to solve these COP-CP programs. We show that this approach has asymptotic convergence under mild assumptions. Moreover, we use the coupled flat truncation conditions (FTCs) to certify tightness of semidefinite relaxations, and we give sufficient conditions for finite convergence of the hierarchy, under which the FTCs hold at every optimal solution of all sufficiently high-order relaxations. Numerical experiments are presented to show the effectiveness of our method.

comments
34 pages, 2 figures
fields
Optimization and Control
pdf ↗ page arXiv:2602.14949 ↗