Sunday, April 11, 2010

L1 portfolio formulation

In the paper “Mean-Absolute Deviation Portfolio Optimization Model and Its Applications to Tokyo Stock Market,” Hiroshi Konno and Hiroaki Yamazaki, Management Science, Vol. 37, No. 5 (May, 1991), pp. 519-531 (http://www.jstor.org/pss/2632458) the following Linear Programming model is presented:

Here x(j) is the allocation (the variable we are interested in), and y(t) are auxiliary variables. The data are:

• a(j,t) are mean adjusted returns
• M0 is the budget
• rho is the required return
• r(j) are the stock returns

This model is in fact almost identical to what is presented in this blog before: http://yetanothermathprogrammingconsultant.blogspot.com/2009/07/ms-solver-foundation-excel-interface_07.html. Actually the formulation in the paper by Konno e.a. is slightly non-optimal: the big data block sum(j, a(j,t)*x(j)) is present twice in the model. For large data sets this can be felt in larger solution times. Hence a slightly better formulation could be:

On a synthetic data set with n=2000 stocks and T=300 observations we have:

 Model Konno ea Improved variables 2300 2600 equations 602 302 nonzero elements 1,204,900 605,200 simplex iterations 2031 1224 solution time 8.9 2.97

GAMS/Gurobi did not really like my improved formulation:

 Starting Gurobi... Optimize a model with 302 Rows, 2600 Columns and 604600 NonZeros Presolve time: 0.34s Iteration    Objective       Primal Inf.    Dual Inf.      Time        0    0.0000000e+00   1.320000e+00   0.000000e+00      0s Out of memory *** Out of memory *** Could not solve problem (10001)

This is probably due to this 100% dense block. I’ll pass it on for investigation. Gurobi is under active development so this may be already working ok with later versions. To humble me it solves the original formulation from Konno/Yamazaki just fine!

The above timings were for Cplex/dual. As the original authors used MINOS, here are some timings with MINOS:

• Konno e.a.: its:17032, time:28.7
• Improved: its:11884, time:7.8

The timings with Cplex/dual and Minos/primal point in the same direction. Note that MINOS is faster with the improved model than Cplex on the Konno model. So proper modeling can sometimes help more than choosing a faster solver (of course both having a better formulation and a faster solver is even better). The importance of proper modeling is usually more important for MIP models, but here we see some real differences in performance for different formulations in an LP.