| is.inCHv3.9 {mlergm} | R Documentation |
Determine whether a vector is in the closure of the convex hull of some sample of vectors
Description
is.inCH returns TRUE if and only if p is contained in
the convex hull of the points given as the rows of M. If p is
a matrix, each row is tested individually, and TRUE is returned if
all rows are in the convex hull.
Usage
is.inCHv3.9(p, M, verbose = FALSE, ...)
Arguments
p |
A |
M |
An |
verbose |
A logical vector indicating whether to print progress |
... |
arguments passed directly to linear program solver |
Details
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 \le 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) \le 0 and x \ge 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 \le 1.
This function is used in the "stepping" algorithm of Hummel et al (2012).
Value
Logical, telling whether p is (or all rows of p are)
in the closed convex hull of the points in M.
References
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.