Best way to find all possible linear combinations of n rows from large dataset that meets a target for each column

I have a large dataset, A, roughly 10000 rows and 10 columns. Each row represents a different investment portfolio and each column represents the percentage of investment in that sector, such that each row sums up to 1. I have a target percentage for each sector and want to find the all possible linear combinations of n different investment portfolios (rows) that meet it. My knowledge of Matlab is pretty basic so I had thought of using the built-in function combnk to find all the combinations of the rows without repeating, then using it and a loop to calculate one by one if the combinations meet the target, but combnk doesn't work for such large number of elements. I also figured this probably isn't the best way to do this so if anyone has any ideas, please let me know.

[Matt J]

Do you really mean all possible linear combinations, with no constraints on the n coefficients? Even if A had only n rows, There would normally be an (uncountably) infinite number of coefficient choices.

[Yan Loh]

Sorry for the confusion, I mean to set n to a certain value such as 5 to start off with. Is that what you meant?

[David Goodmanson]

Hi Yan,

Do you mean the usual linear combination with adjustable coefficients, where you get to pick the coefficients c? So with 10 portfolios,

c1*pf1 + c2*pf2 + ... c10*pf10 = target pf

Or do you mean finding a certain number n of portfolios so that their straight average equals the target portfolio, within some small tolerance?

If it's the first case, then with less than 10 portfolios, in general it can't be done. With more than 10 portfolios the c's cannot be calculated uniquely. With 10 portfolios, the odds are excellent that any set of 10 that you choose are linearly independent, in which case you can find the c's.

However, the number of ways to pick 10 portfolios out of 10000 is about 2.7x10^33. That's a lot of ways. The age of the universe is about 4x10^17 seconds.

[Matt J]

Or, do you mean

   c_1*pf_1 + c_2*pf_2 + ... c_n*pf_n >= target pf

If so, the c's are almost never unique, regardless of n.

[David Goodmanson]

Hi Matt, depending on how you mean this, I don't believe it's true. For 10 column data and a given 10 linearly independent row portfolios, you have a nonsingular 10x10 matrix that will give unique c's.

[Yan Loh]

Hey David, the first case was what I meant. I have tried it for a smaller matrix, A, and a smaller n=2 and it hasn't worked but it might help clarify things:

n=2

A=[0.25 0.3 0.35 0.1; 0.1 0.4 0.5 0; 0.4 0.2 0.35 0.05; 0.2 0.3 0.3 0.2; 0.2 0.1 0.4 0.3;]

B=[0.2335 0.23 0.3675 0.17]                %Target

c=combnk(1:size(A),n)

xy=zeros(size(c));
for i=1:size(c)
syms x y
eqn1=x*A(c(i,1),1)+y*A(c(i,2),1)==B(1);
eqn2=x*A(c(i,1),2)+y*A(c(i,2),2)==B(2);
eqn3=x*A(c(i,1),3)+y*A(c(i,2),3)==B(3);
eqn4=x*A(c(i,1),4)+y*A(c(i,2),4)==B(4);
sol = solve([eqn1, eqn2, eqn3, eqn4], [x, y]);
xSol = sol.x;
ySol = sol.y;
xy(i,:)=[xSol ySol];
end

xSol returns empty sym for every one but I know there exist a solution for the combination row 1 & 5 with x=0.65, y=0.35

I figured this method, even if it were to work for a small matrix, wouldn't work for a matrix as large as the one I'm working with due to the large number of different combinations.

[David Goodmanson]

Hi Yan,

.65*A(1,:) + .35*A(5,:)
    ans = 0.2325    0.2300    0.3675    0.1700
B
      B = 0.2335    0.2300    0.3675    0.1700

These two don't agree; they differ by .001 in the first entry. If that is satisfactory and you want to find the smallest number of portfolios to combine that satisfy some tolerance, that's an interesting linear programming problem, not that easy.

If you want an exact solution, then you can get one by taking any four portfolios from the 10000 that you have. (Occasionally you may get four that don't work). I picked four by arbitrarily eliminating portfolio 2 from A.

It's way more common in this situation to calculate with portfolios in columns than rows, so I took the transpose of A and B before finding the solution.

% original matrix without row 2 is four typical portfolios
 A = [0.25 0.3 0.35 0.1
     0.4 0.2 0.35 0.05
     0.2 0.3 0.3 0.2
     0.2 0.1 0.4 0.3];

B=[0.2335 0.23 0.3675 0.17];

Atrans = A'                 % portfolios in columns
Btrans = B'                 % column vec
c = Atrans\Btrans
  c =
  0.6410
  0.0063
  0.0054
  0.3484

The first coefficient is for portfolio 1, etc. This is an exact solution for Btrans, within numerical error down around 1e-16. The only problem is that sometimes some of the coefficients may come out negative, in which case I suppose you have to divest yourself of part of a portfolio.

[Matt J]

Hi Matt, depending on how you mean this, I don't believe it's true. For 10 column data and a given 10 linearly independent row portfolios, you have a nonsingular 10x10 matrix that will give unique c's.

I had an inequality there, supposing that the OP may have meant the portfolio target as a lower bound, but it looks now that he did not.

[David Goodmanson]

Sorry Matt, I missed seeing the > part.

Answer 1

[Bruno Luong]

Your problem can be formulated as finding (all) feasible solutions of a linear constraints.

A*c >= target
c >= 0
sum(c) = 1

The feasible region is either empty (eg if target if too high) or interior of a polygonal in an afine space R^(n-1) where n is the length of target. The set has therefore continuum cardinal (too many point) to be listed on a computer.

To find ONE solution you can use LINPROG with a dummy cost objective, it will return a feasible point (or not) of the linear constraint.

Answer 2

[Matt J]

In your response to David, you have implied that your coefficients c are completely unconstrained, i.e., they are allowed to have negative values. I suspect you don't really mean that, since this is a financial application and I have never heard of investing a negative amount in a portfolio. If I assume that c>=0, then you are looking for all c with n non-zero coefficients satisfying the linear (in)equalities,

A.'*c = pf_target
c>=0

As David has told you, you can't get finite solutions to this unless you restrict yourself to linearly independent combinations of columns of A.' (portfolios). So, I will assume further that you wish to confine your search in this manner.

Now, it is a theorem from linear programming that this subset of solutions are precisely the vertices of the 10000-dimensional polyhedron described by the inequalities above. Therefore, your problem reduces to a vertex enumeration problem. For a 10000-dimensional space, the number of vertices may be finite, but likely still too huge to realistically store in a computer. Nevertheless, you can attempt the enumeration using LCON2VERT (download here). It would look as follows,

solutions = lcon2vert( eye(10),zeroes(10,1)   ,   A.',pf_target);

[Bruno Luong]

To Matt: for the non degenerated case, the vertices are solutions(s) of the problem of optimizing some linear objective function.

Here there is no objective function specified, the feasible set cannot be reduced to set of vertices, but the interior of the polytope is also valid.

Even if you want to enumerate the vertices, in the case of

A.'*c = pf_target
c>=0

The number of vertices can go up to nchoosek(10000,9) >= 2 * 10^30. Just forget about any attempt of numeration.

[Matt J]

@Bruno

As I explained, the solution set boils down to vertices if you limit the search to linearly indep. combinations of portfolios. This is a theorem from convex analysis, see for example Theorem 2.6 here, and is valid regardless of whether you have an objective function.

As for the size of the enumeration, I think I already said I was pessimistic, but that’s what the OP asked for....

[Bruno Luong]

I think I miss-understood what you wrote above. You are right, the vertices are subset solution(s) of the constraints

    A*c = t
    c >= 0

Assume they are {c}_i, i=1,...,p (p can be up to 10^30).

But you never said how all solutions can be get from {c_i}.

The solutions (points belong to feasible set, or polytope), if bounded, are actually all convex combination of {c_i}, meaning

S = { c = sum_(w_i*c_i) : w_i>=0, sum(w_i) = 1 }.

OP wants to enumerate S (and not the relative tiny subset {c_i}), which has continuum cardinal when p>1 (recall, in his case p >= 10^30).

Inexperience people often have very off intuition about combinatorics, and how those thing can grow fast, and they believe computer is infinity fast and has infinity large in storage.

I'll try to steer them away and avoid giving them the impression that they could solve such problem by brute force.

[Yan Loh]

Thanks Matt and Bruno, I now realise my approach of as Bruno puts it as using brute force is not the best way to solve this problem and will rethink it