3

I have a distance (similarity) matrix D, for example, 

D <- matrix(c(0.00, 1.00, 1.00, 0.10, 0.05, 1.00, 0.00, 1.00, 1.00, 1.00, 1.00, 1.00, 0.00, 0.90, 0.95, 0.10, 1.00, 0.90, 0.00, 0.15, 0.05, 1.00, 0.95, 0.15, 0.00),5,5)

and a vector of weights w = (w1, ..., wn) such that sum(w) == 1. The values in the vector w are real and between 0 and 1, inclusively. I need to find a vector w such that the sum w*D*t(w) is maximized. Where t(w) is the transpose of w and the symbol "*" denotes matrix multiplication.

Amazingly enough, I can't find a solver that can do this in R.

Thank you

Rodrigo Guinea
  • 328
  • 4
  • 16
  • 1
    @chinsoon12, I think you're right. See for example section 'Quadratic forms on the unit sphere' [here](http://www.its.caltech.edu/~kcborder/Notes/QuadraticForms.pdf). – Bas May 04 '20 at 08:22
  • 2
    @chinsoon12 I guess `eigen(D)$vectors[,1]` ignored the constraints `sum(w)=1` and `0 <=w<=1` – ThomasIsCoding May 04 '20 at 09:14
  • @chinsoon12 yes, if the maximization problem is non-constrained, then I believe your approach with `eigen` is the most elegant one – ThomasIsCoding May 04 '20 at 09:41

1 Answers1

3

Maybe you can try fmincon from package pracma, e.g.,

library(pracma)
D <- matrix(c(0.00, 1.00, 1.00, 0.10, 0.05, 1.00, 0.00, 1.00, 1.00, 1.00, 1.00, 1.00, 0.00, 0.90, 0.95, 0.10, 1.00, 0.90, 0.00, 0.15, 0.05, 1.00, 0.95, 0.15, 0.00),5,5)
n <- dim(D)[1]
res <- fmincon(rep(1,n),
               fn = function(w) -t(w)%*%D%*%w, 
               A = t(rep(1,n)), 
               b = 1,
               lb = rep(0,n),
               ub = rep(1,n))
w <- res$par

and you will get

> w
[1] 3.333331e-01 3.333338e-01 3.333331e-01 7.008297e-22 0.000000e+00
ThomasIsCoding
  • 96,636
  • 9
  • 24
  • 81