Python API Documentation

This section contains the Python API documentation for the PolytopeWalk library.

Module: polytopewalk

Polytopewalk Library

class polytopewalk.FROutput

Bases: pybind11_object

Output for Facial Reduction.

property Q

Matrix used to go between forms.

property dense_A

Full-dim form Ax <= b.

property dense_b

Full-dim form Ax <= b.

property saved_V

PAVv = Pb decomposition.

property sparse_A

Constrained form Ax = b, x >=_k 0.

property sparse_b

Constrained form Ax = b, x >=_k 0.

property z1

Vector used to go between forms.

class polytopewalk.FacialReduction(self: polytopewalk.FacialReduction, err_dc: float = 1e-06)

Bases: pybind11_object

Facial Reduction Implementation.

Initialization for Facial Reduction Class.

Parameters:

err_dc (double, optional) – Error sensitivity for decomposition calculation (default is 1e-6).

reduce(self: polytopewalk.FacialReduction, A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, sparse: bool) → FROutput

Completes facial reduction on Ax = b, x >=_k 0.

Parameters:

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of polytope.

  • sparse (bool) – Includes only sparse constrained polytope or adds dense full-dimensional polytope.

Returns:

Facial Reduction results object.

Return type:

FROutput

polytopewalk.denseFullWalkRun(niter: int, A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, walk: RandomWalk, fr: FacialReduction, dc: DenseCenter, burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Dense Central Function. Starts with polytope in sparse, constrained formulation. Computes facial reduction to preprocess polytope and uses the dense, full-dimensional polytope to run MCMC sampler before converting it back into original formulation.

Parameters:

  • niter (int) – Number of iterations.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of the polytope.

  • walk (RandomWalk) – Random walk instance.

  • fr (FacialReduction) – Facial reduction object.

  • dc (DenseCenter) – Dense center object.

  • burnin (int, optional) – Number of burn-in steps (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

polytopewalk.sparseFullWalkRun(niter: int, A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, walk: SparseRandomWalk, fr: FacialReduction, sc: SparseCenter, burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Sparse Central Function. Starts with polytope in sparse, constrained formulation. Computes facial reduction to preprocess polytope and uses the reduced constrained polytope to run MCMC sampler before converting it back into original formulation.

Parameters:

  • niter (int) – Number of iterations.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of the polytope.

  • walk (RandomWalk) – Random walk instance.

  • fr (FacialReduction) – Facial reduction object.

  • sc (SparseCenter) – Sparse center object.

  • burnin (int, optional) – Number of burn-in steps (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

Initialization Classes

class polytopewalk.FacialReduction(self: polytopewalk.FacialReduction, err_dc: float = 1e-06)

Bases: pybind11_object

Facial Reduction Implementation.

Initialization for Facial Reduction Class.

Parameters:

err_dc (double, optional) – Error sensitivity for decomposition calculation (default is 1e-6).

reduce(self: polytopewalk.FacialReduction, A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, sparse: bool) → FROutput

Completes facial reduction on Ax = b, x >=_k 0.

Parameters:

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of polytope.

  • sparse (bool) – Includes only sparse constrained polytope or adds dense full-dimensional polytope.

Returns:

Facial Reduction results object.

Return type:

FROutput

class polytopewalk.dense.DenseCenter(self: polytopewalk.dense.DenseCenter)

Bases: pybind11_object

Initialization Algorithm for Dense Polytopes.

Initialization for Center Algorithm.

getInitialPoint(self: polytopewalk.dense.DenseCenter, A: numpy.ndarray[numpy.float64[m, n]], b: numpy.ndarray[numpy.float64[m, 1]]) → numpy.ndarray[numpy.float64[m, 1]]

Finds analytical center for Ax <= b.

Parameters:

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

Returns:

Point well within polytope.

Return type:

numpy.ndarray

class polytopewalk.sparse.SparseCenter(self: polytopewalk.sparse.SparseCenter)

Bases: pybind11_object

Initialization Algorithm for Sparse Polytopes.

Initialization for Center Algorithm.

getInitialPoint(self: polytopewalk.sparse.SparseCenter, A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int) → numpy.ndarray[numpy.float64[m, 1]]

Finds analytical center Ax = b, x >=_k 0.

Parameters:

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of the polytope.

Returns:

Point well within polytope.

Return type:

numpy.ndarray

RandomWalk Classes

class polytopewalk.dense.RandomWalk(self: polytopewalk.dense.RandomWalk)

Bases: pybind11_object

Random Walk Superclass Implementation.

Initialization for Random Walk Super Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

generateCompleteWalk(self: polytopewalk.dense.RandomWalk, niter: int, init: numpy.ndarray[numpy.float64[m, 1]], A: numpy.ndarray[numpy.float64[m, n]], b: numpy.ndarray[numpy.float64[m, 1]], burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Generate values from Random Walk (virtual function).

Parameters:

  • niter (int) – Number of iterations.

  • init (numpy.ndarray) – Initial point to start sampling from.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • burnin (int, optional) – Constant for how many to exclude initially (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

class polytopewalk.sparse.SparseRandomWalk(self: polytopewalk.sparse.SparseRandomWalk, err: float = 1e-06)

Bases: pybind11_object

Sparse Random Walk Super Class Implementation.

Initialization for Sparse Random Walk Super Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

err (double, optional) – Constant for error term term (default is 1e-6).

generateCompleteWalk(self: polytopewalk.sparse.SparseRandomWalk, niter: int, init: numpy.ndarray[numpy.float64[m, 1]], A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Generate values from Sparse Random Walk (virtual function).

Parameters:

  • niter (int) – Number of steps to sample from.

  • init (numpy.ndarray) – Initial point to start sampling from.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of polytope.

  • burnin (int, optional) – Constant for how many to exclude initially (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

Subclasses of RandomWalk

class polytopewalk.dense.BarrierWalk(self: polytopewalk.dense.BarrierWalk, r: float = 0.5)

Bases: RandomWalk

Barrier Walk Implementation.

Initialization for Barrier Walk Super Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

r (double, optional) – Radius for starting distance (default is 0.5).

generateCompleteWalk(self: polytopewalk.dense.BarrierWalk, niter: int, init: numpy.ndarray[numpy.float64[m, 1]], A: numpy.ndarray[numpy.float64[m, n]], b: numpy.ndarray[numpy.float64[m, 1]], burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Generate values from Barrier Walk (virtual function).

Parameters:

  • niter (int) – Number of steps to sample from.

  • init (numpy.ndarray) – Initial point to start sampling from.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • burnin (int, optional) – Constant for how many to exclude initially (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

generateWeight(self: polytopewalk.dense.BarrierWalk, x: numpy.ndarray[numpy.float64[m, 1]], A: numpy.ndarray[numpy.float64[m, n]], b: numpy.ndarray[numpy.float64[m, 1]]) → numpy.ndarray[numpy.float64[m, 1]]

Generate weight from Barrier Walk (virtual function).

Parameters:

  • x (numpy.ndarray) – Point inside polytope.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

Returns:

Weight vector (specified by walk type).

Return type:

numpy.ndarray

class polytopewalk.dense.DikinWalk(self: polytopewalk.dense.DikinWalk, r: float = 0.5)

Dikin Walk Implementation.

Initialization for Dikin Walk Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

r (double, optional) – Radius for Dikin Ellipsoid (default is 0.5).

class polytopewalk.dense.VaidyaWalk(self: polytopewalk.dense.VaidyaWalk, r: float = 0.5)

Vaidya Walk Implementation.

Initialization for Vaidya Walk Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

r (double, optional) – Radius for Vaidya Ellipsoid (default is 0.5).

class polytopewalk.dense.JohnWalk(self: polytopewalk.dense.JohnWalk, r: float = 0.5, lim: float = 1e-05, max_iter: int = 1000)

John Walk Implementation.

Initialization for John Walk Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

  • r (double, optional) – Radius for John Ellipsoid (default is 0.5).

  • lim (double, optional) – Constant for stopping limit in fixed-point iteration (default is 1e-5).

  • max_iter (int, optional) – Constant for maximum number of fixed point iterations (default is 1000).

class polytopewalk.dense.DikinLSWalk(self: polytopewalk.dense.DikinLSWalk, r: float = 0.5, g_lim: float = 0.01, step_size: float = 0.1, max_iter: int = 1000)

Lee Sidford Walk Implementation.

Initialization for Lee Sidford Walk Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

  • r (double, optional) – Radius for Lee-Sidford Ellipsoid (default is 0.5).

  • g_lim (double, optional) – Constant for stopping gradient norm in gradient descent (default is 0.01).

  • step_size (double, optional) – Constant for step size in gradient descent (default is 0.1).

  • max_iter (int, optional) – Constant for maximum number of gradient descent iterations (default is 1000).

class polytopewalk.dense.BallWalk(self: polytopewalk.dense.BallWalk, r: float = 0.5)

Ball Walk Implementation.

Initialization for Ball Walk Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

r (double, optional) – Radius for ball (default is 0.5).

class polytopewalk.dense.HitAndRun(self: polytopewalk.dense.HitAndRun, r: float = 0.5, err: float = 0.01)

Hit-Run Implementation.

Initialization for Hit and Run Class. Runs on Full-Dimensional Polytope Form: Ax <= b.

Parameters:

  • r (double, optional) – Radius for starting distance (default is 0.5).

  • err (double, optional) – Constant for closeness to edge of polytope (default is 0.01).

Subclasses of SparseRandomWalk

class polytopewalk.sparse.SparseBarrierWalk(self: polytopewalk.sparse.SparseBarrierWalk, r: float = 0.5, err: float = 1e-06)

Bases: SparseRandomWalk

Sparse Barrier Walk Implementation.

Initialization for Sparse Barrier Walk Super Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for starting distance (default is 0.5).

  • err (double, optional) – Constant for error term in g^{-1}(x) (default is 1e-6).

generateCompleteWalk(self: polytopewalk.sparse.SparseBarrierWalk, niter: int, init: numpy.ndarray[numpy.float64[m, 1]], A: scipy.sparse.csc_matrix[numpy.float64], b: numpy.ndarray[numpy.float64[m, 1]], k: int, burnin: int = 0, thin: int = 1, seed: int = -1) → numpy.ndarray[numpy.float64[m, n]]

Generate values from Sparse Barrier Walk.

Parameters:

  • niter (int) – Number of steps to sample from.

  • init (numpy.ndarray) – Initial point to start sampling from.

  • A (numpy.ndarray) – Constraint matrix.

  • b (numpy.ndarray) – Constraint vector.

  • k (int) – Dimensionality of polytope.

  • burnin (int, optional) – Constant for how many to exclude initially (default is 0).

  • thin (int, optional) – Number of samples to thin (default is 1).

  • seed (int, optional) – Seed number for reproducibility (default is -1 meaning no fixed setting).

Returns:

List of sampled points.

Return type:

numpy.ndarray

generateWeight(self: polytopewalk.sparse.SparseBarrierWalk, x: numpy.ndarray[numpy.float64[m, 1]], A: scipy.sparse.csc_matrix[numpy.float64], k: int) → numpy.ndarray[numpy.float64[m, 1]]

Generate weight from Sparse Barrier Walk (virtual function).

Parameters:

  • x (numpy.ndarray) – Point inside polytope.

  • A (numpy.ndarray) – Constraint matrix.

  • k (int) – Dimensionality of polytope.

Returns:

Weight vector (specified by walk type).

Return type:

numpy.ndarray

class polytopewalk.sparse.SparseDikinWalk(self: polytopewalk.sparse.SparseDikinWalk, r: float = 0.5, err: float = 1e-06)

Sparse Dikin Walk Implementation.

Initialization for Sparse Dikin Walk Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for Dikin Ellipsoid (default is 0.5).

  • err (double, optional) – Constant for error term in g^{-1}(x) (default is 1e-6).

class polytopewalk.sparse.SparseVaidyaWalk(self: polytopewalk.sparse.SparseVaidyaWalk, r: float = 0.5, err: float = 1e-06)

Sparse Vaidya Walk Implementation.

Initialization for Sparse Vaidya Walk Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for Vaidya Ellipsoid (default is 0.5).

  • err (double, optional) – Constant for error term in g^{-1}(x) (default is 1e-6).

class polytopewalk.sparse.SparseJohnWalk(self: polytopewalk.sparse.SparseJohnWalk, r: float = 0.5, lim: float = 1e-05, max_iter: int = 1000, err: float = 1e-06)

Sparse John Walk Implementation.

Initialization for Sparse John Walk Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for John Ellipsoid (default is 0.5).

  • lim (double, optional) – Constant for stopping limit in fixed-point iteration (default is 1e-5).

  • max_iter (int, optional) – Constant for maximum number of fixed point iterations (default is 1000).

  • err (double, optional) – Constant for error term in g^{-1}(x) (default is 1e-6).

class polytopewalk.sparse.SparseDikinLSWalk(self: polytopewalk.sparse.SparseDikinLSWalk, r: float = 0.5, g_lim: float = 0.01, step_size: float = 0.1, max_iter: int = 1000, err: float = 1e-06)

Sparse Lee Sidford Walk Implementation.

Initialization for Sparse Lee Sidford Walk Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for Lee-Sidford Ellipsoid (default is 0.5).

  • g_lim (double, optional) – Constant for stopping gradient norm in gradient descent (default is 0.01).

  • step_size (double, optional) – Constant for step size in gradient descent (default is 0.1).

  • max_iter (int, optional) – Constant for maximum number of gradient descent iterations (default is 1000).

  • err (double, optional) – Constant for error term in g^{-1}(x) (default is 1e-6).

class polytopewalk.sparse.SparseBallWalk(self: polytopewalk.sparse.SparseBallWalk, r: float = 0.5)

Sparse Ball Walk Implementation.

Initialization for Sparse Ball Walk Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

r (double, optional) – Radius for ball (default is 0.5).

class polytopewalk.sparse.SparseHitAndRun(self: polytopewalk.sparse.SparseHitAndRun, r: float = 0.5, err: float = 0.01)

Sparse Hit and Run Implementation.

Initialization for Sparse Hit and Run Class. Runs on Constrained Polytope Form: Ax = b, x >=_k 0.

Parameters:

  • r (double, optional) – Radius for starting distance (default is 0.5).

  • err (double, optional) – Constant for closeness to edge of polytope (default is 0.01).