577. Spatial branch-and-bound methods for solving the k-Hyperplane clustering
Invited abstract in session WC-4: Large Scale Optimization for Statistical Learning, stream Optimization for machine learning.
Wednesday, 14:00-16:00Room: B100/5013
Authors (first author is the speaker)
| 1. | Stefano Coniglio
|
| Department of Economics, University of Bergamo | |
| 2. | Montree Jaidee
|
| Mathematical Sciences, University of Southampton |
Abstract
We address the k-Hyperplane Clustering problem, which consists in finding k hyperplanes that minimize the sum, over all data points, of squared Euclidean (2-norm) distances to their closest hyperplanes.
We propose two algorithms that solve this problem to global optimality, both grounded in spatial-branch-and-bound (SBB) techniques.
In the first algorithm, we strengthen a basic mixed integer quadratically-constrained quadratic-programming (MIQCQP) formulation with additional constraints derived from p-norm formulations of the problem defined for values of p different from 2.
The second algorithm introduces a problem-specific branching scheme, where the infeasible regions of the problem (complements of Euclidean balls) are approximated by a polyhedron whose vertex set becomes increasingly rich as branching progresses.
Experimental results demonstrate that both approaches substantially improve the problem’s solvability to global optimality.
Keywords
- Nonlinear mixed integer optimization
- Global optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers