minimumvolume

Minimumvolume refers to problems in geometry and optimization that seek the smallest possible volume of a geometric object that contains a given set of points or satisfies certain containment constraints. The most common instance is the minimum-volume enclosing ellipsoid (MVEE), also known as the Loewner–John ellipsoid, which is the ellipsoid of smallest volume that contains a finite set of points in Euclidean space.

Formulation and mathematics: For a data set {x_i} in R^d, the goal is to find a center c in R^d and a positive definite matrix A in R^{d×d} such that the ellipsoid E(c,A) = {x : (x − c)^T A (x − c) ≤ 1} contains all points. The ellipsoid’s volume is proportional to det(A)^{-1/2}, so the MVEE problem can be stated as maximizing det(A) subject to (x_i − c)^T A (x_i − c) ≤ 1 for all i. Equivalently, one can minimize log det(A^{-1}) under the same constraints. The optimal pair (c*, A*) defines the MVEE, with principal radii related to the eigenvalues of A*.

Algorithms and complexity: MVEE can be computed via convex optimization. Classical methods include Khachiyan’s algorithm, an iterative, polynomial-time procedure, and interior-point methods that are effective for moderate to large datasets. Variants address numerical stability, high dimensionality, or streaming data.

Applications and related concepts: MVEE is used in data analysis for outlier detection, robust shape description, data visualization, computer vision, and machine learning. Related notions include minimum-volume sets in statistics and other minimum enclosing shapes such as the minimum enclosing ball. The concept connects to broader themes in convex optimization and geometric approximation.