3

I am using amoeba to solve an optimization problem and want to distribute the initial perturbations uniformly about the initial estimate. With only Excel at my disposal, I cannot figure out how to compute the Cartesian coordinates for the vertices of a regular 16-simplex.

There are published values up to a 10-simplex available on the 'net, but I've not been able to locate any solutions for higher dimensions. Perhaps someone out there has the tools to compute these coordinates (e.g. Mathematica, Maple, or Matlab), or can point me as a procedure to accomplish this in Excel.

EBlake
  • 133
  • 6
  • Does the answer have to live in 16 dimensions? If not, just use the 17 axis points in 17-dimensional space: (1,0,...,0), (0,1,0,...,0), ..., (0,...,0,1) – Don Hatch Sep 12 '20 at 05:33

2 Answers2

3

Hint:

You could start to define the vertices $q_i^{(n)}$ and midpoints $m^{(n)}$ of a regular n-simplex (edge length equalling 1) recursively, e.g. $$ q_0^{(1)} = (0),\\ q_1^{(1)} = (g_1), \quad\text{with}\quad g_1 = 1,\\ m^{(1)} = (h_1), \quad\text{with}\quad h_1 = \frac{1}{2},\\ q_i^{(n+1)} = (q_i^{(n)},0), \quad\text{with}\quad 0 \le i \le n,\\ q_{n+1}^{(n+1)} = (m^{(n)},g_{n+1})\\ m^{(n+1)} = (m^{(n)},h_{n+1}). $$

If one then imposes the conditions $(*)$: $$ \|q_{n+1}^{(n+1)} - q_{n}^{(n+1)} \|^2 = 1\\ \|q_{n+1}^{(n+1)} - m^{(n+1)}\|^2 = \|q_{n}^{(n+1)} - m^{(n+1)}\|^2. $$ This gives $$ \|q_{n+1}^{(n+1)} - q_{i}^{(n+1)} \|^2 = 1$$ and then $$ \|q_{j}^{(n+1)} - q_{i}^{(n+1)} \|^2 = 1.$$

It follows from the conditions $(*)$, that we have $(2*)$: $$ (g_{n+1}-h_{n+1})^2 = (1-g_{n+1}^2) + h_{n+1}^2,\\ (g_{n+1}-h_{n+1})^2 = (g_n-h_n)^2 + h_{n+1}^2. $$

From which one can deduce $$ g_{n+2}^2 = \frac{4g_{n+1}^2-1}{4g_{n+1}^2}. $$

Which can be used to get by induction $$g_n^2 = \frac{n+1}{2n}.$$ and hence $$h_n^2 = \frac{1}{2n(n+1)}.$$

I hope there is no typo and the details can be filled by the reader.

The definition of $q_i^{(n)}$ and the determinant formula for the simplex volume, give additionally for this simplex $$ Vol(S_n) = \frac{(n+1)^{1/2}}{n!} \left(\frac{1}{2}\right)^{n/2} $$

andre
  • 1,284
  • Thanks for the theoretical framework and the considerable effort you put into your reply. For myself, the solution to the 16-simplex forms a small part of a much larger industrial problem, so I was looking for a quick solution with the tools at my disposal. – EBlake Jul 27 '15 at 20:43
  • So you can now implement the recursion in your favorite programming language up to dimension 16. – andre Jul 27 '15 at 20:46
  • Actually what I called above midpoint $m^{(n)}$ is the center of gravity of the constructed regular simplex $S_n$. – andre Nov 19 '15 at 20:49
0

I managed to set the problem up as an optimization problem in Excel with some predictable boundary conditions (now that's recursive - solving part of an optimization scheme using another optimization scheme). This is a numerical solution rather than empirical.

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
-0.0625,0.998044937,0,0,0,0,0,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,0.995824618,0,0,0,0,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,0.993280997,0,0,0,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,0.990337943,0,0,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,0.986893272,0,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,0.982806744,0,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,0.977880357,0,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,0.971825326,0,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,0.964203037,0,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,0.954313524,0,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,0.940965807,0,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,-0.188193171,0.92195445,0,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,-0.188193171,-0.230488623,0.892678562,0,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,-0.188193171,-0.230488623,-0.297559513,0.841625397,0
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,-0.188193171,-0.230488623,-0.297559513,-0.420812698,0.728869005
-0.0625,-0.066536335,-0.071130335,-0.076406233,-0.082528162,-0.089717571,-0.098280675,-0.108653377,-0.121478167,-0.137743285,-0.159052253,-0.188193171,-0.230488623,-0.297559513,-0.420812698,-0.728869005
EBlake
  • 133
  • 6