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 — Method

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

cone_from_inequalities — Function

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]

cone_from_equations — Function

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

secondary_cone — Method

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 = incidence_matrix([[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 — Method

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

in — Method

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

issubset — Method

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

facet_degrees — Method

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.

Examples

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

facets — Method

facets(as::Type{T} = LinearHalfspace, C::Cone)

Return the facets of C in the format defined by as.

The allowed values for as are

Halfspace (or its subtype LinearHalfspace),
Hyperplane (or its subtype `LinearHyperplane1),
Cone.

Examples

julia> c = positive_hull([1 0 0; 0 1 0; 1 1 1])
Polyhedral cone in ambient dimension 3

julia> f = facets(Halfspace, c)
3-element SubObjectIterator{LinearHalfspace{QQFieldElem}} over the halfspaces of R^3 described by:
-x_3 <= 0
-x_1 + x_3 <= 0
-x_2 + x_3 <= 0

f_vector — Method

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

hilbert_basis — Method

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]

codim — Method

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

dim — Method

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

polarize — Method

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]

intersect — Method

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

is_pointed — Method

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

is_fulldimensional — Method

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

lineality_dim — Method

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

lineality_space — Method

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]

n_facets — Method

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

n_rays — Method

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

rays — Method

rays([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 — Method

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.

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 — Method

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