版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Univ Texas Austin Grad Program Operat Res & Ind Engn Austin TX 78712 USA
出 版 物:《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)
年 卷 期:2018年第28卷第4期
页 面:3105-3126页
核心收录:
学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金:National Science Foundation Directorate For Engineering Div Of Electrical, Commun & Cyber Sys Funding Source: National Science Foundation
主 题:semidefinite programming K-means conic programming copositive programming
摘 要:In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing schemes, our proposed SDP formulation gives rise to solutions that can be leveraged to identify the clusters. We devise a new approximation algorithm for K-means clustering that utilizes the improved formulation and empirically illustrate its superiority over the state-of-the-art solution schemes.