题　目：On the power of sparse cuts

嘉　宾：Nan Jiang , Assistant Professor, Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology

主持人：葛冬冬，教授，上海交通大学安泰经济与管理学院

时　间：2026年3月9日（周一）14:00-15:30

地　点：上海交通大学徐汇校区安泰浩然楼308室

内容简介:

In this talk, we introduce and analyze a class of valid inequalities for nonconvex quadratically constrained optimization problems (QCQPs) which we call Eigen-CG inequalities. These inequalities are obtained by applying a Chvátal--Gomory (CG) rounding to the well-known eigenvector inequalities for QCQPs, and transferring binary-valid inequalities to the continuous setting via a result of Burer and Letchford (2009). We define three nested subfamilies and prove that they are strictly contained in one another. However, we show that the convex conic closure of two of these subfamilies is equal and, in fact, coincides with the Boros--Hammer inequalities---a powerful family of inequalities that include, in particular, the triangle and McCormick inequalities. Using this CG perspective, we also prove that dense Eigen-CG inequalities are ineffective when used with the standard SDP+McCormick relaxation. This provides a complementary perspective on what is observed in practice: that sparse inequalities are impactful. Finally, based on these insights, we develop a computational strategy to find sparse Eigen-CG cuts and verify their effectiveness in nonconvex QCQP instances. Our results confirm that density quickly degrades effectiveness, but that including sparse inequalities beyond triangle inequalities can provide significant improvements in dual bounds.

演讲人简介：

Nan Jiang is an Assistant Professor in the Department of Industrial Engineering and Decision Analytics (IEDA) at the Hong Kong University of Science and Technology (HKUST). Before joining HKUST, he was a postdoc at Cornell Tech. He received his Ph.D. in Operations Research from the School of Industrial and Systems Engineering at Georgia Tech. He is interested in developing new methods or algorithms for decision-making under uncertainty.

欢迎广大师生参加!