[R] optimization problem

[Erwin Kalvelagen]

 <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
erwin at amsterdamoptimization.com
http://amsterdamoptimization.com