bpchesney.org

Minimize risk by maximizing diversity.  Whether you’re a trader deciding which stocks to invest in, an investor deciding which companies to invest in, or a manager trying to decide which projects to support, you can minimize your risk by investing in a portfolio of products.  This approach fits very nicely with the notion of diversity developed earlier.

Suppose you have 5 companies seeking investment. An investor can purchase up to 30% of a company. Each company must project its value at the end of the investment period and the investor has this information, along with the price per share for each company. Different companies have different prices per share and different projected valuations at the end of the investment period.

The investor cashes out and earns a share of the value of the company when the investment period is complete, proportional to the amount of the company the investor owns. For example, if the investor owns 3000 of the company’s 10000 shares, 30% of the valuation of the company at the end of the investment period goes to the investor.

The investor can only purchase whole shares of the company (no fractional shares, this is like a minimum investment). The investor may not ’short’ a company, that is, sell shares of a company that the investor does not own. So the number of shares an investor chooses to purchase must either be 0 or some positive integer less than or equal to the number of shares for sale.

Companies may or may not meet their valuation projections. Companies may go under, resulting in a valuation of 0 at the end of the investment period. The investor does not know how likely a company is to meet its goal or fold altogether. The goal is to avoid modeling this unknown and to develop a robust strategy based on the only two things the investor knows for sure: price per share and the projected valuation.  The investor seeks a 10% return and has $100,000 to invest.

Let’s write some equations to figure out what the investor should do.  We’ll use x to represent the amount of money invested in each company.

The restriction on how much of each company the investor can own amounts to a restriction on the amount of money the investor can invest in each company.  Let’s say that for company 1, the maximum investment is 50000, for company 2, its 40000, and for company 3 its 60000.

Each company expects to turn the investment they receive into a return to the investor.  We’ll use p to represent the percentage return on investment each company claims they will return to the investor at the end of the investment period.  If a company claims a 10% return on their investment, then their value for p is 1.1, since they will return the initial investment, plus another 10% on top of that.  The investor has a goal of 10% return on total investment, so weighted sum of p, weighted by the amount invested, must be greater than 110000.

That last equation can be rewritten as:

So now we have our equations in the form Ax<=b, where

To find the most diverse solution, the optimization problem is

As opposed to the most common way of solving this problem, which is to focus on maximizing return.  One way of maximizing return is to ignore the constraint of getting at least 10% on the investment and just get as much as possible.  That linear program is

where

Another way of maximizing the return is to leave the constraint as a minimum bound on the return.  That just tells the solver of the linear program to quit once 10% return is reached.  That kind of violates the spirit of maximizing your return and is not very illustrative when comparing it to maximizing diversity.  We’ll treat max return as truly getting as much return as possible, without regard for how difficult the problem is for the solver, and drop the minimum return requirement for max return.

Let’s look at the two strategies: max diversity and max return.  Let’s say that as a company offers more return, it’s price per share is higher and, even accounting for differences in the number of shares available, that this translates into a higher maximum investment.  So the companies with a higher maximum investment are promising a bigger return.  Let’s say p is:

The max return solution is:

This solution has a projected return of 14.1%.  This solution is 3-sparse for N=5, or 60% sparse.  It concentrates as much investment as possible into the highest returning company.  Once that investment is maxed out, then the rest goes into the second highest returning company until the total investment limit is reached.

The most diverse solution is:

It has a PSR of 0.20834 and a return of 10.00016%.

What happens if one of the companies fails?  If it’s the high-return company, 4, the max return solution, since it is sparse, only returns 33.6% of the investor’s money ($33600).   However, the diverse solution is much more robust and still returns over 86% of the investor’s money ($860411) if company 4 fails and the others meet their targets.  For a 4% gain on return, the risk that you would lose over 50% of your money  is clearly not worth it.

Maximizing return could give a sparse solution, even when you don’t specifically seek it. The sparse solution is not robust to the risk of total failure, in this case, zero return. The minimum PSR solution sacrifices return to deliver a diverse solution which is more robust to failure, that is, it is much more likely to have an acceptable return. Notice that I am comparing max return vs. the diverse solution as strategies. Allowing the sparse solution is what makes max return less robust.  When considering how to invest, the sparse solution is focusing your efforts, which could promise more return, but is less robust.  The diverse solution is hedging your bets.  Once the minimum return goal is met the diverse solution mitigates risk by spreading it out across a portfolio of investments.

We know about sparsity for vectors, which is the property of having a lot of 0′s (or elements close enough to 0).  The 0′s in a sparse matrix or vector, generally, make computation easier.  This has been a boon to sampling systems in the form of compressive sampling, which allows recovery of sampled data by using computationally-efficient algorithms that exploit sparsity.

The opposite of sparsity is density.  A vector whose entries are mostly nonzero is said to be “dense,” both in the sense that it is not sparse, as well as being slow and difficult to muddle through calculations on this vector if it is really large.  In general, dense vectors are not very useful.  Or are they?  In this post, I introduce the notion of diverse vectors, a subset of dense vectors, as a more interesting foil to sparsity than simply dense vectors.

This post explores a measure of diversity called the peak-to-sum ratio (PSR). We can use PSR to find the most diverse solution in a linear program, but what can it be used for? We’ll find this linear program optimally distributes quantized, positive units, such as currency or genes. Maximizing diversity, by minimizing PSR, is desirable in several applications:

• Investing
• Workload Distribution
• Product Distribution
• Sensor Data Fusion and Machine Learning

In contrast to some systems which allow dense vectors, these systems actually desire the most diverse solution.

Consider the following system of equations:

x₁ + x₂ + x₃ + x₄ = 12

x₂ - x₃     = 0

x₄ = 0

The following table gives a partial list of possible solutions (for x₁, x₂, and x₃, since x₄ is already given).

The sparsest solution is highlighted in green, (12, 0, 0, 0).  It has the most zeroes in it.  It has everything concentrated in one element of the vector, the first element.  All other elements are zero, making several computations on that vector faster and easier.

Notice the solution highlighted in yellow, (4,4,4,0).  It has very few zeros in it, in fact, none except the one variable that was explicitly set to 0.  But there are other solutions that have only one zero, or are, as they say, 1-sparse.  For instance, (10,1,1,0) is also 1-sparse.  The vector (4,4,4,0) is highlighted and (10,1,1,0) is not because (4,4,4,0) is more diverse.  What makes it more diverse?  The (4,4,4,0) vector has the most equitable distribution among its elements, which is, conceptually, the opposite of being sparse.  Whereas the most sparse solution has its energy concentrated in the fewest elements, the most diverse solution has its energy distributed to the most elements.  In fact, (10,1,1,0) could be considered to be more sparse than (4,4,4,0) as it is closer to having its energy concentrated in one vector (first posited in [1]).

So if we’re talking about more or less diverse/sparse, this implies that we can quantify it.  One way to quantify it is to look at the peak-to-sum  ratio (PSR).  The peak to sum ratio is defined as the ratio of the largest element in x to the sum of all elements of x.

PSR can also be expressed as the ratio of two norms, the infinity norm and the first norm.  Let’s see what this ratio looks like for the solutions we considered above, plus a few more.

The (4,4,4,0) solution appears to have the lowest PSR, until we proceed to solution (13,13,-14,0).  As we proceed past (13,13,-14,0), PSR becomes vanishingly small.  In fact, we see that (4,4,4,0) was just a local minima for PSR.

This is unsatisfying, for a couple of reasons.  The first is linear programming.  We can’t use a linear program to minimize PSR and arrive at the most diverse solution because PSR is not convex, that is, we can’t be sure we’re on a path to smaller and smaller PSR because we could encounter a local minima, like we did at (4,4,4,0).

The second way this is unsatisfying is that (13,13,-14,0) does not seem more diverse than (4,4,4,0).  If we’re considering the elements of x to be bins of energy, or some other thing that is to be distributed, then having an element that is -14 does not make any sense.  Instead of distributing, or deciding how things are to be allocated, we are actually taking them away, which defeats the whole purpose of what we are trying to do. So let’s add in a constraint that x has to be greater than 0.

For this particular problem, we can proceed in a linear fashion from the first candidate solution (12,0,0,0) to the most diverse one (4,4,4,0). However, in general, is this problem convex? That is, could we choose another set of equations and be able to march towards the most diverse answer?

Consider the definition of convexity for a feasible set of solutions.  A set is convex if, when proceeding from one point to the next, you stay in that set [2].  It helps to rewrite our problem in terms of linear algebra.  We seek the most diverse solution to a set of linear equations,

where Ax=b represents our equations we’re trying to solve.  Since x cannot be negative, we know that,

Is this convex?  The shaded region in the following graph shows the x’s that satisfy the quantity (PSR) to be minimized when it’s less than or equal to 1.

In the example in the graph above, there are only two elements in x.  The possible values of x outside of the shaded region, when either x1 or x2 or both are negative, are not in the set of feasible solutions.  So do the answers in this shaded region form a convex set? Yes, because we can pick two points in the shaded region, and draw a straight line between them that has to stay in the shaded region.

Notice if we restrict values of the elements of x to the integers, we still have a convex set!  This result is satisfying because we’ll want to distribute units of energy, currency, etc…, anyway.

In the language of linear algebra,

where Z represents the set of integers.  So the two constraints we’ve added to our convex optimization problem to find the most diverse solution:

1. Must not contain a negative distribution (x greater than or equal to 0)
2. Must have a base unit of distribution (x must contain integers)

We can now use an integer program to perform the optimization.  Restricted to positive, integer values, when we minimize PSR, our linear program will march algorithmically, inexorably to the most diverse solution to a system of linear equations.

References

[1]  Zonoobi et al. “Gini Index as Sparsity Measure for Signal Reconstruction from Compressive Samples,”  IEEE Journal of Selected Topics in Signal Processing.  vol 5, no. 5, Sept. 2011.

[2]  Strang, Gilbert.  Computational Science and Engineering.  Wellesley, MA: Wellesley-Cambridge Press, 2007.