find_inside {multinomineq}

Find a Point/Parameter Vector Within a Convex Polytope

Description

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.

Usage

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)