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.
is.inCH(p, M, verbose=FALSE, …)A \(d\)-dimensional vector or a matrix with \(d\) columns
An \(r\) by \(d\) matrix. Each row of M is a
\(d\)-dimensional vector.
A logical vector indicating whether to print progress
arguments passed directly to linear program solver
Logical, telling whether p is (or all rows of p are) in the closed convex hull of the points
in M.
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).
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.