Nesterov’s smoothing technique and minimizing differences of convex functions for hierarchical clustering
Nesterov’s smoothing technique and minimizing differences of convex functions for hierarchical clustering
复制标题
Nesterov 的平滑技术和最小化层次聚类凸函数的差异
作者：
N. M. Nam;W. Geremew;S. Reynolds;T. Tran
两级分层聚类模型通常用于设计最佳多播网络。在本文中，我们考虑两个不同的配方的双层层次聚类问题，离散优化问题，可以被证明是NP-难的。我们的方法是通过对离散条件进行一些放松，将问题转化为连续优化问题。然后Nesterov的光滑技术和一个数值算法的凸函数称为DCA的差异最小化，以科普的非光滑性和非凸性的问题。数值例子来说明我们的方法。
A bilevel hierarchical clustering model is commonly used in designing optimal multicast networks. In this paper, we consider two different formulations of the bilevel hierarchical clustering problem, a discrete optimization problem which can be shown to be NP-hard. Our approach is to reformulate the problem as a continuous optimization problem by making some relaxations on the discreteness conditions. Then Nesterov’s smoothing technique and a numerical algorithm for minimizing differences of convex functions called the DCA are applied to cope with the nonsmoothness and nonconvexity of the problem. Numerical examples are provided to illustrate our method.