Skip to main content
4 of 4
Fully Math Jaxed
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

How to extract 'top k' multiple solutions from a quadratic optimization problem?

Imagine we are interested in the following problem:

$$ \min_{w} \left( w^T V w + \lambda \|w\| \right) \\ \text{s.t. } w^T R \geq c $$

Where 𝑤 is an $N \times 1$ vector, $V$ is an $N \times N$ covariance matrix, and 𝜆 is a regularisation parameter

Suppose further that out of these $N$ items, however, some of them are very highly correlated (almost, but not fully, collinear).

I'm not interested in obtaining the unique best solution here, but instead in ways to extract multiple "$K$" (ideally sparse) near optimal solution vectors. What are ways to go about this problem?

Have thought about random random perturbations (or partitions) to the $V$ matrix, but I was wondering if someone can help think of less 'empirical' approaches. Could eigen-decomposition be used to assist in extracting orthogonal solutions?

Thanks!