勷勤数学•专家报告

题      目：An efficient algorithm for the $\ell_{p}$ norm based metric nearness problem

报  告  人： 王承竞 教授  (邀请人：陈艳男)

                                              西南交通大学

时      间： 9月18日  16：00-17:00

地     点：数科院西楼二楼会议室

报告人简介:

          王承竞，西南交通大学数学学院副教授，于浙江大学数学系取得计算数学博士学位，曾在新加坡国立大学参与博士后研究工作。他长期致力于大规模数值优化的理论、算法和软件研究，曾与人合作针对一类包含甚广的复合优化模型给出了扰动分析中一些重要的等价刻画，并针对一些重要的统计学习问题，如协方差选取大规模半定规划问题、机器学习中的平方根Lasso问题、支持向量机问题、度量学习问题等，进行了算法设计和软件实现。他在Journal of the London Mathematical Society,  Mathematics of Computation, SIAM Journal on Optimization, Journal of Machine Learning Research, IEEE Transactions on Signal Processing等杂志发表了多篇文章。王承竞于2018年入选四川省学术和技术带头人后备人才，现为中国数学会计算数学分会理事。

摘      要：

           Given a dissimilarity matrix, the metric nearness problem is to find the nearest matrix of distances that satisfy the triangle inequalities. This problem has wide applications, such as sensor networks, image processing, and so on. But it is of great challenge even to obtain a moderately accurate solution due to the $O(n^{3})$ metric constraints and the nonsmooth objective function which is usually a weighted $\ell_{p}$ norm based distance. In this paper, we propose a delayed constraint generation method with each subproblem solved by the semismooth Newton based proximal augmented Lagrangian method (PALM) for the metric nearness problem. Due to the high memory requirement for the storage of the matrix related to the metric constraints, we take advantage of the special structure of the matrix and do not need to store the corresponding constraint matrix. A pleasing aspect of our algorithm is that we can solve these problems involving up to $10^{8}$ variables and $10^{13}$ constraints. Numerical experiments demonstrate the efficiency of our algorithm.  In theory, firstly, under a mild condition, we establish a primal-dual error bound condition which is very essential for the analysis of local convergence rate of PALM. Secondly, we prove the equivalence between the dual nondegeneracy condition and nonsingularity of the generalized Jacobian for the inner subproblem of PALM. Thirdly, when $q(\cdot)=\|\cdot\|_{1}$ or $\|\cdot\|_{\infty}$, without the strict complementarity condition, we also prove the equivalence between the the dual nondegeneracy condition and the uniqueness of the primal solution.

          欢迎老师、同学们参加、交流！