[R] optimization problem

[Ravi Varadhan]

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.