3
$\begingroup$

I am building software for an investment manager. The investment manager invests money on behalf of his clients.

The investment manager has a model portfolio, of say 20 stocks, each with certain weightage.

Eg: His model portfolio can look like this:

{GOOG: .03, AAPL: 0.4, MSFT: 0.25, TESLA: 0.5, IBM: 0.1, .....} Now lets say the investment manager has one client, who holds all of the stocks, the total of which is worth, say USD50,000, but with slightly different weightage:

{GOOG: .0295, AAPL: 0.415, MSFT: 0.232, TESLA: 0.1, IBM: 0.2, .....} Now the client wants to invest a lumpsum, lets say USD10,000.

Now, the investment manager wants to split this USD10,000 across 20 stocks, so that he gets closest to the model portfolio. i.e. I want the resultant USD60,000 to be split in a way that is closest to the ratios maintained in the model portfolio.

A limitation here is that, I can buy or sell a minimum of 1 stock; I cannot deal in fractions of stocks.

Is there a name for this kind of problem? I am pretty sure this has been solved by someone, so do not want to reinvent the wheel.

I do not know what I should google for, or where to start from.

I want the chosen allocation to have the least deviation from the model portfolio, measured by $L_2$ distance (sum of squared differences). Also, the investor keeps investing periodically, so there is a chance his portfolio might deviate further and further, so the idea is to keep these "tracking errors" to a minimum, so that it the investor's portfolio is as close to the model portfolio as possible.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ In Excel there is something called "Goal Seek" you could explore. In regular programming take a look on Amazon at a book called "Assignment Problems." There are a number of algorithms in there that will likely address this. But the example you give seems simple enough that simple ratios and rounding to whole numbers should solve the problem. $\endgroup$ – mba12 Mar 2 '17 at 18:51
3
$\begingroup$

Let $d_i$ be the desired dollar amount that you'd ideally like to have invested in the $i$th stock (i.e., $d_1,\dots,d_n$ represent the ideal/model portfolio, without taking the requirement to avoid fractional shares). Let $p_i$ denote the price of a single share of the $i$th stock.

Then you want to find a solution to the following optimization problem

$$\begin{align*} \text{minimize } &(p_1 x_1 - d_1)^2 + \dots + (p_{20} x_{20} - d_{20})^2\\ \text{subject to } &p_1 x_1 + \dots + p_{20} x_{20} = 10,000\\ &x_1 \ge 0, \dots, x_{20} \ge 0 \end{align*}$$

where you require that the variables $x_1,\dots,x_{20}$ be integers. Here the $p_i$'s and $d_i$'s are given (they are known constants), and you've solving for the $x_i$'s.

This is an instance of quadratic integer programming: i.e., integer programming with linear constraints and a quadratic objective function. That in turn is a special case of mixed-integer quadratic programming (MIQP). In general MIQP allows the problem to contain some integer variables and some continuous variables; your particular instance has only integer variables, so it's a special case of MIQP. You can find off-the-shelf MIQP solvers out there. I would recommend that you try applying one to your problem. Given the problem size you describe, I would expect them to be effective and efficient at your problem.

If you wanted to measure the deviation from the ideal model by the $L_1$ distance (sum of absolute values of differences) instead of the $L_2$ distance (sum of squared differences), that could be expressed as an instance of integer linear programming (ILP), for which solvers are even more effective.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hi, one question. Why do we square the difference? Cant we minimise the absolute value of (pixi−di) instead? $\endgroup$ – ashwnacharya Mar 7 '17 at 7:57
  • 1
    $\begingroup$ @ashwnacharya, the difference is squared because that's what you said you wanted: you said you wanted the L2 distance. Yes, you could minimize the sum of the absolute values of the differences; as I say in my answer, that's the L1 distance, and you can minimize that using integer linear programming. This is why I originally asked (in a comment on your question) what you wanted to minimize, because that affects the solution method. $\endgroup$ – D.W.♦ Mar 7 '17 at 17:23
  • $\begingroup$ Ok, sorry my bad. I should have rephrased my question better. My intention was to ask that, given my intention of minimizing the deviation from the model portfolio, is it okay if I minimise the L1 distance instead of L2. I was trying to understand what the implications were, if I chose one over the other. $\endgroup$ – ashwnacharya Mar 8 '17 at 8:28
  • 1
    $\begingroup$ @ashwnacharya, I'm afraid that only you will be able to determine which distance metric is most suitable for your application. That depends on the nature of your application. The L2 distance tends to penalize large deviations especially highly, and try to spread out differences across all stocks. The L1 distance tends to try a little harder to reduce the number of stocks that have any non-zero difference. If you'd like to get a better feeling for that, I suggest you play with some examples, then ask on Mathematics about any remaining confusions about the differences between these metrics. $\endgroup$ – D.W.♦ Mar 8 '17 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.