I just came across the following problem: Let us consider the unit corner of the n-cube $$ \Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \mbox{ for all } i\right\}. $$ Let $P$ be a polytope in $\Delta_c^n$ generated as the intersection of $m$ half-spaces. Let us equip $\Delta^n$ with the distance defined with a positive-definite matrix $Q$. I am looking to compute the diameter of the set $P$.

From a quick exploration, the diameter is the maximal distance between two extremal points of $P$.

The problem is that the number of these extremal points is typically exponential in $n$.

But if $Q$ has only a few eigenvalues that are not small, is there a smart way to approximate the diameter of $P$ ?

I am interested in any setting, even randomized ones, where the diameter can be approximated correctly numerically. The only hypothesis I do like to keep is the fact that $n$ being large.