<klausch <at> gmx.de> writes: > > 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 >
This could be modeled as a MIQP problem: min sum((i,j),sqr(V(i,j))) v(i,j) = sum(k, P(i,k)*G(k,j)) - Id(i,j); sum(i, P(i,j)) = 1 sum(j, P(i,j)) = 1 P(i,j) in {0,1} If you have access to Cplex then http://cran.r- project.org/web/packages/Rcplex/Rcplex.pdf can help. If you can use a different norm it may be possible to use linear MIP technology allowing a wider range of solvers. This is combinatorial, so for p > 20 say it may become slow (this also depends on the data). Erwin ---------------------------------------------------------------- Erwin Kalvelagen Amsterdam Optimization Modeling Group er...@amsterdamoptimization.com http://amsterdamoptimization.com ______________________________________________ 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.