通过置换 R 中的列来最大化矩阵的对角线

Question

我正在使用 R 中的方阵，我们可以称它为mat，并且想要排列列（即改变它们的顺序）以最大化对角线元素的总和。我想通过线性规划方法来做到这一点，即依靠优化包 lpSolve。代码解决方案当然值得赞赏，但如果失败，任何将其表述为线性规划问题的帮助将不胜感激。

我的问题类似于这个问题：置换方形 2 向列联表（矩阵）的列以最大化其对角线. 但是，在那个问题以及我在 SO 上发现的其他问题中，按行最大化该行中的对角线元素就足够了。问题是像

mat2 <- mat[,max.col(mat, 'first')]

不会对我有用：你可能会遇到这样的情况：一行有多个相等的最大值，或者（比如）在第 X 行中，你在对角线上选择 11 而不是 10，但因此在第 X+1 行你被迫有5 在对角线上而不是 30，因为 30 与 10 属于同一列。

我知道有一种称为匈牙利算法的算法可以执行此操作，但是除了 lpSolve 之外，我无法使用任何包来应对此挑战。

Answer 1

矩阵的列置换A 对应于矩阵乘法AP，其中P是置换矩阵（置换单位矩阵）。于是我们可以建立如下数学模型：

第一个约束是Y=AP。对P确定的约束P是一个适当的置换矩阵（每行和每列一个 1）。目标最大化列置换矩阵Y的迹（矩阵的迹是其对角线元素的总和）。

请注意，我们可以优化此公式（所有y[i,j]withi<>j均未使用，我们可以替换剩余的 y）。

一些 R 代码来试试这个：

library(CVXR)

# random matrix A
set.seed(123)
n <- 10
A <- matrix(runif(n^2,min=-1,max=1),nrow=n,ncol=n)

# decision variables
P <- Variable(n,n,boolean=T)
Y <- Variable(n,n)

# optimization model
# direct translation of the mathematical model given above
problem <- Problem(Maximize(matrix_trace(Y)),
                   list(Y==A %*% P,
                        sum_entries(P,axis=1) == 1,
                        sum_entries(P,axis=2) == 1))

# solve and print results
result <- solve(problem)
cat("status:",result$status)
cat("objective:",result$value)

在这个例子中，我们从矩阵开始

             [,1]        [,2]        [,3]        [,4]       [,5]       [,6]       [,7]        [,8]       [,9]       [,10]
 [1,] -0.42484496  0.91366669  0.77907863  0.92604847 -0.7144000 -0.9083377  0.3302304  0.50895032 -0.5127611 -0.73860862
 [2,]  0.57661027 -0.09333169  0.38560681  0.80459809 -0.1709073 -0.1155999 -0.8103187  0.25844226  0.3361112  0.30620385
 [3,] -0.18204616  0.35514127  0.28101363  0.38141056 -0.1725513  0.5978497 -0.2320607  0.42036480 -0.1647064 -0.31296706
 [4,]  0.76603481  0.14526680  0.98853955  0.59093484 -0.2623091 -0.7562015 -0.4512327 -0.99875045  0.5763917  0.31351626
 [5,]  0.88093457 -0.79415063  0.31141160 -0.95077263 -0.6951105  0.1218960  0.6292801 -0.04936685 -0.7942707 -0.35925352
 [6,] -0.90888700  0.79964994  0.41706094 -0.04440806 -0.7223879 -0.5869372 -0.1029673 -0.55976223 -0.1302145 -0.62461776
 [7,]  0.05621098 -0.50782453  0.08813205  0.51691908 -0.5339318 -0.7449367  0.6201287 -0.24036692  0.9699140  0.56458860
 [8,]  0.78483809 -0.91588093  0.18828404 -0.56718413 -0.0680751  0.5066157  0.6247790  0.22554201  0.7861022 -0.81281003
 [9,]  0.10287003 -0.34415856 -0.42168053 -0.36363798 -0.4680547  0.7900907  0.5886846 -0.29640418  0.7729381 -0.06644192
[10,] -0.08677053  0.90900730 -0.70577271 -0.53674843  0.7156554 -0.2510744 -0.1203366 -0.77772915 -0.6498947  0.02301092

这有trace(A)=0.7133438.

Y 变量具有排列的列：

             [,1]        [,2]        [,3]        [,4]        [,5]        [,6]       [,7]       [,8]       [,9]      [,10]
 [1,]  0.92604847 -0.73860862  0.50895032  0.77907863 -0.42484496  0.91366669 -0.5127611  0.3302304 -0.9083377 -0.7144000
 [2,]  0.80459809  0.30620385  0.25844226  0.38560681  0.57661027 -0.09333169  0.3361112 -0.8103187 -0.1155999 -0.1709073
 [3,]  0.38141056 -0.31296706  0.42036480  0.28101363 -0.18204616  0.35514127 -0.1647064 -0.2320607  0.5978497 -0.1725513
 [4,]  0.59093484  0.31351626 -0.99875045  0.98853955  0.76603481  0.14526680  0.5763917 -0.4512327 -0.7562015 -0.2623091
 [5,] -0.95077263 -0.35925352 -0.04936685  0.31141160  0.88093457 -0.79415063 -0.7942707  0.6292801  0.1218960 -0.6951105
 [6,] -0.04440806 -0.62461776 -0.55976223  0.41706094 -0.90888700  0.79964994 -0.1302145 -0.1029673 -0.5869372 -0.7223879
 [7,]  0.51691908  0.56458860 -0.24036692  0.08813205  0.05621098 -0.50782453  0.9699140  0.6201287 -0.7449367 -0.5339318
 [8,] -0.56718413 -0.81281003  0.22554201  0.18828404  0.78483809 -0.91588093  0.7861022  0.6247790  0.5066157 -0.0680751
 [9,] -0.36363798 -0.06644192 -0.29640418 -0.42168053  0.10287003 -0.34415856  0.7729381  0.5886846  0.7900907 -0.4680547
[10,] -0.53674843  0.02301092 -0.77772915 -0.70577271 -0.08677053  0.90900730 -0.6498947 -0.1203366 -0.2510744  0.7156554

我们有trace(Y)=7.42218。这是我们能做的最好的（已证明）。