A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming
Abstract
Extending the classical K-means and K-medians models, this paper introduces an ℓp,q mixed-norm clustering model where the centroid updates and cluster assignments are under the ℓp and ℓq norms, respectively. The model is formulated as a mixed-integer program (MIP) with Heaviside composite constraints that describe the nearest-center assignments. The framework recovers K-means and K-medians when p=q=2 and p=q=1, respectively, and yields new models when p≠ q. To address the computational challenges, we develop a progressive integer programming (PIP) method that adaptively fixes confident assignments and solves restricted mixed-integer subproblems. For q=1, we develop a convex inner approximation of the difference-of-convex constraints in the restricted subproblems, for which a global solution can be computed. Importantly, we establish the connection between the local minimizer and the strong center-local minimizer of the mixed-norm clustering problem and the global optimal solution of the restricted subproblems under certain assumptions. This connection provides a practical certificate of a local minimizer of the nonconvex mixed-norm clustering model. We further develop techniques for constructing adaptive fixing sets and working sets for q=1. Extensive numerical experiments demonstrate the superior performance of the mixed-norm clustering model and the efficiency of PIP for solving the MIP model, which may be intractable otherwise. In particular, the ℓ2,1 mixed-norm clustering model is effective under coordinate-sparse, mean-balanced contamination, whereas the ℓ1,2 model is preferred under dense coordinatewise Cauchy contamination. The numerical results also show that PIP can escape poor alternating solutions and obtain substantially better feasible clustering, while preserving strong warm starts when no improvement is found.
Related
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- Accelerated Benders decomposition for bi-objective mixed integer programming
BibTeX
@misc{liu2026perspective,
title = {{A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming}},
author = {Junyi Liu and Yulin Peng and Yao Xie and Yancheng Yuan and Jong-Shi Pang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08002},
eprint = {2609.08002},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08002},
}
RIS
TY - UNPB
TI - A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming
AU - Junyi Liu
AU - Yulin Peng
AU - Yao Xie
AU - Yancheng Yuan
AU - Jong-Shi Pang
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.08002
UR - https://arxiv.org/abs/2609.08002
AB - Extending the classical K-means and K-medians models, this paper introduces an ℓ_p,q mixed-norm clustering model where the centroid updates and cluster assignments are under the ℓ_p and ℓ_q norms, respectively. The model is formulated as a mixed-integer program (MIP) with Heaviside composite constraints that describe the nearest-center assignments. The framework recovers K-means and K-medians when p=q=2 and p=q=1, respectively, and yields new models when p≠ q. To address the computational challenges, we develop a progressive integer programming (PIP) method that adaptively fixes confident assignments and solves restricted mixed-integer subproblems. For q=1, we develop a convex inner approximation of the difference-of-convex constraints in the restricted subproblems, for which a global solution can be computed. Importantly, we establish the connection between the local minimizer and the strong center-local minimizer of the mixed-norm clustering problem and the global optimal solution of the restricted subproblems under certain assumptions. This connection provides a practical certificate of a local minimizer of the nonconvex mixed-norm clustering model. We further develop techniques for constructing adaptive fixing sets and working sets for q=1. Extensive numerical experiments demonstrate the superior performance of the mixed-norm clustering model and the efficiency of PIP for solving the MIP model, which may be intractable otherwise. In particular, the ℓ_2,1 mixed-norm clustering model is effective under coordinate-sparse, mean-balanced contamination, whereas the ℓ_1,2 model is preferred under dense coordinatewise Cauchy contamination. The numerical results also show that PIP can escape poor alternating solutions and obtain substantially better feasible clustering, while preserving strong warm starts when no improvement is found.
ER -