学术报告报告题目: Recent advances on algorithms for solving doubly nonnegative relaxations of mixed-binary quadratic programs
报 告 人: Kim-Chuan Toh 教授
报告时间: 2025年8月18日（星期一）9:00-12:00
地 点：37号楼3A02
邀 请 人: 潘少华教授
欢迎广大师生前往！
数学学院
2025年8月6日
报告摘要：
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].
报告人简介：
Kim-Chuan Toh is a Provost’s Chair Professor in the Department of Mathematics at the National University of Singapore.He works extensively on convex programming, particularly large-scale matrix optimization problems such as semidefinite programming, and optimization problems arising from machine learning and statistics.Currently he serves as a co-Editor for Mathematical Programming, an Area Editor for Mathematical Programming Computation,an Associate Editor for SIAM J. on Optimization, Operations Research, and ACM Transactions on Mathematical Software.He received the INFORMS Optimization Society Farkas Prize in 2017, the triennial Mathematical Optimization Society Beale-Orchard Hays Prize in 2018 and Paul Tseng Memorial Lectureship in 2024, respectively.He is a Fellow of SIAM and a Fellow of the Singapore National Academy of Science.