学校地图 | 网站地图 | ENGLISH
首页学校概况机构设置学科建设人才招聘招生就业数字校园校长信箱校友网
首页
 校园新闻 
 通知公告 
 学术交流 
 网站地图 
 院部动态 
数学科学学院
当前位置: 首页>>学术交流>>数学科学学院>>正文
ChebyshevCenter of the Intersection of Balls: Complexity, Relaxation andApproximation
2017-12-15 17:16     (点击次数:)

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

报告时间:20171217日(本周日)上午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》编委。

关闭窗口
 

版权所有 河南科技学院 河南省新乡市华兰大道东段 453003

豫公网安备 41070202000140号 工信部备案:豫ICP备05002482