0

I have created some sample code for an optimization problem I am struggling with. The idea is that I have a vector of length 100 which represents various assets. Each asset has a factor associated with it. There is a vector of current assets held and their allocation percentages. Since this is a portion of a greater budget, this allocation sums to some value less than 100%. The objective is to move the assets around such that the allocation (70% in this problem) remains the same and that the target weighted average factor value is reached as close as possible. An additional constraint is that no more than 5 transactions can be made. This means you could reduce one asset and add another, and that would be 2 transactions.

The problem is when I run this optimization, it produces the initial weightings. I suspect it is because as soon as a change is made, the value_constraint is violated. Does anyone have any recommendations for how to approach this problem?

This is the code you can use to run the model, I have included a made up scenario (test case) where two assets are traded for 2 different ones, if it's not helpful for you feel free to ignore it, but this scenario meets both constraints, and with seed(1) produces a worse result. 

set.seed(1)

number_of_assets <- 100
max_transactions <- 5
sum_of_assets_value <- 0.70

factors <- runif(number_of_assets, 0, 10)

current_weights <- c(rep(sum_of_assets_value/5, 5), rep(0, number_of_assets-5))
current_factor <- current_weights %*% factors

lower_bound <- -current_weights
upper_bound <- rep(sum_of_assets_value, number_of_assets)


#test model manually with simple scenario
weights <- c(rep(0, 2), rep(sum_of_assets_value/5, 5), rep(0, number_of_assets-7)) #test case for functionality
change_count_constraint <- sum((current_weights^2 - weights^2)^2 > 0) <= max_transactions #constraint should be met with only 4 assets changed
total_value_constraint <- sum(weights) == sum_of_assets_value # constraint is met since weights sum to desired amount
new_factor <- weights %*% factors #new factor from the test case
target_factor <- 1.5 #target factor for testing
difference <- (target_factor - new_factor)^2 #square the difference, since we are attempting to minimize the absolute value of the difference
#end test case


 #this is the function for the optimization, includes the two constraints and assigns a penalty if violated
evalFunc <- function(optweights){
  new_factor <- optweights %*% factors

  count_constraint <- sum((current_weights^2 - optweights^2)^2 > 0) <= max_transactions
  value_constraint <- sum(optweights) == sum_of_assets_value
  if(count_constraint == FALSE | value_constraint == FALSE){penalty <- 100000}

  result <- (target_factor - new_factor)^2 + penalty
  result
}


optimization <- optim(current_weights, #starting weights
                      evalFunc, 
                      lower=lower_bound, upper=upper_bound, 
                      method="L-BFGS-B", 
                      control= list(maxit=5000))
rrbest
  • 1,619
  • 3
  • 14
  • 22
  • 1
    I think the problem is that whatever the optimizer tries, `sum(optweights) == sum_of_assets_value` will be FALSE hence penalized. Instead, you need to make the penalty a growing function of the distance between the sums, so the optimizer can learn where to go. To some extent, the other penalty (max transactions) could be modeled in a similar way. – flodel May 22 '13 at 21:48
  • @flodel Can you explain why this is? In the test scenario I put together the results are TRUE, so I am curious if this is something unique to the optimizer or something about computer science I should know – rrbest May 22 '13 at 22:00
  • 1
    The optimizer does not know you want `sum(optweights) == sum_of_assets_value`, it would have to learn about it by evaluating your cost function with different guesses. The way you have the penalty modeled, there is nothing that will hint to move `sum(opt weights)` towards `sum_of_assets_value`. Also, yes, the probability to hit exactly `sum(optweights) == sum_of_assets_value` is zero if you account for floating point errors. – flodel May 22 '13 at 22:18
  • 1
    For floating point numbers never being equal when you think they should, see, for instance [this question](http://stackoverflow.com/questions/9508518/why-are-these-numbers-not-equal/). – Vincent Zoonekynd May 22 '13 at 22:24
  • 2
    The count constraint is more worrying: it makes your problem an [integer program](http://en.wikipedia.org/wiki/Integer_programming). You can try to solve those problems with a [branch-and-cut algorithm](http://en.wikipedia.org/wiki/Branch_and_cut) (that requires many optimizations) or some form of local search (genetic algorithm, simulated annealing, etc. -- that is easier to implement). – Vincent Zoonekynd May 22 '13 at 22:29
  • 1
    Finally, I don't think your problem is very well posed. There must be infinitely many solutions and building one by hand is super easy, no? You want to reduce your "total factor"? Then start selling your asset with highest factor and buy the one with smallest factor. If you can't reach your target after selling all of that first asset, then start over with your asset with second highest factor, etc. – flodel May 22 '13 at 22:51
  • @flodel - I've simplified the problem a bit for the post, but there are actually 10 factors for each asset, and there is another constraint that the sum of the factor values also has a target. Manually, the trouble comes when getting the sum of factors and the allocation to hit the required targets simultaneously. Maybe factor isn't the best word... but think Asset 1 has a total value of 5, of which 2 comes from factor A, 2 comes from factor B and 1 comes from factor C. There is a required target for the total value and weighting, but also desired targets for each factor and total transactions – rrbest May 23 '13 at 15:17

0 Answers0