# discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} x_{\I}.$$ Here

• $$\I \subseteq [d] = \{1, 2, \dots, d\}$$;
• $$x \in \R^d$$ is a fixed vector;
• $$\Sigma \in \R^{d \times d}$$ is a fixed positive-definite matrix;
• $$x_{\I} \in \R^{|\I|}$$, $$\Sigma_{\I} \in \mathbb R^{|\I| \times |\I|}$$ are the subsets of $$x$$ and $$\Sigma$$ obtained by taking only the rows and columns corresponding to the indices in $$\I$$;
• $$d$$ is potentially fairly large (between hundreds and maybe hundreds of thousands); $$k$$ is fairly small (up to maybe 20-50).

My first thought was a greedy algorithm – using the block matrix inverse formula, it's straightforward to work out $$f(\I \cup \{ i \})$$ in terms of $$\Sigma_\I^{-1}$$, and it all seems feasible computationally. Unfortunately, though, I found a counterexample showing $$f(\I)$$ isn't submodular, so the greedy approach may not work so well.

I'm interested in practical algorithms and/or algorithms with guarantees (ideally both). Is this problem studied in the literature already / what kinds of optimization algorithms should I be looking at other than just plain greedy?

P.S: If it helps, you can assume that $$x$$ is a sample from a normal distribution with mean 0 and covariance $$\Sigma$$; ideally, the algorithm would work well with high probability over the sample $$x$$.

• Is $\Sigma_{\mathcal{I}}$ guaranteed to be invertible? Under the current conditions, if there is 0 on the diagonal of $\Sigma$, then this property may not hold. In that case, what do you define $f(\mathcal{I})$ to be? Nov 23 at 10:40
• @nirshahar, $\Sigma$ is a covariance matrix, it has $1$ on the diagonal. Nov 23 at 12:07
• co-author on the research here: It's a covariance, not a correlation, but $\Sigma$ is strictly positive definite and so $\Sigma_{\mathcal I}$ is guaranteed to be strictly positive definite as well. Nov 23 at 19:20
• On second thought, you can absorb the scaling of $\Sigma$ into $x$ and so make $\Sigma$ a correlation matrix, if that's more convenient. Nov 23 at 20:22

Not sure this leads to a practical solution, but is another way to approach the problem. Let $$c_{ij}$$ be the element in row $$i$$ and column $$j$$ of the "full" matrix $$x^T \Sigma^{-1} x$$. Then solve this Integer Program: $$\max \sum_{i=1}^d \sum_{j=1}^d c_{ij} y_{ij}$$ subject to $$y_{ij} \le u_i \ \hbox{and} \ y_{ij}\le u_j, \ \forall i,j$$ $$\sum_{i=1}^d u_i \le k$$ $$u_i \in \{0,1\}, \ y_{ij}\ge 0$$ The variable $$u$$ just picks out which rows & columns you are going to put in the set $$\mathcal I$$. If the integer program is too hard to solve, solving the linear program might lead you near a good solution in practice.

Another interpretation: You're asked to pick $$k$$ assets out of $$d$$ that maximize the variance of the portfolio (in absolute or dollar terms). If this was in relative terms, then you'd always just pick the most volatile asset on its own (adding any other asset would reduce the relative vol, assuming nothing is perfectly correlated). But in dollar terms, you get more risk with more money invested. So seems very close to a Markowitz Mean-Variance kind of question.

New contributor
TickaJules is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• I'm not clear on what you mean by "the full matrix $x^\top \Sigma^{-1} x$". That expression evaluates to a number, not a matrix. Right? Or am I misunderstanding something?
– D.W.
Nov 25 at 2:24
• Also, $(\Sigma_I)^{-1}$ is not the same as $(\Sigma^{-1})_I$, which I think makes any approach of the sort you outline here ineffective. It looks like you are trying to maximize $x_I^\top (\Sigma^{-1})_I x_I$, but the problem statement says to maximize $x_I^\top (\Sigma_I)^{-1} x_I$, which is different. As a result, I don't think your approach works.
– D.W.
Nov 25 at 2:26
• Ah yes, I misread it. That makes it harder. My answer doesn't work then. Nov 25 at 2:36