Improved Conic Reformulations for $K$-means Clustering

DOI10.1137/17M1135724zbMath1408.90237arXiv1706.07105MaRDI QIDQ4555446

Madhushini Narayana Prasad, Grani A. Hanasusanto

Publication date: 20 November 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.07105

zbMATH Keywords

semidefinite programming; copositive programming; \(K\)-means; conic programming

Mathematics Subject Classification ID

90C22: Semidefinite programming

90C25: Convex programming

90C26: Nonconvex programming, global optimization

Related Items

Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming, The Ratio-Cut Polytope and K-Means Clustering, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem

Uses Software

• YALMIP
• clusfind

Cites Work

• Unnamed Item
• Unnamed Item
• Representing quadratically constrained quadratic programs as generalized copositive programs
• NP-hardness of Euclidean sum-of-squares clustering
• Cluster analysis and mathematical programming
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Approximation of the Stability Number of a Graph via Copositive Programming
• Copositive Programming
• Relax, No Need to Round
• Convexity in SemiAlgebraic Geometry and Polynomial Optimization
• Finding Groups in Data
• Clustering subgaussian mixtures by semidefinite programming
• Least squares quantization in PCM
• Approximating K‐means‐type Clustering via Semidefinite Programming
• On Cones of Nonnegative Quadratic Functions