$ontext

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!


---------------------------------------------------------------------------------


This is easily implemented as a MIQP, but depending on the data this may be
difficult to solve to optimality.

$offtext

set i /i1*i25/;
alias (i,j,k);

parameter G(i,j);
G(i,j) = uniform(-1,1);

parameter Id(i,j);
Id(i,i) = 1;

binary variable p(i,j);
variable z;

equation
  norm
  assign1(i)
  assign2(j)
;

* Frobenius norm: http://mathworld.wolfram.com/FrobeniusNorm.html
* we can drop the sqrt as this is a monotonic increasing function
norm..  z =e= sum((i,j), sqr(sum(k, p(i,k)*g(k,j)) - Id(i,j)));


* these assignment constraints make sure P is a permutation matrix
assign1(i).. sum(j, p(i,j)) =e= 1;
assign2(j).. sum(i, p(i,j)) =e= 1;

model m /all/;
option optcr=0;
solve m minimizing z using miqcp;

scalar frobnorm "Frobenius norm";
frobnorm=sqrt(sum((i,j),sqr(sum(k, p.l(i,k)*g(k,j)) - Id(i,j))));
display frobnorm;