C++ Dense Random Walks

class RandomWalk

Subclassed by BallWalk, BarrierWalk, HitAndRun

Public Functions

inline RandomWalk()

initialization of Random Walk super class

virtual MatrixXd generateCompleteWalk(const int niter, VectorXd &init, const MatrixXd &A, const VectorXd &b, int burnin, int thin, int seed)

generate values from the walk

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix (Ax <= b)

  • b – polytope vector (Ax <= b)

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

class BallWalk : public RandomWalk

Public Functions

inline BallWalk(double r)

initialization of Ball Walk class

Parameters:

r – spread parameter

virtual MatrixXd generateCompleteWalk(const int niter, VectorXd &init, const MatrixXd &A, const VectorXd &b, int burnin, int thin, int seed) override

generate values from Ball Walk

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrixd (Ax <= b)

  • b – polytope vector (Ax <= b)

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

virtual void printType() override

print general type

class HitAndRun : public RandomWalk

Public Functions

inline HitAndRun(double r, double err = 1e-6)

initialization of Hit and Run class

Parameters:

  • r – spread hyperparamter

  • err – error hyperparameter

virtual MatrixXd generateCompleteWalk(const int niter, VectorXd &init, const MatrixXd &A, const VectorXd &b, int burnin, int thin, int seed) override

Generate values from the walk.

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope matrix

  • burnin – number of steps to burn

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

virtual void printType() override

print general type

class BarrierWalk : public RandomWalk

Subclassed by DikinLSWalk, DikinWalk, JohnWalk, VaidyaWalk

Public Functions

inline BarrierWalk(double r)

initialization of BarrierWalk class

Parameters:

r – spread parameter

virtual VectorXd generateWeight(const VectorXd &x, const MatrixXd &A, const VectorXd &b)

generate weights when calculating Hessian matrix

Parameters:

  • x – point in polytope to generate weight

  • A – polytope matrix (Ax <= b)

  • b – polytope vector (Ax <= b)

Returns:

Vector

virtual MatrixXd generateCompleteWalk(const int niter, VectorXd &init, const MatrixXd &A, const VectorXd &b, int burnin, int thin, int seed) override

generate values from the walk

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope vector

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

virtual void setDistTerm(int d, int n)

set distribution constant

Parameters:

  • d – (dimension)

  • n – (number of constraints)

class DikinWalk : public BarrierWalk

Public Functions

inline DikinWalk(double r)

initialization of Dikin Walk class

Parameters:

r – spread parameter

virtual void printType() override

print dikin

virtual VectorXd generateWeight(const VectorXd &x, const MatrixXd &A, const VectorXd &b) override

returns weight for DikinWalk (Identity Matrix)

Parameters:

  • x – point

  • A – polytope matrix (Ax <= b)

  • b – polytope vector (Ax <= b)

Returns:

Vector

class VaidyaWalk : public BarrierWalk

Public Functions

inline VaidyaWalk(double r)

initialization of Sparse Vaidya Walk class

Parameters:

r – spread parameter

virtual void printType() override

print general type

virtual VectorXd generateWeight(const VectorXd &x, const MatrixXd &A, const VectorXd &b) override

returns weight for Vaidya Walk (leverage score calculation)

Parameters:

  • x – center vector

  • A – polytope matrix

  • b – polytope vector

Returns:

Vectorr

class JohnWalk : public BarrierWalk

Public Functions

inline JohnWalk(double r, double lim = 1e-5, int max_iter = 1000)

initialization of John Walk class

Parameters:

  • r – spread parameter

  • lim – norm limit for fixed point iteration

  • max_iter – maximum number of iterations in gradient descent

virtual void printType() override

print john walk

virtual VectorXd generateWeight(const VectorXd &x, const MatrixXd &A, const VectorXd &b) override

generates John weight by solving convex optimization problem

Parameters:

  • x – point in polytope to generate DikinLS weight

  • A – polytope matrix

  • b – polytope matrix

Returns:

Vector

class DikinLSWalk : public BarrierWalk

Public Functions

inline DikinLSWalk(double r, double g_lim = 0.01, double step_size = 0.1, int max_iter = 1000)

initialization of Lee Sidford Walk class

Parameters:

  • r – spread parameter

  • g_lim – gradient descent norm limit

  • step_size – size of gradient descent step

  • max_iter – maximum number of iterations in gradient descent

virtual void printType() override

print dikinls

virtual VectorXd generateWeight(const VectorXd &x, const MatrixXd &A, const VectorXd &b) override

generate weights when calculating Hessian matrix

Parameters:

  • x – point in polytope to generate DikinLS weight

  • A – polytope matrix (Ax <= b)

  • b – polytope vector (Ax <= b)

Returns:

Vector