0

I'm trying to solve the following quadratic programming problem:

 minw wTΣw,
s.t. wTe = 1,
st. ‖w‖1 ≤ δ

Where A is an identity matrix, Sigma is a covariance matrix and e is a vector of ones.

The first constraint ensures that the solution adds up to one.

The second constraint ensures that the sum of absolute values (1-norm) of the solution is less than or equal to a certain constant.

I tried to solve this the following way: 

library(Rsolnp)
#Generate some sample data
N=100
sample.data <- replicate(N,rnorm(1000,0,1))

#specify optimization problem  


fn<-function(x) {cov.Rt<-cov(sample.data); return(as.numeric(t(x)%*%cov.Rt%*%x))}

#specify equality constraint   


eqn<-function(x){one.vec<-matrix(1,ncol=N,nrow=1);return(as.numeric(one.vec%*%x))}

constraints<-1

#specify inequality constraint


ineq<-function(x){one.vec<-matrix(1,ncol=N,nrow=1);
  z1<-one.vec%*%abs(x)
  return(as.numeric(z1))
      }
#specify lower and upper bounds

uh<-2
lb<-1

#specify starting vector of "w"
    x0<-matrix(1/N,N,1)

#solve quadratic optimization problem: 

control <- list("trace"="0")
sol1<-solnp(pars=x0,fun=fn,eqfun=eqn,eqB=constraints, ineqfun=ineq,ineqUB=uh,ineqLB=lb,control=control)

I would like to know:

  1. Is this solution correct?

  2. Are there alternative (simpler) ways to solve it? The solution using solnp() takes forever for larger tasks.

Armali
  • 18,255
  • 14
  • 57
  • 171
tzi
  • 67
  • 1
  • 5
  • `sum(i, w(i)^2) <= delta` is not completely the same as requiring that the sum of the absolute values is less than `delta`. The first is really non-linear, the second form can be linearized. – Erwin Kalvelagen Dec 12 '16 at 02:16
  • Thanks for your help! There was a mistake in the math formula. I corrected the inequality constraint in the formula. I do actually want the sum of absolute values to be less than delta. Does that clarify? – tzi Dec 12 '16 at 07:44
  • My problem is that running this 100 times takes around 30 hours. If the code is correct, is there any way to implement it (using e.g. another solver) that doesn't take so long? Or is this inherently such a slow thing to solve? – tzi Dec 12 '16 at 07:45
  • After linearizing `sum(i, abs(w(i))<= delta` you can use a (good) convex QP solver. Typically such a model solves very quickly. – Erwin Kalvelagen Dec 12 '16 at 09:09
  • You mean solve.qp for example? Could you explain how this problem could be linearized and specified in the Amat and bvec arguments of solve.qp? My matrix knowledge is too limited for imposing the inequality. solnp() was much more intuitive in this sense. I can modify the question to ask for a solution using solve.qp if that helps. But I would really appreciate if you could explain how to impose these two constraints. – tzi Dec 12 '16 at 09:13
  • I just found that you already answered this problem: http://stackoverflow.com/questions/34165200/minimizing-quadratic-function-subject-to-norm-inequality-constraint/34654340#34654340 – tzi Dec 12 '16 at 13:57
  • Feel free to close this question if you agree that it answers my question. – tzi Dec 12 '16 at 13:58

0 Answers0