$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.
This version implements an assignment problem giving the same solution.
$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;
parameter c(i,j);
c(i,j) = sum(k, sqr(Id(i,k)-G(j,k)));
equation cassign;
cassign.. z =e= sum((i,j),c(i,j)*p(i,j));
model assign/assign1,assign2,cassign/;
solve assign minimizing z using rmip;
scalar frobnorm "Frobenius norm";
frobnorm=sqrt(sum((i,j),sqr(sum(k, p.l(i,k)*g(k,j)) - Id(i,j))));
display frobnorm;