List all the nonempty faces of a convex polyhedron, giving for each the dimension, the active set of constraints, and a relative interior point.
allfaces(hrep)a list containing the following components:
list of integers giving the dimensions of the faces.
list of integer vectors giving for each face the
set of constraints that are active (satisfied with equality) on
the face, the integers referring to row numbers of hrep.
list of double or character vectors
(same type as hrep)
giving a point in the relative interior of each face.
H-representation of convex polyhedron (see details).
The argument hrep may
have type "character" in which case its elements are interpreted
as unlimited precision rational numbers. They consist of an optional
minus sign, a string of digits of any length (the numerator),
a slash, and another string of digits of any length (the denominator).
The denominator must be positive. If the denominator is one, the
slash and the denominator may be omitted. This package
provides several functions (see ConvertGMP and ArithmeticGMP)
for conversion back and forth between R floating point numbers and rationals
and for arithmetic on GMP rationals.
If you want correct answers, use rational arithmetic. If you do not,
this function may (1) produce approximately correct answers, (2) fail with
an error, (3) give answers that are nowhere near correct with no error or
warning, or (4) crash R losing all work done to that point. In large
simulations (1) is most frequent, (2) occurs roughly one time in a thousand,
(3) occurs roughly one time in ten thousand, and (4) has only occurred once
and only with the redundant function. So the R floating point
arithmetic version does mostly work, but you cannot trust its results unless
you can check them independently.
See cddlibman.pdf in the doc directory of this package,
especially Sections 1 and 2.
This function lists all nonempty faces of a convex polyhedron
given by the H-representation given by the matrix hrep.
Let
l <- hrep[ , 1]
b <- hrep[ , 2]
v <- hrep[ , - c(1, 2)]
a <- (- v)
Then the convex polyhedron in question is the set of
points x satisfying
axb <- a %*% x - b
all(axb <= 0)
all(l * axb == 0)
A nonempty face of a convex polyhedron \(P\) is the subset of \(P\) that is the set of points over which some linear function achieves its maximum over \(P\). Note that \(P\) is a face of \(P\) and appears in the list of faces. By definition the empty set is also a face, but is not listed. These two faces are said to be improper, the other faces are proper.
A face in the listing is characterized by the set of constraints that are active, i. e., satisfied with equality, on the face.
The relative interior of a convex set its its interior considered as a subset of its affine hull. The relative interior of a one-point set is that point. The relative interior of a multi-point convex set is the union of open line segments \((x, y)\) with endpoints \(x\) and \(y\) in the set.
scdd, ArithmeticGMP,
ConvertGMP
hrep <- rbind(c(0, 1, 1, 1, -1),
c(0, 1, 1, -1, -1),
c(0, 1, -1, -1, -1),
c(0, 1, -1, 1, -1),
c(0, 0, 0, 0, 1))
allfaces(d2q(hrep))
Run the code above in your browser using DataLab