2

I am trying to solve the following inequality constraint:

Given time-series data for N stocks, I am trying to construct a portfolio weight vector to minimize the variance of the returns.

the objective function:

min w^{T}\sum w
s.t. e_{n}^{T}w=1
\left \| w \right \|\leq C

where w is the vector of weights, \sum is the covariance matrix, e_{n}^{T} is a vector of ones, C is a constant. Where the second constraint (\left \| w \right \|) is an inequality constraint (2-norm of the weights).

I tried using the nloptr() function but it gives me an error: Incorrect algorithm supplied. I'm not sure how to select the correct algorithm and I'm also not sure if this is the right method of solving this inequality constraint.

I am also open to using other functions as long as they solve this constraint.

Here is my attempted solution:

data <- replicate(4,rnorm(100))
N <- 4
fn<-function(x) {cov.Rt<-cov(data); return(as.numeric(t(x) %*%cov.Rt%*%x))}     
eqn<-function(x){one.vec<-matrix(1,ncol=N,nrow=1); return(-1+as.numeric(one.vec%*%x))}


C <- 1.5
ineq<-function(x){
  z1<- t(x) %*% x
  return(as.numeric(z1-C))  
}   

uh <-rep(C^2,N)
lb<- rep(0,N)
x0 <- rep(1,N)

local_opts <- list("algorithm"="NLOPT_LN_AUGLAG,",xtol_rel=1.0e-7)
opts <- list("algorithm"="NLOPT_LN_AUGLAG,",
             "xtol_rel"=1.0e-8,local_opts=local_opts)
sol1<-nloptr(x0,eval_f=fn,eval_g_eq=eqn, eval_g_ineq=ineq,ub=uh,lb=lb,opts=opts)
user3742038
  • 77
  • 1
  • 8
  • Maybe "Minimizing quadratic function subject to norm inequality constraint." I'm going to delete my answer since it doesn't really get you there! – Matthew Gunn Dec 09 '15 at 08:11
  • You seem to have a typo in your code. There is an extraneous comma in "NLOPT_LN_AUGLAG," – Dhanesh Dec 22 '15 at 04:11

2 Answers2

2

This looks like a simple QP (Quadratic Programming) problem. It may be easier to use a QP solver instead of a general purpose NLP (NonLinear Programming) solver (no need for derivatives, functions etc.). R has a QP solver called quadprog. It is not totally trivial to setup a problem for quadprog, but here is a very similar portfolio example with complete R code to show how to solve this. It has the same objective (minimize risk), the same budget constraint and the lower and upper-bounds. The example just has an extra constraint that specifies a minimum required portfolio return.

Actually I misread the question: the second constraint is ||x|| <= C. I think we can express the whole model as:

enter image description here

This actually looks like a convex model. I could solve it with "big" solvers like Cplex,Gurobi and Mosek. These solvers support convex Quadratically Constrained problems. I also believe this can be formulated as a cone programming problem, opening up more possibilities.

Here is an example where I use package cccp in R. cccp stands for Cone Constrained Convex Problems and is a port of CVXOPT.

enter image description here

Community
  • 1
  • 1
Erwin Kalvelagen
  • 15,677
  • 2
  • 14
  • 39
  • Thanks for your help. Please correct me if I'm wrong: I tried using quadprog before but my understand is that it can only handle linear constraints. My constraint is a non-linear one. Do you think that's still doable using quadprog? – user3742038 Dec 09 '15 at 18:27
  • Sorry, The math did not render correctly in my browser. You want the sum of squares of w(i) to be bounded. Indeed that makes the model nonlinearly constrained (may be even nonconvex). I believe that is a somewhat unusual constraint for a portfolio model. Can you tell me how you came up with that constraint? My answer is not completely valid, but it still may be of use to find a good starting point for the full nonlinearly constrained problem. I often use a simpler version of the model to find a good starting point for a more complicated model. – Erwin Kalvelagen Dec 09 '15 at 18:39
  • This constraint comes from DeMiguel et al. See page 8: http://www.usc.edu/schools/business/FBE/seminars/papers/F_11-14-08_UPPAL-DGNU.pdf – user3742038 Dec 09 '15 at 18:44
  • Thanks ! I think a solution for Mosek would already be great help. I could then call Mosek from R. – user3742038 Dec 09 '15 at 22:02
  • I tried the above QCP model with GAMS + Mosek, and it solved just fine. – Erwin Kalvelagen Dec 09 '15 at 22:08
  • Do you think this is translatable using quadprog? – user3742038 Dec 09 '15 at 22:40
  • The 2-norm constraint probably not. But the paper mentions using the 1-norm. This can be linearized. – Erwin Kalvelagen Dec 10 '15 at 03:05
  • Should I post this problem to math stackexchange asking how to linearize this constraint? – user3742038 Dec 10 '15 at 07:19
  • My permission is not needed for that! – Erwin Kalvelagen Dec 10 '15 at 09:26
  • I'm just asking you if I understand the problem correclty :) – user3742038 Dec 10 '15 at 09:27
  • Please go ahead. It always helps to formulate a proper question (forces to organize ones thoughts) and to get some feedback. – Erwin Kalvelagen Dec 10 '15 at 09:46
  • I added a cone formulation using R's cccp. It gives the same solution as the quadratically constrained version. – Erwin Kalvelagen Dec 10 '15 at 16:30
  • Thanks a lot, this is really helpful! – user3742038 Dec 10 '15 at 20:24
1

The 2-norm of weights doesn't make sense. It has to be the 1-norm. This is essentially a constraint on the leverage of the portfolio. 1-norm(w) <= 1.6 implies that the portfolio is at most 130/30 (Sorry for using finance language here). You want to read about quadratic cones though. w'COV w = w'L'Lw (Cholesky decomp) and hence w'Cov w = 2-Norm (Lw)^2. Hence you can introduce the linear constraint y - Lw = 0 and t >= 2-Norm(Lw) [This defines a quadratic cone). Now you minimize t. The 1-norm can also be replaced by cones as abs(x_i) = sqrt(x_i^2) = 2-norm(x_i). So introduce a quadratic cone for each element of the vector x.

tschm
  • 2,905
  • 6
  • 33
  • 45