n-Dimensional centroid for Universal optimization algorithms

Background

Over the course of his career, Thomas Cover developed the concept of "natural optimization", with which he addressed problems where an optimal strategy emerges naturally through a process of weighting and updating based on past performance (rank weighting).

This work spans multiple domains, including portfolio selection, data compression, and information theory.

Major applications

Universal Portfolio - an optimization method where the strategy asymptotically converges on the performance of the best constant-rebalanced (fixed) portfolio.

Universal Data Compression (Information Theory) - In 1973 Cover described his “Universal Coding” that approaches the optimal compression rate of an unknown source, without knowing its probability distribution in advance. This universal code asymptotically achieves the best possible compression rate over time. Cover assessed the tradeoff between compression efficiency and redundancy, showing how sequential prediction can minimize excess code length. His methods influenced Lempel-Ziv compression, used in ZIP files and other modern compression techniques.

Universal Prediction & Learning

Cover’s natural optimization extends to sequential prediction, where an algorithm refines its predictions over time to match the best hindsight strategy. Consider machine learning algorithms that adapt without predefined models.

These solutions:

• Neither make no require predictions.
• Make no assumption about the distribution of data.

• Have no parameters to fit, train, or learn.

Computationally intensive, the approaches have required taking the integral over infinite combinations of the tracked data sets, (prices, different compression algorithms, competing climate models, …)

A number of parties have implemented approximations (e.g., discretization, sampling methods) gaining speed traded for accuracy.

Cover, building on the insights of John Kelly and Claude Shannon, arrived at something I think important, a means to optimize sequential decision making in the face of uncertainty.

Some years ago I played around with some multi-dimensional geometry.

I wanted to identify the center of mass of regular simplexes that had what someone described to me as hyper-caps.

I very recently came across the Mathematica function, RegionCentroid[ ] which appears able to simplify the kind of calculations required for Cover's Universal optimization techniques.

Consider the following representation of a 2-dimensional (a line on the x axis) simplex with a hyper-cap:

polygon = Polygon[{{0, 0}, {1, 0}, {1, .75}, {0, .25}}];
cm = RegionCentroid[polygon]*1.0
cx = cm[[2]]
Graphics[{EdgeForm[Black],
  Transparent,
  polygon, 
  Red, 
  Point[cm]},
 Axes -> True,
 AxesLabel -> {x, y},
 GridLines -> {{cx}, {cm[[2]]}}]

{0.583333, 0.270833}

The first of the produced values would equate to the rank weighting in, for instance, a Universal Portfolio of two securities.

In this application, the line on the x-axis represents all possible portfolio combinations of 2 securities.

Point {0,0} represents a 100% allocation to Security1 and point {1,0} represents 100% allocation to Security 2.

The mid point of the line {0, 0.5} would represent the portfolio weights with 50% in each of the 2 securities.

To make it clear, the heights of the depicted polygon represent the hyper-cap, with the values of:

Security1 = 0.25 Security2 = 0.75

Therefore, in the example above, one would “rebalance” the portfolio to:

• 58.33% in Security 1 and
• (100% - 58.33%) in Security 2.

One would then recalculate the RegionCentroid[ ] at each time step and project from the centroid to the base of the simplex (in the 2-dimensional case, the co-ordinate value of the centroid's x-axis.

Straight forward with a 2-dimensional simplex. Reasonable to think about with a 3-dimensional simplex. Gets complicated with a large n-dimensional simplexes.

Nevertheless, the use of RegionCentroid[ ] could make calculating even large n-dimensional simplexes vastly more efficient than previous approaches.

It essentially casts the question as a geometry problem rather than an integration one.

I have 2 questions. One Mathematica based and the second geometry based (but I’d welcome any answer to it).

Question 1

As demonstrated in my code above (repeated here) polygon = Polygon[{{0, 0}, {1, 0}, {1, .75}, {0, .25}}];

Mathematica appears to construct the polygon point-to-point counter clockwise.

This works fine for plane geometry (2-D polygon).

I need to intuitively understand how I need to supply co-ordinates to Mathematica to define, a polygon 3-dimensional simplex with a hyper-cap and better yet how to think about this in n-dimensions.

Question 2

Given that for any n-dimensional simplex with a corresponding hyper-cap, the simplex serves as the “base” of the polygon for purposes of finding the n-dimensional equivalent of the 2-dimensional centroid's x-axis value, which co-ordinates do I need to extract from n-dimensional polygon centroids?

Some additional context

The following function can calculate the centroid and one can extend it pretty simply to n-dimensions. It assumes a regular simplex. The number of "heights" corresponds to the simplex's dimensionality.

h = {3, 4, 2};  (*heights at right angles to the base simplex*)
n = Length[h];

A = Transpose[
   Prepend[#, 03] & /@ 
    CholeskyDecomposition[(IdentityMatrix[n - 1] + 1)/2]];

((h/Total[h] + 1)/(1 + n)) . A

Output:

{109/72, 1 + 11/(24 Sqrt[3])}

The simplex with hyper-cap would look something like this:

Where the base simplex = a unit equilateral triangle and the "vertical" sides stand orthogonal to the base.