In
convex geometry
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of num ...
and
polyhedral combinatorics
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
Research in polyhedral co ...
, the extension complexity of a
convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
is the smallest number of
facets among convex polytopes
that have
as a projection. In this context,
is called an extended formulation of
; it may have much higher dimension than
.
The extension complexity depends on the precise shape of
, not just on its combinatorial structure. For instance,
regular polygon
In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...
s with
sides have extension complexity
(expressed using
big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
), but some other convex
-gons have extension complexity at least proportional to
.
If a polytope describing the feasible solutions to a
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way. For instance, it is known that the
matching polytope
In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the the ...
has exponential extension complexity. On the other hand, the
independence polytope of
regular matroids has polynomial extension complexity.
The notion of extension complexity has also been generalized from linear programming to
semidefinite programming
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of po ...
, by considering projections of
spectrahedra in place of projections of polytopes.
References
Polyhedral combinatorics
{{geometry-stub