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_hullMethod
positive_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
source
cone_from_inequalitiesFunction
cone_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]
source
cone_from_equationsFunction
cone_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
source
secondary_coneMethod
secondary_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
source

Auxiliary functions

ambient_dimMethod
ambient_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
source
inMethod
in(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
source
issubsetMethod
issubset(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
source
facet_degreesMethod
facet_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
source
f_vectorMethod
f_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
source
hilbert_basisMethod
hilbert_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]
source
codimMethod
codim(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
source
dimMethod
dim(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
source
polarizeMethod
polarize(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]
source
intersectMethod
intersect(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
source
is_pointedMethod
is_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
source
is_fulldimensionalMethod
is_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
source
lineality_dimMethod
lineality_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
source
lineality_spaceMethod
lineality_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]
source
n_facetsMethod
n_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
source
n_raysMethod
n_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
source
raysMethod
rays(C::Cone)

Return the rays of C.

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(P))
[1      0]
[1   3//2]

julia> matrix(ZZ, rays(P))
[1   0]
[2   3]
source
rays_modulo_linealityMethod
rays_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.

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]
source
ray_degreesMethod
ray_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
source