find_inside function

Find a Point/Parameter Vector Within a Convex Polytope

Finds the center/a random point that is within the convex polytope defined by the linear inequalities A*x <= b or by the convex hull over the vertices in the matrix V.

find_inside(
  A,
  b,
  V,
  options = NULL,
  random = FALSE,
  probs = TRUE,
  boundary = 1e-05
)

Arguments

• A: a matrix with one row for each linear inequality constraint and one column for each of the free parameters. The parameter space is defined as all probabilities x that fulfill the order constraints A*x <= b.
• b: a vector of the same length as the number of rows of A.
• V: a matrix of vertices (one per row) that define the polytope of admissible parameters as the convex hull over these points (if provided, A and b are ignored). Similar as for A, columns of V omit the last value for each multinomial condition (e.g., a1,a2,a3,b1,b2 becomes a1,a2,b1). Note that this method is comparatively slow since it solves linear-programming problems to test whether a point is inside a polytope (Fukuda, 2004) or to run the Gibbs sampler.
• options: optional: number of options per item type (only for $A x \leq b$ representation). Necessary to account for sum-to-one constraints within multinomial distributions (e.g., p_1 + p_2 + p_3 <= 1). By default, parameters are assumed to be independent.
• random: if TRUE, random starting values in the interior are generated. If FALSE, the center of the polytope is computed using linear programming.
• probs: only for A*x<b representation: whether to add inequality constraints that the variables are probabilities (nonnegative and sum to 1 within each option)
• boundary: constant value $c$ that is subtracted on the right-hand side of the order constraints, $A x \leq b - c$. This ensuresa that the resulting point is in the interior of the polytope and not at the boundary, which is important for MCMC sampling.

Details

If vertices V are provided, a convex combination of the vertices is returned. If random=TRUE, the weights are drawn uniformly from a Dirichlet distribution.

If inequalities are provided via A and b, linear programming (LP) is used to find the Chebyshev center of the polytope (i.e., the center of the largest ball that fits into the polytope; the solution may not be unique). If random=TRUE, LP is used to find a random point (not uniformly sampled!) in the convex polytope.

Examples

# inequality representation (A*x <= b)
A <- matrix(
  c(
    1, -1, 0, 1, 0,
    0, 0, -1, 0, 1,
    0, 0, 0, 1, -1,
    1, 1, 1, 1, 0,
    1, 1, 1, 0, 0,
    -1, 0, 0, 0, 0
  ),
  ncol = 5, byrow = TRUE
)
b <- c(0.5, 0, 0, .7, .4, -.2)
find_inside(A, b)
find_inside(A, b, random = TRUE)

# vertex representation
V <- matrix(c(
  # strict weak orders
  0, 1, 0, 1, 0, 1, # a < b < c
  1, 0, 0, 1, 0, 1, # b < a < c
  0, 1, 0, 1, 1, 0, # a < c < b
  0, 1, 1, 0, 1, 0, # c < a < b
  1, 0, 1, 0, 1, 0, # c < b < a
  1, 0, 1, 0, 0, 1, # b < c < a

  0, 0, 0, 1, 0, 1, # a ~ b < c
  0, 1, 0, 0, 1, 0, # a ~ c < b
  1, 0, 1, 0, 0, 0, # c ~ b < a
  0, 1, 0, 1, 0, 0, # a < b ~ c
  1, 0, 0, 0, 0, 1, # b < a ~ c
  0, 0, 1, 0, 1, 0, # c < a ~ b

  0, 0, 0, 0, 0, 0 # a ~ b ~ c
), byrow = TRUE, ncol = 6)
find_inside(V = V)
find_inside(V = V, random = TRUE)