Löwner-John Polyellipsoid Problem: On the Location of Foci
Given a finite set of foci in a metric space and a nonnegative radius R, a polyellipsoid is the set of points whose sum of distances to the foci is at most R. In this on-going work, we address the following generalization of the Löwner-John ellipsoid problem. Given a (non necessarily convex) compact set K and a positive integer n, find a polyellipsoid of n foci that has minimum volume among all containing K. For that aim, first we (abstractly) model the problem as a sort of continuous location problem where the "facilities" to be placed become the foci. Thereby, the continuous decision variables are the coordinates of the n foci together with the radius (note these decisions determine the polyellipsoid). Considering the finite-dimensional euclidean space endowed with a Hölder norm, we work from such ethereal minimum-volume enclosing problem to an exact (or relaxed) conic reformulation that leads to a tractable approach useful in pattern separation and one-class classification.
Palabras clave: Löwner-John Problem Minimum-Volume Enclosing Problems Convex Optimization Pattern Separation One-Class Classification Location Science Machine Learning