Audience requirements: high school math. No need to be a programmer.
What is Linear Programming?
Mathematical optimization (of which LP is a special case1) is a class of mathematical methods to help choose the best possible choice from a set of alternatives. It has many uses in real-life problems. It requires converting a problem into a mathematical representation. The best solution typically seeks the best value of an objective function (i.e. what you want to achieve, such as maximizing profit in a factory) subject to some constraints (e.g. availability of raw materials). LP is a very well understood field, and many good solvers exist.
Simple LP-based portfolio optimization example
Assume an ideal portfolio2 of 3 asset classes:
- 10% cash
- 50% stocks
- 40% bonds
Define c, s, b to be the respective percentage of each asset class in the final portfolio. In order to get closest to the ideal (a.k.a. target) portfolio, we must2 minimize:
- |10 – c| + |50 – s| + |40 – b| (“distance from ideal portfolio”)
… subject to constraints3, 4:
- 0 <= c <= 100
- 0 <= s <= 100
- 0 <= b <= 100
- c + s + b = 100
For brevity, [7 52 41] will mean “a portfolio that’s 7% cash, 52% stocks, 41% bonds”.
- The vertical bar in the objective function means “absolute value”. Linear programs do not support this concept, but we’ll get to that in a future post.
- 1 through 3 mean “any single asset must be between 0% and 100% of the portfolio”. Makes sense. E.g. if I have $100, I can’t ever hold $110 in stocks, or minus $10.
- 4 means “if you add up all the holdings, they should add up to the value of the entire portfolio”.
- The direction in which a single asset class is off target (above or below) does not matter. Take [10 49 41] and [10 51 39]. Stocks are considered equally off target at 49% vs 51%.
- Being off target by e.g. 1% has the same penalty regardless of asset class5. E.g. [9 51 40] is just as good as [10 51 39].
The best scenario is when we hold a portfolio that matches the target exactly: [10 40 50] gives us |10 – 10| + |50 – 50| + |40 – 40| = 0.
Being slightly off, which is intuitively worse, also works out to be worse: e.g. [7 52 41] gives us |10 – 7| + |50 – 52| + |40 – 41| = 6. We are trying to minimize this value, so 6 > 0 means this portfolio is worse, as expected.
Why do all this?
This all sounds complicated. Why not just buy 50% stocks, 40% bonds, and leave 10% cash aside?
Say that we also hold some stock6 that cannot be sold (e.g. an unvested executive stock grant). If total stock (as a % of all assets) is already e.g. 80%, then what do we do? We likely don’t want to buy even more stocks, because we are already overweight at 80% (vs the target of 50%). However, how should the remaining 20% be invested? Clearly, bonds can’t be 40% of the total (80% + 40% > 100%). In practice, this is way more complicated, because there are multiple asset classes, and also multiple objectives.
The real value shows when we aren’t able to pick the best portfolio, but must pick the best from a set of feasible portfolios. LP is good at that.
Investing well can be done with well-established mathematical optimization techniques. It is possibly to define rigorously what makes a good portfolio, which lets us
- exclude invalid portfolios
- pick the best valid portfolio
This technique is even more important in the presence of multiple – and many times conflicting – goals. This is not illustrated here, and will be addressed in a future blog post.
- Linear programming is not related to computer programming, although one can write software to solve linear programs.
- Typically, a financial advisor (automated or not) ascertains a client’s needs (how risk-averse they are, their near-term needs for cash, etc.) and suggests an ideal portfolio. Doing this in terms of asset classes is not the only (or even best) way to do this, but it’s the industry standard, and will suffice for this example.
- 0 <= c <= 100 is actually two constraints, but we show it as one for brevity.
- If you are a finance person: This example is intentionally simple. We are
- disallowing leverage
- disallowing short sales
- ignoring any (minuscule, in practice) transaction costs that will reduce the value of the portfolio if we trade
- assuming our only objective is to match the target portfolio
- In practice, a proportional penalty is better. 8% less in stocks isn’t horrible – 42% is close enough to 50%, proportionally. However, 2% in cash (vs a target of 10%) is very far off; it is 1/5th of the desired 10%.
- For simplicity in this example, we assume that your external stock behaves the same as whatever stock fund you’d normally buy. We do not make this assumption in our actual system.