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 dd-dimensional vector or a matrix with dd columns

M

An rr by dd matrix. Each row of M is a dd-dimensional vector.

verbose

A logical vector indicating whether to print progress

...

arguments passed directly to linear program solver

Details

The dd-vector p is in the convex hull of the dd-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=(1p)q=(1 p')' and L=(1M)L = (1 M), if the maximum value of zqz'q for all zz such that zL0z'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=abz=a-b, where aa and bb are nonnegative vectors. If we write x=(ab)x=(a' b')', we obtain the linear program given by:

Minimize (qq)x(-q' q')x subject to x(LL)0x'(L -L) \le 0 and x0x \ge 0. One additional constraint arises because whenever any strictly negative value of (qq)x(-q' q')x may be achieved, doubling xx arbitrarily many times makes this value arbitrarily large in the negative direction, so no minimizer exists. Therefore, we add the constraint (qq)x1(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


[Package mlergm version 0.8 Index]