portfolio optimization sorting efficient solutions C#

Question

I have the following problem to solve:

Let H be a set of portfolios. For each portfolio i in H let (ri,vi) be the (return,risk) values for this solution.

For each i in H if there exists j in H (j is different from i) such that rj>=ri and vj<=vi then delete i from H. because i is dominated by j (it has better return for less risk).

At the end H will be the set of undominated efficient solutions.

I tried to solve the above problem using linq:

 H.RemoveAll(x => H.Any(y => x.CalculateReturn() <= y.CalculateReturn() && x.CalculateRisk() >= y.CalculateRisk() && x != y));

But I wonder if there exist a more efficient way, because if H.Count() is of the order of ten thousands, then it takes a lot of time to remove the dominated portfolios.

Thanks in advance for any help !

Christos

Answer 1

First off, you should be caching the Risk/Reward. I can't tell if you are by your code sample, but if you aren't you need to transform the list first.

Once you've done that, it makes sense to order the list according to the risk. As you increase risk, then, all you have to check is that your reward is strictly greater than the best reward you've seen so far. If it's not, you can remove it. That should dramatically improve performance.

Unfortunately, I'm not feeling clever enough to think of a way to do this with pure LINQ at the moment, but this code segment should work:

(Disclaimer: I haven't compiled/tested)

var orderedH = (
  from h in H
  let reward = h.CalculatedReward()
  let risk = h.CalculatedRisk()
  orderby risk ascending
  select new {
    Original = h,
    Risk = risk,
    Reward = reward
}).ToList();

var maxReward = Double.NegativeInfinity;
for (int i = 0; i < orderedH.Count; i++)
{
  if (orderedH[i].Reward <= maxReward) {
    orderedH.RemoveAt(i--);
  }
  else {
    maxReward = orderedH[i].Reward;
  }
}

var filteredPortfolio = orderedH.Select(h => h.Original);