No, I cannot find counterexamples, so that actually seems to give identical
solutions! That is fantastic.

I guess my homework is now convince myself  we can go from this quadratic
objective

sum_i,j [ sum_k P[i,k]*G[k,j] - I[i,j] ]^2

to a linear one:

sum_i,j c[i,j]*P[i,j]

Thanks !

Erwin

----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin@amsterdamoptimization.com
http://amsterdamoptimization.com
----------------------------------------------------------------


On Sat, Jan 16, 2010 at 11:42 PM, Ravi Varadhan <rvaradhan@jhmi.edu> wrote:

>
> Interesting!
>
> Now, if I change the "cost matrix", D,  in the LSAP formulation slightly
> such that it is quadratic, it finds the best solution to your example:
>
>
> 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] <- sqrt(sum((B[j, ] - A[i, ])^2))
>        D[j, i] <- (sum((B[j, ] - A[i, ])^2))  # this is better
>         } }
> vec <- c(solve_LSAP(D))
> list(A=A[vec,], pvec=vec)
> }
>
>  > X<-pMatrix.min(A,B)
> > X$pvec
> [1] 6 1 3 2 4 5
> > dist(X$A, B)
> [1] 10.50172
> >
>
> This should be fine.  Any counter-examples to this?!
>
> 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@jhmi.edu
>
>
> ----- Original Message -----
> From: Erwin Kalvelagen <erwin.kalvelagen@gmail.com>
> Date: Saturday, January 16, 2010 5:26 pm
> Subject: Re: [R] optimization problem
> To: Ravi Varadhan <rvaradhan@jhmi.edu>
> Cc: r-help@stat.math.ethz.ch
>
>
> > I believe this is a very good approximation but not a 100% correct
> > formulation of the original problem.
> >
> > E.g. for
> >
> >
> > A <- matrix(c(
> >    -0.62668585718,-0.78785288063,-1.32462887089, 0.63935994044,
> >    -1.99878497801, 4.42667400292, 0.65534961645, 1.86914537669,
> >    -0.97229929674, 2.37404268115, 0.01223810011,-1.24956493590,
> >     0.92711756473,-1.51859351813, 3.76707054743,-2.30641777527,
> >    -1.98918429361,-0.43634856903,-3.65989556798, 0.00073904070,
> >    -1.44153837918, 1.42004180214,-1.81388322489,-1.92423923917,
> >    -1.46322482727,-1.81783134835,-2.59801302663, 2.03462135096,
> >     1.32546711550,-0.21519150247,-1.94319654347, 0.68773346973,
> >    -2.75094791807,-1.44814080195, 3.14197123843,-0.52521369103
> > ),nrow=6)
> >
> > B<-diag(nrow=6)
> >
> > X<-pMatrix.min(A,B)
> >
> > dist(X$A, B)
> >
> > X$pvec
> >
> > bestpvec <- c(6,1,3,2,4,5)
> >
> > dist(A[bestpvec,],B)
> >
> > you get a norm of 10.58374 while the true optimal norm is 10.50172.  For
> > small problems you often get the optimal solution, but the error
> > caused by
> > linearizing the objective becomes larger if the problems are larger.
> > But the
> > approximation is actually very good.
> >
> > Erwin
> >
> >
> > ----------------------------------------------------------------
> > Erwin Kalvelagen
> > Amsterdam Optimization Modeling Group
> > erwin@amsterdamoptimization.com
> >
> > ----------------------------------------------------------------
> >
> >
> > On Sat, Jan 16, 2010 at 2:01 PM, Ravi Varadhan <rvaradhan@jhmi.edu>
> wrote:
> >
> > >
> > > Yes, it can be formulated as an LSAP.  It works just fine.  I have
> checked
> > > it with several 3 x 3 examples.
> > >
> > > Here is another convincing example:
> > >
> > > n <- 50
> > >
> > > A <- matrix(rnorm(n*n), n, n)
> > >
> > > > # Find P such that ||PA - C|| is minimum
> > >
> > > vec <- sample(1:n, n, rep=FALSE)  # a random permutation
> > >
> > > C <- A[vec, ]  # the target matrix is just a permutation of original
> > matrix
> > >
> > > B <- pMatrix.min(A, C)$A
> > >
> > > > dist(B, C)
> > > [1] 0
> > >
> > > > dist(A, C)
> > > [1] 69.60859
> > >
> > > 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@jhmi.edu
> > >
> > >
> > > ----- Original Message -----
> > > From: Erwin Kalvelagen <erwin.kalvelagen@gmail.com>
> > > Date: Saturday, January 16, 2010 1:36 pm
> > > Subject: Re: [R] optimization problem
> > > To: Ravi Varadhan <rvaradhan@jhmi.edu>
> > > Cc: r-help@stat.math.ethz.ch
> > >
> > >
> > > > I also have doubts this can be formulated correctly as a linear
> > > assignment
> > > > problem. You may want to check the results with a small example.
> > > >
> > > > Erwin
> > > >
> > > > ----------------------------------------------------------------
> > > > Erwin Kalvelagen
> > > > Amsterdam Optimization Modeling Group
> > > > erwin@amsterdamoptimization.com
> > > >
> > > > ----------------------------------------------------------------
> > > >
> > > >
> > > > On Sat, Jan 16, 2010 at 9:59 AM, Ravi Varadhan <rvaradhan@jhmi.edu>
> > > wrote:
> > > >
> > > > >
> > > > > Thanks, Erwin, for pointing out this mistake.
> > > > >
> > > > > Here is the correct function for Frobenius norm.
> > > > >
> > > > > Klaus - Just replace the old `dist' with the following one.
> > > > >
> > > > > dist <- function(A, B) {
> > > > >  # Frobenius norm of A - B
> > > > >  n <- nrow(A)
> > > > >  sqrt(sum((B - A)^2))
> > > > >  }
> > > > >
> > > > > 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@jhmi.edu
> > > > >
> > > > >
> > > > > ----- Original Message -----
> > > > > From: Erwin Kalvelagen <erwin.kalvelagen@gmail.com>
> > > > > Date: Saturday, January 16, 2010 2:35 am
> > > > > Subject: Re: [R] optimization problem
> > > > > To: r-help@stat.math.ethz.ch
> > > > >
> > > > >
> > > > > > Ravi Varadhan <rvaradhan <at> jhmi.edu> writes:
> > > > > > > dist <- function(A, B) {
> > > > > > > # Frobenius norm of A - B
> > > > > > >     n <- nrow(A)
> > > > > > >     sum(abs(B - A))
> > > > > > > }
> > > > > > >
> > > > > >
> > > > > > See  for a definition of the
> > > > > > Frobenius norm.
> > > > > >
> > > > > >
> > > > > > Erwin
> > > > > >
> > > > > > ----------------------------------------------------------------
> > > > > > Erwin Kalvelagen
> > > > > > Amsterdam Optimization Modeling Group
> > > > > > erwin@amsterdamoptimization.com
> > > > > >
> > > > > >
> > > > > > ______________________________________________
> > > > > > R-help@r-project.org mailing list
> > > > > >
> > > > > > PLEASE do read the posting guide
> > > > > > and provide commented, minimal, self-contained, reproducible
> code.
> > > > >
> > >
>

	[[alternative HTML version deleted]]

