6
$\begingroup$

So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^{n}$, $C \in \mathbb{R}^{p \times m}$, and $d \in \mathbb{R}^{p}$. I would like to deduce a formula for the volume of the set of feasible $x$:s that satisfy these constraints. It would be great if anyone could point me in a good direction, maybe this can't be solved analytically, in this case, maybe there is an approximation?

$\endgroup$
11
$\begingroup$

Here is one paper, whose introduction will lead you to others:

Lasserre, Jean B., and Eduardo S. Zeron. "A new algorithm for the volume of a convex polytope." arXiv math/0106168 (2001).

If you want a faster but approximate algorithm:

Emiris, Ioannis Z., and Vissarion Fisikopoulos. "Efficient random-walk methods for approximating polytope volume." In Proceedings 13th Symposium on Computational Geometry, p. 318. ACM, 2014. ACM link.

Also addressed in a 2009 MO question: "Algorithm for finding the volume of a convex polytope."

$\endgroup$
4
$\begingroup$

The volume of the resulting convex polytope is given by the leading coefficient of the Ehrhart (quasi)polynomial if all matrices in your half-space description are rational (that is, have only rational entries) and the resulting polyhedron is compact. Ehrhart quasipolynomials can be computed using Normaliz or Latte. These software are open source so if you're interested in how the algorithms run just have a look.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.