Improved Conic Reformulations for $K$-means Clustering

DOI10.1137/17M1135724zbMath1408.90237arXiv1706.07105OpenAlexW2899810529MaRDI 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 programmingcopositive programming\(K\)-meansconic programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Nonconvex programming, global optimization (90C26)

Related Items (5)

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

This page was built for publication: Improved Conic Reformulations for $K$-means Clustering