optimization problem

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: rvaradhan at jhmi.edu


----- Original Message -----
From: klausch at gmx.de
Date: Friday, January 15, 2010 9:53 am
Subject: [R] optimization problem
To: r-help at 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 at r-project.org mailing list
 
 PLEASE do read the posting guide 
 and provide commented, minimal, self-contained, reproducible code.