Cones
Introduction
Let $\mathbb{F}$ be an ordered field; the default is that $\mathbb{F}=\mathbb{Q}$ is the field of rational numbers.
A set $C \subseteq \mathbb{F}^n$ is called a (polyhedral) cone if it can be written as the set of non-negative linear combinations of finitely many vectors in $\mathbb{F}^n$. Equivalently, cones can be written as the intersection of finitely many homogeneous linear inequalities.
Any cone is a special case of a polyhedron. Conversely, intersecting a cone with a suitable affine hyperplane yields a polyhedron whose faces are in bijection with the faces of the cone. Going back and forth between polyhedra and their homogenizations, the cones, is a frequent operation. This is one reason for keeping cones as a distinct type.
Construction
positive_hull
— Methodpositive_hull([::Union{Type{T}, Field} = QQFieldElem,] R::AbstractCollection[RayVector] [, L::AbstractCollection[RayVector]]; non_redundant::Bool = false) where T<:scalar_types
A polyhedral cone, not necessarily pointed, defined by the positive hull of the rays R
, with lineality given by L
. The first argument either specifies the Type
of its coefficients or their parent Field
.
R
is given row-wise as representative vectors, with lineality generated by the rows of L
, i.e. the cone consists of all positive linear combinations of the rows of R
plus all linear combinations of the rows of L
.
This is an interior description, analogous to the $V$-representation of a polytope.
Redundant rays are allowed.
Examples
To construct the positive orthant as a Cone
, you can write:
julia> R = [1 0; 0 1];
julia> PO = positive_hull(R)
Polyhedral cone in ambient dimension 2
To obtain the upper half-space of the plane:
julia> R = [0 1];
julia> L = [1 0];
julia> HS = positive_hull(R, L)
Polyhedral cone in ambient dimension 2
cone_from_inequalities
— Functioncone_from_inequalities([::Union{Type{T}, Field} = QQFieldElem,] I::AbstractCollection[LinearHalfspace] [, E::AbstractCollection[LinearHyperplane]]; non_redundant::Bool = false)
The (convex) cone defined by
\[\{ x | Ix ≤ 0, Ex = 0 \}.\]
Use non_redundant = true
if the given description contains no redundant rows to avoid unnecessary redundancy checks. The first argument either specifies the Type
of its coefficients or their parent Field
.
Examples
julia> C = cone_from_inequalities([0 -1; -1 1])
Polyhedral cone in ambient dimension 2
julia> rays(C)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[1, 1]
cone_from_equations
— Functioncone_from_equations([::Union{Type{T}, Field} = QQFieldElem,] E::AbstractCollection[LinearHyperplane]; non_redundant::Bool = false)
The (convex) cone defined by
\[\{ x | Ex = 0 \}.\]
Use non_redundant = true
if the given description contains no redundant rows to avoid unnecessary redundancy checks. The first argument either specifies the Type
of its coefficients or their parent Field
.
Examples
julia> C = cone_from_equations([1 0 0; 0 -1 1])
Polyhedral cone in ambient dimension 3
julia> lineality_space(C)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
[0, 1, 1]
julia> dim(C)
1
secondary_cone
— Methodsecondary_cone(SOP::SubdivisionOfPoints)
Return the secondary cone of a subdivision of points, the closure of all the weight vectors inducing the given subdivision of points.
Examples
For a non-regular subdivision, the secondary cone can still contain non-trivial weights, but it will not be full-dimensional.
julia> moaepts = [4 0 0; 0 4 0; 0 0 4; 2 1 1; 1 2 1; 1 1 2];
julia> moaeimnonreg0 = IncidenceMatrix([[4,5,6],[1,4,2],[2,4,5],[2,3,5],[3,5,6],[1,3,6],[1,4,6]]);
julia> MOAE = subdivision_of_points(moaepts, moaeimnonreg0)
Subdivision of points in ambient dimension 3
julia> C = secondary_cone(MOAE)
Polyhedral cone in ambient dimension 6
julia> dim(C)
4
Auxiliary functions
ambient_dim
— Methodambient_dim(C::Cone)
Return the ambient dimension of C
.
Examples
The cone C
in this example is 2-dimensional within a 3-dimensional ambient space.
julia> C = positive_hull([1 0 0; 1 1 0; 0 1 0]);
julia> ambient_dim(C)
3
in
— Methodin(v::AbstractVector, C::Cone)
Check whether the vector v
is contained in the cone C
.
Examples
The positive orthant only contains vectors with non-negative entries:
julia> C = positive_hull([1 0; 0 1]);
julia> [1, 2] in C
true
julia> [1, -2] in C
false
issubset
— Methodissubset(C0::Cone, C1::Cone)
Check whether C0
is a subset of the cone C1
.
Examples
julia> C0 = positive_hull([1 1])
Polyhedral cone in ambient dimension 2
julia> C1 = positive_hull([1 0; 0 1])
Polyhedral cone in ambient dimension 2
julia> issubset(C0, C1)
true
julia> issubset(C1, C0)
false
facet_degrees
— Methodfacet_degrees(C::Cone)
Facet degrees of the cone. The degree of a facet is the number of adjacent facets. In particular a general $2$-dimensional cone has two facets (rays) that meet at the origin.
Example
Produce the facet degrees of a cone over a square and a cone over a square pyramid.
julia> c = positive_hull([1 1 0; 1 -1 0; 1 0 1; 1 0 -1])
Polyhedral cone in ambient dimension 3
julia> facet_degrees(c)
4-element Vector{Int64}:
2
2
2
2
julia> c = positive_hull([1 0 1 0; 1 0 -1 0; 1 0 0 1; 1 0 0 -1; 1 1 0 0])
Polyhedral cone in ambient dimension 4
julia> facet_degrees(c)
5-element Vector{Int64}:
4
3
3
3
3
f_vector
— Methodf_vector(C::Cone)
Compute the vector $(f₁,f₂,...,f_{(dim(C)-1))$` where $f_i$ is the number of faces of $C$ of dimension $i$.
Examples
Take the cone over a square, then the f-vector of the cone is the same as of the square.
julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3
julia> f_vector(C)
2-element Vector{ZZRingElem}:
4
4
julia> square = cube(2)
Polytope in ambient dimension 2
julia> f_vector(square)
2-element Vector{ZZRingElem}:
4
4
hilbert_basis
— Methodhilbert_basis(C::Cone{QQFieldElem})
Return the Hilbert basis of a pointed cone C
as the rows of a matrix.
Examples
This (non-smooth) cone in the plane has a hilbert basis with three elements.
julia> C = positive_hull([1 0; 1 2])
A polyhedral cone in ambient dimension 2
julia> matrix(ZZ, hilbert_basis(C))
[1 0]
[1 2]
[1 1]
codim
— Methodcodim(C::Cone)
Return the codimension of C
.
Examples
The cone C
in this example is 2-dimensional within a 3-dimensional ambient space.
julia> C = positive_hull([1 0 0; 1 1 0; 0 1 0]);
julia> codim(C)
1
dim
— Methoddim(C::Cone)
Return the dimension of C
.
Examples
The cone C
in this example is 2-dimensional within a 3-dimensional ambient space.
julia> C = positive_hull([1 0 0; 1 1 0; 0 1 0]);
julia> dim(C)
2
polarize
— Methodpolarize(C::Cone)
Return the polar dual of C
, the cone consisting of all those linear functions that evaluate positively on all of C
.
Examples
julia> C = positive_hull([1 0; -1 2])
Polyhedral cone in ambient dimension 2
julia> Cv = polarize(C)
Polyhedral cone in ambient dimension 2
julia> rays(Cv)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 1//2]
[0, 1]
intersect
— Methodintersect(C::Cone...)
Return the intersection $\bigcap\limits_{c \in C} c$.
Examples
julia> C0 = positive_hull([1 0])
Polyhedral cone in ambient dimension 2
julia> C1 = positive_hull([0 1])
Polyhedral cone in ambient dimension 2
julia> C01 = intersect(C0, C1)
Polyhedral cone in ambient dimension 2
julia> rays(C01)
0-element SubObjectIterator{RayVector{QQFieldElem}}
julia> dim(C01)
0
is_pointed
— Methodis_pointed(C::Cone)
Determine whether C
is pointed, i.e. whether the origin is a face of C
.
Examples
A cone with lineality is not pointed, but a cone only consisting of a single ray is.
julia> C = positive_hull([1 0], [0 1]);
julia> is_pointed(C)
false
julia> C = positive_hull([1 0]);
julia> is_pointed(C)
true
is_fulldimensional
— Methodis_fulldimensional(C::Cone)
Determine whether C
is full-dimensional.
Examples
The cone C
in this example is 2-dimensional within a 3-dimensional ambient space.
julia> C = positive_hull([1 0 0; 1 1 0; 0 1 0]);
julia> is_fulldimensional(C)
false
lineality_dim
— Methodlineality_dim(C::Cone)
Compute the dimension of the lineality space of $C$, i.e. the largest linear subspace contained in $C$.
Examples
A cone is pointed if and only if the dimension of its lineality space is zero.
julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3
julia> is_pointed(C)
true
julia> lineality_dim(C)
0
julia> C1 = positive_hull([1 0],[0 1; 0 -1])
Polyhedral cone in ambient dimension 2
julia> is_pointed(C1)
false
julia> lineality_dim(C1)
1
lineality_space
— Methodlineality_space(C::Cone)
Return a basis of the lineality space of C
.
Examples
Three rays are used here to construct the upper half-plane. Actually, two of these rays point in opposite directions. This gives us a 1-dimensional lineality.
julia> UH = positive_hull([1 0; 0 1; -1 0]);
julia> lineality_space(UH)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
n_facets
— Methodn_facets(C::Cone)
Return the number of facets of a cone C
.
Examples
The cone over a square at height one has four facets.
julia> C = positive_hull([1 0 0; 1 1 0; 1 1 1; 1 0 1])
Polyhedral cone in ambient dimension 3
julia> n_facets(C)
4
n_rays
— Methodn_rays(C::Cone)
Return the number of rays of C
.
Examples
Here a cone is constructed from three rays. Calling number_of_rays
reveals that one of these was redundant:
julia> R = [1 0; 0 1; 0 2];
julia> PO = positive_hull(R);
julia> n_rays(PO)
2
rays
— Methodrays([as::Type{T} = RayVector,] C::Cone)
Return the rays of C
in the format defined by as
. The rays are defined to be the one-dimensional faces, so if C
has lineality, there are no rays.
See also rays_modulo_lineality
.
Optional arguments for as
include
RayVector
.
Examples
Here a cone is constructed from three rays. Calling rays
reveals that one of these was redundant:
julia> R = [1 0; 0 1; 0 2];
julia> PO = positive_hull(R);
julia> rays(PO)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[0, 1]
The rays can also be converted to a matrix using the matrix(ring, ...)
function. If ring=ZZ
the primitive generators of the rays are returned.
julia> R = [1 0; 2 3];
julia> P = positive_hull(R);
julia> rays(P)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[1, 3//2]
julia> matrix(QQ, rays(RayVector, P))
[1 0]
[1 3//2]
julia> matrix(ZZ, rays(P))
[1 0]
[2 3]
A half-space has no rays:
julia> UH = cone_from_inequalities([-1 0 0])
Polyhedral cone in ambient dimension 3
julia> rays(UH)
0-element SubObjectIterator{RayVector{QQFieldElem}}
rays_modulo_lineality
— Methodrays_modulo_lineality(as, C::Cone)
Return the rays of the cone of C
up to lineality as a NamedTuple
with two iterators. If C
has lineality L
, then the iterator rays_modulo_lineality
iterates over representatives of the rays of C/L
. The iterator lineality_basis
gives a basis of the lineality space L
.
See also rays
and lineality_space
.
Examples
For a pointed cone, with two generators, we get the usual rays:
julia> C = positive_hull([1 0; 0 1])
Polyhedral cone in ambient dimension 2
julia> rays(C)
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[0, 1]
julia> RML = rays_modulo_lineality(C)
(rays_modulo_lineality = RayVector{QQFieldElem}[[1, 0], [0, 1]], lineality_basis = RayVector{QQFieldElem}[])
julia> RML.rays_modulo_lineality
2-element SubObjectIterator{RayVector{QQFieldElem}}:
[1, 0]
[0, 1]
julia> RML.lineality_basis
0-element SubObjectIterator{RayVector{QQFieldElem}}
If the cone has lineality, the second iterator iterates over a basis for the space of lineality. The following example has one generator for the positive hull plus one generator for the lineality space:
julia> C = positive_hull([1 0],[0 1])
Polyhedral cone in ambient dimension 2
julia> lineality_dim(C)
1
julia> rays(C)
0-element SubObjectIterator{RayVector{QQFieldElem}}
julia> RML = rays_modulo_lineality(C)
(rays_modulo_lineality = RayVector{QQFieldElem}[[1, 0]], lineality_basis = RayVector{QQFieldElem}[[0, 1]])
julia> RML.lineality_basis
1-element SubObjectIterator{RayVector{QQFieldElem}}:
[0, 1]
ray_degrees
— Methodray_degrees(C::Cone)
Ray degrees of the cone. If the cone has lineality, the output is empty since there are no rays that are also faces.
Examples
julia> c = cone_from_inequalities([-1 0 0; 0 -1 0])
Polyhedral cone in ambient dimension 3
julia> ray_degrees(c)
Int64[]
julia> c = positive_hull([1 0 1 0; 1 0 -1 0; 1 0 0 1; 1 0 0 -1; 1 1 0 0])
Polyhedral cone in ambient dimension 4
julia> ray_degrees(c)
5-element Vector{Int64}:
3
3
3
3
4