is.inCHv3.9 function

Determine whether a vector is in the closure of the convex hull of some sample of vectors

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.inCHv3.9(p, M, verbose = FALSE, ...)

Arguments

• p: A $d$-dimensional vector or a matrix with $d$ columns
• M: An $r$ by $d$ matrix. Each row of M is a $d$-dimensional vector.
• verbose: A logical vector indicating whether to print progress
• ...: arguments passed directly to linear program solver

Returns

Logical, telling whether p is (or all rows of p are) in the closed convex hull of the points in M.

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 c("$x=(a'\n$", "$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).

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.