Hi Klaus, This problem can be cast as a linear sum assignment problem (LSAP), and solved using the `solve_LSAP' function in the "clue" package. I show how to solve a slightly more general problem of finding a permulation of matrix A (n x n) that minimizes the Frobenius distance to a given matrix B (n x n). In your case, B = I. I ran this for n up to 100. It seems to be quite fast.
Here is how you do this: dist <- function(A, B) { # Frobenius norm of A - B n <- nrow(A) sum(abs(B - A)) } pMatrix.min <- function(A, B) { # finds the permutation P of A such that ||PA - B|| is minimum # in Frobenius norm # Uses the linear-sum assignment problem (LSAP) solver # in the "clue" package # Returns P%*%A and the permutation vector `pvec' such that # A[pvec, ] is the permutation of A closest to B n <- nrow(A) D <- matrix(NA, n, n) for (i in 1:n) { for (j in 1:n) { D[j, i] <- sum(abs(B[j, ] - A[i, ])) } } vec <- c(solve_LSAP(D)) list(A=A[vec,], pvec=vec) } #set.seed(123) # Find P such that ||PA - I|| is minimum n <- 100 A <- matrix(rnorm(n*n), n, n) dist(A, diag(n)) B <- pMatrix.min(A, diag(n))$A # B = P%*%A dist(B, diag(n)) # Find P such that ||PA - C|| is minimum C <- matrix(rnorm(n*n), n, n) B <- pMatrix.min(A, C)$A dist(A, C) dist(B, C) Let me know how this works for you. Best, Ravi. ____________________________________________________________________ Ravi Varadhan, Ph.D. Assistant Professor, Division of Geriatric Medicine and Gerontology School of Medicine Johns Hopkins University Ph. (410) 502-2619 email: rvarad...@jhmi.edu ----- Original Message ----- From: klau...@gmx.de Date: Friday, January 15, 2010 9:53 am Subject: [R] optimization problem To: r-help@r-project.org > Dear R-experts, > > this is not a direct R-problem but I hope you can help me anyway. > > I would like to minimize || PG-I || over P, where P is a p x p > permutation matrix (obtained by permuting the rows and/or columns of > the identity matrix), G is a given p x p matrix with full rank and I > the identity matrix. ||.|| is the frobenius norm. > > Does anyone know an algorithm to solve such a problem? And if yes, is > it implemented in R? > > Currently I minimize it by going through all possible permutations - > but this is not feasible for higher dimensional problems as I would > like to consider too. > > Any help is appreciated! > > Thanks in advance, > > Klaus > > -- > Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla > Firefox 3.5 - > sicherer, schneller und einfacher! > > ______________________________________________ > R-help@r-project.org mailing list > > PLEASE do read the posting guide > and provide commented, minimal, self-contained, reproducible code. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.