MAP Clustering under the Gaussian Mixture Model via Mixed Integer Nonlinear Optimization
This work addresses clustering with side constraints for applications like bioinformatics, though it is incremental as it builds on existing optimization frameworks.
The paper tackles the MAP clustering problem under the Gaussian mixture model by formulating it as a mixed-integer nonlinear optimization problem, achieving ε-global optimality with explicit suboptimality quantification and showing better solutions than standard methods in numerical experiments.
We present a global optimization approach for solving the maximum a-posteriori (MAP) clustering problem under the Gaussian mixture model.Our approach can accommodate side constraints and it preserves the combinatorial structure of the MAP clustering problem by formulating it asa mixed-integer nonlinear optimization problem (MINLP). We approximate the MINLP through a mixed-integer quadratic program (MIQP) transformation that improves computational aspects while guaranteeing $ε$-global optimality. An important benefit of our approach is the explicit quantification of the degree of suboptimality, via the optimality gap, en route to finding the globally optimal MAP clustering. Numerical experiments comparing our method to other approaches show that our method finds a better solution than standard clustering methods. Finally, we cluster a real breast cancer gene expression data set incorporating intrinsic subtype information; the induced constraints substantially improve the computational performance and produce more coherent and bio-logically meaningful clusters.