allfaces | R Documentation |
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)
hrep |
H-representation of convex polyhedron (see details). |
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.
a list containing the following components:
dimension |
list of integers giving the dimensions of the faces. |
active.set |
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 |
relative.interior.point |
list of double or character vectors
(same type as |
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.
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))
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.