| is.inCH {ergm} | R Documentation |
is.inCH returns TRUE if and only if
p is contained in the convex hull of the points given as
the rows of M.
is.inCH(p, M, ...)
p |
A d-dimensional vector |
M |
An r by d matrix. Each row of |
... |
arguments passed directly to linear program solver |
The d-vector p is in the convex hull of the d-vectors
forming the rows of M if and only if there exists no separating
hyperplane between p and the rows of M. This condition
may be reworded as follows:
Letting q=(1 p')' and L = (1 M), if the maximum value of
z'q for all z such that z'L ≤ 0 equals zero
(the maximum must be at least zero since z=0 gives zero), then there is no
separating hyperplane and so p is contained in the convex hull
of the rows of M. So the question of interest becomes a
constrained optimization problem.
Solving this problem relies on the package lpSolve to solve
a linear program. We may put the program in "standard form" by
writing z=a-b, where a and b are nonnegative
vectors. If we write x=(a' b')', we obtain the linear program
given by:
Minimize (-q' q')x subject to x'(L -L) ≤ 0 and x ≥ 0. One additional constraint arises because whenever any strictly negative value of (-q' q')x may be achieved, doubling x arbitrarily many times makes this value arbitrarily large in the negative direction, so no minimizer exists. Therefore, we add the constraint (q' -q')x ≤ 1.
This function is used in the "stepping" algorithm of Hummel et al (2012).
Logical, telling whether p is in the closed convex hull of the points
in M.
Hummel, R. M., Hunter, D. R., and Handcock, M. S. (2012), Improving Simulation-Based Algorithms for Fitting ERGMs, Journal of Computational and Graphical Statistics, 21: 920-939.