Title: Recent advances on algorithms for solving doubly nonnegative relaxations of mixed-binary quadratic programs

Speaker:Kim-Chuan Toh (Professor)

Time: Monday, August 18, 2025,9:00-12:00

Venue: Room 3A02, Building No. 37, Wushan Campus

Abstract: 

As a powerful relaxation of the completely positive conic reformulation of a mixed-binary quadratic program (MBQP), doubly nonnegative (DNN) relaxation can usually provide a tight lower bound. However, DNN programming problems are known to be challenging to solve because of their huge number of $\Omega(n^2)$ constraints and $\Omega(n^2)$ variables. In this talk, we present some recent advances on algorithms for solving DNN problems and related variants. In particular, we introduce the algorithm RiNNAL, a method for solving DNN relaxations of large-scale MBQPs by leveraging their solutions’ possible low-rank property. RiNNAL is a globally convergent Riemannian based augmented Lagrangian method (ALM) that penalizes the nonnegative and complementarity constraints while preserving all other constraints as an algebraic variety in the ALM subproblem. After applying low-rank factorization in the subproblem, its feasible region becomes an algebraic variety with favorable geometric properties. We make the crucial step to equivalently reformulate most of the quadratic constraints in the factorized model into fewer and more manageable affine constraints. Moreover, we show that the retraction operation, which is the metric projection onto the variety, although non-convex, can be computed efficiently through an equivalent convex reformulation under certain regularity conditions. Numerous numerical experiments will be presented to validate the efficiency of the proposed algorithm. [This talk is based mainly on joint work with Di Hou and Tianyun Tang].