新萄京官网 旧版新闻网 ENGLISH IHome

数学科学学院夏勇教授团队在数学优化知名期刊Mathematical Programming发表研究成果

点击数:    |    加入时间:2020-03-17

新萄京新闻网3月17日电(通讯员 李田田)日前,新萄京数学科学学院夏勇教授、2015级博士生杨美佳、2014级博士生王姝,在凸几何计算领域取得重要进展。研究成果“Chebyshev Center of the Intersection of Balls: Complexity, Relaxation and Approximation”在国际期刊《Mathematical Programming》在线发表,该期刊为数学优化领域知名期刊,2018年影响因子为3.785。(论文链接:https://doi.org/10.1007/s10107-020-01479-0)

点击图片查看论文

该问题可追溯到英国著名数学家、皇家学会会员Sylvester,他于1857年提出平面上有限多个点的最小圆覆盖问题,即寻找这有限个点的切比雪夫中心,推而广之的问题是对一些凸集寻找其切比雪夫中心。寻找n维空间p个球的交集的切比雪夫中心问题由著名优化专家、FISTA提出者、以色列理工学院Beck教授2007年提出,在鲁棒估计、无线网络通信、控制、优化等领域有重要应用。如下图示为一个n=2,p=3的例子,黄色圆为覆盖红色区域的最小圆。

Beck教授2007年通过对偶松弛提出该问题的标准二次规划近似方法,并证明当p≤n-1时,该近似是精确的。2009年Beck教授将该充分条件进一步放松成p≤n。

夏勇教授课题组对该问题进行了深入的研究,并取得了重要成果。证明了该问题是NP-hard;首次理论分析了p>n的情形,证明了p-n固定或者n固定时,该问题是多项式可解;此外,首次证明了Beck教授建立的标准二次规划近似方法存在一个渐近为2的近似比(近似比为2意指近似解的函数值不超过精确最小值的2倍)。

该项工作得到国家自然科学基金优秀青年科学基金、面上项目、青年基金资助,也得到澳门市自然科学基金重点项目资助。

(审核:袁星)

编辑:贾爱平

更多新闻
07 月
10
07 月
07
07 月
07
07 月
05
07 月
05
新萄京重庆校友会换届大会举行

点击数:
加入时间:2020-07-05
07 月
03
XML 地图 | Sitemap 地图