在 n 個資產中找到 k 個“最小化”相關矩陣的資產

我正在嘗試找到一種有效的選擇方式 $ k $ 從 $ n $ 相互關聯最小的風險資產。我知道我可以對所有人進行蠻力搜尋 $ k $ 大小的組合 $ n $ 資產，但這不能擴展​​為 $ n $ 增長所以我想知道是否有針對這個問題的優化。

例如，您有以下候選 10 資產 SHW、GOOG、AMZN、WMT、XOM、JNJ、UPS、AMT、AAPL 和 NEE。你會執行什麼 python、matlab 或 R 程式碼（你選擇）來收集每種資產的每日收益，並找到 5 種資產的子集，以最小化這些資產的相關矩陣的條目的平方和的平方根5 資產的回報。

我認為這是一個二進制整數規劃問題（或者可能是凸優化，因為我們正在尋找最小值？），如果錯誤，請更正以下公式。

給定

1. 返回矩陣 $ R $ 在哪裡 $ \left(r_{ij}\right) \in \mathbb{R}^{m \times n} $ 是回報 $ i $ - 第一天和 $ j $ -th 資產和
2. 相關矩陣 $ C = \text{corr}\left( R \right) $ 在哪裡 $ \left(c_{ij}\right) \in \mathbb{R}^{n \times n} $ 是之間的相關係數 $ i $ -th 和 $ j $ -th 資產

我們想找到 $ \vec{x} \in \left{0,1\right}^n $ 英石

1. $ \sum \limits_i^n x_i = k $ 和
2. $ \vec{x} $ 最小化 $ \sqrt{\sum \limits_{i,j}^n {c’}{ij}^{2}} $ ， 在哪裡 $ \left({c’}{ij}\right) \in \mathbb{R}^{n \times n} $ 是來自修改後的相關矩陣的條目 $ C’ $ 對於選擇的資產 $ \vec{x} $ , 由 $ C’= \left(\vec{x} \otimes \vec{x}\right) \odot C $ .

也就是說， $ C’ $ 是 $ C $ 被拒絕資產的行和列“歸零”，由外部產品給出 $ \vec{x} $ 與自己（得到一個矩陣 $ X $ 和 $ x_{i,j} \in \left{0,1\right} = 0 $ 什麼時候 $ \vec{x}i = 0 $ 和 $ x{i,j} = 1 $ 什麼時候 $ \vec{x}_i = 1 $ ) 哈達瑪乘以 $ C $ . 最後我選擇了條目的平方和的平方根 $ C’ $ 但我認為任何距離度量都可以（比如條目絕對值的平均值）。

謝謝。

（我認為 10 個資產中有 5 個只是一個範例，因為在這種情況下，所有組合都可以輕鬆檢查。）

這是一個如何R使用稱為門檻值接受的算法的範例。

library("neighbours")  ## https://github.com/enricoschumann/neighbours
library("NMOF")        ## https://github.com/enricoschumann/NMOF

C我從隨機回報創建一個相關矩陣。（請注意，我使用的觀察很少，因此相關性差異很大。）

C <- cor(randomReturns(na = 10, ns = 20, rho = 0.5, sd = 0.01))
##        [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
##  [1,] 1.000 0.390 0.715 0.645 0.621 0.587 0.701 0.437 0.394 0.219
##  [2,] 0.390 1.000 0.359 0.447 0.496 0.725 0.499 0.218 0.469 0.244
##  [3,] 0.715 0.359 1.000 0.570 0.592 0.506 0.427 0.602 0.495 0.326
##  [4,] 0.645 0.447 0.570 1.000 0.785 0.798 0.646 0.419 0.442 0.655
##  [5,] 0.621 0.496 0.592 0.785 1.000 0.677 0.474 0.319 0.414 0.471
##  [6,] 0.587 0.725 0.506 0.798 0.677 1.000 0.539 0.370 0.378 0.559
##  [7,] 0.701 0.499 0.427 0.646 0.474 0.539 1.000 0.324 0.417 0.433
##  [8,] 0.437 0.218 0.602 0.419 0.319 0.370 0.324 1.000 0.450 0.295
##  [9,] 0.394 0.469 0.495 0.442 0.414 0.378 0.417 0.450 1.000 0.295
## [10,] 0.219 0.244 0.326 0.655 0.471 0.559 0.433 0.295 0.295 1.000

目標函式：給定一個邏輯向量x和一個相關矩陣，計算平方相關之和的平方根。

mean_cor <- function(x, C) {
   tmp <- C[x, x][lower.tri(C[x, x])]
   sqrt(sum(tmp*tmp))
}

所謂鄰域函式。它將通過隨機更改一項資產來更改給定的解決方案。

nb <- neighbourfun(type = "logical", kmin = 5, kmax = 5)

執行算法。

x <- TAopt(mean_cor,
          list(x0 = rep(c(TRUE, FALSE), 5),
               neighbour = nb,
               nI = 200),
          C = C)$xbest

解決方案。

which(x)
## [1]  1  2  8  9 10

C[x, x]
##        [,1]  [,2]  [,3]  [,4]  [,5]
## [1,] 1.000 0.390 0.437 0.394 0.219
## [2,] 0.390 1.000 0.218 0.469 0.244
## [3,] 0.437 0.218 1.000 0.450 0.295
## [4,] 0.394 0.469 0.450 1.000 0.295
## [5,] 0.219 0.244 0.295 0.295 1.000

有關該算法的更多資訊，請參閱SSRN 的本教程。（披露：我是包的維護者NMOF，neighbours我在範例中使用過。）

這確實是一個凸的、二次的、整數規劃問題。其中大多數都是 NP 難的，所以不要為了有效地找到最佳值而絞盡腦汁。也就是說，現在可以使用凸求解器（例如Mosek ）有效地、近似地但高精度地解決這些問題。根據我自己的經驗，這可能適用於數千個資產的規模，例如，在標準零售硬體上具有數百個或更少規模的選定子投資組合。

但也有非常簡單的啟發式解決方案。這些很容易實現，幾乎適用於任何規模 $ n $ 或者 $ k $ ，並且可能會給你一個“足夠好”的解決方案。

啟發式的一些想法：

• 反複試驗：隨機抽樣 $ k $ 出 $ n $ 資產。計算總變異數，重複直到你失去耐心，保留最好的。
• 貪心自下而上：從變異數最小的資產開始，在剩餘的資產中找到下一個 $ n-1 $ 這給你最小的變異數，從剩下的中選擇第三個 $ n-2 $ 等等。
• 貪心自上而下：與自下而上相同，但現在您在每一步中都放棄了一項資產。
• 放鬆：放棄權重為零一的約束，只找到最小變異數的組合。保留 $ k $ 權重最大的資產。我認為這就是@Kermittfrog 的想法。

我確信還有更多的可能性（@Enrico Schumann 的算法、遺傳/進化算法、模擬退火……）。

另請參閱我在 MSE 上的這個相關問題。

引用自：https://quant.stackexchange.com/questions/65680