首页  > 学术科研 > 信息与计算科学系

学术报告:A Fast Matrix Majorization-Projection Method for Constrained Stress Minimization in MDS

来源:信息与计算科学系  作者:王承竞     日期:2017/12/6 13:28:41   点击数:577  


报告题目:A Fast Matrix Majorization-Projection Method for Constrained Stress Minimization in MDS

报告人:戚厚铎 教授 (南安普顿大学)







Kruskal's stress minimization, though nonconvex and nonsmooth, has been amajor computational model for dissimilarity data in multidimensional scaling. Semidefinite Programming (SDP) relaxation (by dropping the rank constraint) would lead to a high number of SDP cone constraints. This has rendered the SDP approach computationally challenging even for problems of small size. In this paper, we reformulate the stress as an Euclidean Distance Matrix (EDM) optimization with box constraints. A key element in our approach is the conditional positive semidefinite cone with rank cut. Although nonconvex, this geometric object allows a fast computation of the projection onto it and it naturally leads to a majorization-minimization algorithm with the minimization step having a closed-form solution. Moreover, we prove that our EDM optimization follows a continuously differentiable path, which greatly facilitated the analysis of the convergence to a stationary point. The superior performance of the proposed algorithm is demonstrated against some of the state-of-the-art solvers in the field of sensor network localization.

* This is a joint work with XiuNaihua and Zhou Shenglong



Houduo Qi received the BSc in Statistics from Peking University in 1990, MSc in Operational Research and Optimal Control from Qufu Normal University in 1993, and PhD in Operational Research and Optimal Control from Institute of Applied Mathematics, Chinese Academy of Sciences (CAS) in 1996. From 1996 to 1998, he was a Chinese Postdoctoral Fellow at the Institute of Computational Mathematics, CAS. From 1998 to 2003, he was a research fellow and then the Australian Postdoctoral Fellow respectively at The Hong Kong Polytechnic University and The University of New South Wales. In 2004, he was awarded the prestigious Queen Elizabeth II Fellowship (QEII Fellow) by the Australian Research Council. In September 2004, he joined the University of Southampton (UoS) as a lecturer in Operational Research, rising to Professor and Chair of Optimization at UoS. He is mainly interested in Mathematical Optimization, especially in matrix optimization with applications to finance and statistics. He has been the Area Editor (Optimization) of Asia-Pacific Journal of Operational Research from 2016, Associate Editor for Mathematical Programming Computation (since 2013) and Journal of Operations Research Society of China (since 2016). From 2010, he has been a college member of Engineering and Physical Sciences Research Council, UK.