Cones

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([::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([::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(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

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(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(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(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(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(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(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(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(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(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(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(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(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(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(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(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([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(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(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