报告人：夏勇，北京航空航天大学数学与系统科学学院教授、博士生导师

报告时间：2017年12月17日（本周日）上午9:00

报告地点：8号楼303（数学学院会议室）

报告题目：ChebyshevCenter of the Intersection of Balls: Complexity, Relaxation andApproximation



报告摘要：

We study the problem of finding the smallest ball enclosingthe intersection of p given balls, the so-called Chebyshev centerproblem (CC). It is a minimax optimization problem and the innermaximization is a uniform quadratic optimization problem (UQ). Itis known when p is less than or equal to the dimension n, the (UQ) enjoysa strong duality and consequently (CC) is solved via a standard convexquadratic programming (SQP). In this talk, we first prove that (CC) is strongly NP-hard, but polynomially solved when n=2. We propose alinear programming relaxation (LP) for (UQ), which is shown to beequivalent to the semidefinite programming relaxation (SDP) if(SDP) is not tight. With the help of the LP relaxation, we caneasily establish the (SQP) relaxation and get a necessary conditionfor the optimal soluton of (CC). Approximation bound of the (SDP)relaxation for (UQ) is established, which is also extended to analyze thetightness of (SQP) relaxation for (CC). Finally, we provethat either (UQ) or (CC) can be solved in polynomial timewhen n=k or p=n+k with a fixed integer number k.



个人简介：

夏勇，1980年生，北京航空航天大学数学与系统科学学院教授、博士生导师，统计运筹与控制系系主任。2002年北京大学本科毕业获理学学士学位，2007获中国科学院博士研究生毕业获理学博士学位，师从袁亚湘院士。主要研究方向是：非凸全局优化。近几年来，主持国家自然科学基金多项，在《MathematicalProgramming》《SIAM Journal onOptimization》等国内外SCI源刊发表论文近40篇。现为中国运筹学会数学规划分会青年理事，北京运筹学会理事，《MathematicalReview》评论员，《Journal of theOperations Research Society of China》编委。