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
er...@amsterdamoptimization.com
http://amsterdamoptimization.com
----------------------------------------------------------------
On Sat, Jan 16, 2010 at 2:01 PM, Ravi Varadhan <rvarad...@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: rvarad...@jhmi.edu
>
>
> ----- Original Message -----
> From: Erwin Kalvelagen <erwin.kalvela...@gmail.com>
> Date: Saturday, January 16, 2010 1:36 pm
> Subject: Re: [R] optimization problem
> To: Ravi Varadhan <rvarad...@jhmi.edu>
> Cc: r-h...@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
> > er...@amsterdamoptimization.com
> >
> > ----------------------------------------------------------------
> >
> >
> > On Sat, Jan 16, 2010 at 9:59 AM, Ravi Varadhan <rvarad...@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: rvarad...@jhmi.edu
> > >
> > >
> > > ----- Original Message -----
> > > From: Erwin Kalvelagen <erwin.kalvela...@gmail.com>
> > > Date: Saturday, January 16, 2010 2:35 am
> > > Subject: Re: [R] optimization problem
> > > To: r-h...@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
> > > > er...@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]]
______________________________________________
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.
