volesti (version 1.0.0)

volume: The main function for volume approximation of a convex Polytope (H-polytope, V-polytope or a zonotope)

Description

For the volume approximation can be used two algorithms. Either SequenceOfBalls or CoolingGaussian. A H-polytope with \(m\) facets is described by a \(m\times d\) matrix \(A\) and a \(m\)-dimensional vector \(b\), s.t.: \(Ax\leq b\). A V-polytope is defined as the convex hull of \(m\) \(d\)-dimensional points which correspond to the vertices of P. A zonotope is desrcibed by the Minkowski sum of \(m\) \(d\)-dimensional segments.

Usage

volume(P, walk_step = NULL, error = NULL, InnerBall = NULL,
  Algo = NULL, WalkType = NULL, rounding = NULL, Parameters = NULL)

Arguments

P

A convex polytope. It is an object from class (a) Hpolytope or (b) Vpolytope or (c) Zonotope.

walk_step

Optional. The number of the steps for the random walk. The default value is \(\lfloor 10 + d/10\rfloor\) for SequenceOfBalls and \(1\) for CoolingGaussian.

error

Optional. Declare the upper bound for the approximation error. The default value is \(1\) for SequenceOfBalls and \(0.1\) for CoolingGaussian.

InnerBall

Optional. A \(d+1\) vector that contains an inner ball. The first \(d\) coordinates corresponds to the center and the last one to the radius of the ball. If it is not given then for H-polytopes the Chebychev ball is computed, for V-polytopes \(d+1\) vertices are picked randomly and the Chebychev ball of the defined simplex is computed. For a zonotope that is defined by the Minkowski sum of \(m\) segments we compute the maximal \(r\) s.t.: \(re_i\in Z\) for all \(i=1,\dots ,d\), then the ball centered at the origin with radius \(r/\sqrt{d}\) is an inscribed ball.

Algo

Optional. A string that declares which algorithm to use: a) 'SoB' for SequenceOfBalls or b) 'CG' for CoolingGaussian.

WalkType

Optional. A string that declares the random walk method: a) 'CDHR' for Coordinate Directions Hit-and-Run, b) 'RDHR' for Random Directions Hit-and-Run or c) 'BW' for Ball Walk. The default walk is 'CDHR'.

rounding

Optional. A boolean parameter for rounding. The default value is FALSE.

Parameters

Optional. A list for the parameters of the algorithms:

• Window The length of the sliding window for CG algorithm. The default value is \(500+4dimension^2\).

• C A constant for the lower bound of \(variance/mean^2\) in schedule annealing of CG algorithm. The default value is \(2\).

• N The number of points we sample in each step of schedule annealing in CG algorithm. The default value is \(500C + dimension^2 / 2\).

• ratio Parameter of schedule annealing of CG algorithm, larger ratio means larger steps in schedule annealing. The default value is \(1 - 1/dimension\).

• frac The fraction of the total error to spend in the first gaussian in CG algorithm. The default value is \(0.1\).

• BW_rad The radius for the ball walk. The default value is \(4r/dimension\), where \(r\) is the radius of the inscribed ball of the polytope.

Value

The approximation of the volume of a convex polytope.

References

I.Z.Emiris and V. Fisikopoulos, “Practical polytope volume approximation,” ACM Trans. Math. Soft., 2014.,

B. Cousins and S. Vempala, “A practical volume algorithm,” Springer-Verlag Berlin Heidelberg and The Mathematical Programming Society, 2015.

Examples

# NOT RUN {
# calling SOB algorithm for a H-polytope (2d unit simplex)
P = GenSimplex(2,'H')
vol = volume(P)

# calling CG algorithm for a V-polytope (3d simplex)
P = GenSimplex(2,'V')
vol = volume(P, Algo = "CG")

# calling CG algorithm for a 2-dimensional zonotope defined as the Minkowski sum of 4 segments
Z = GenZonotope(2, 4)
vol = volume(Z, WalkType = "RDHR", walk_step = 5)
# }