Advances in Computing
p-ISSN: 2163-2944 e-ISSN: 2163-2979
2012; 2(1): 6-11
doi:10.5923/j.ac.20120201.02
Majid Vafaei Jahan
Department of Software Engineering, Mashhad Branch - Islamic Azad University, Mashhad, Iran
Correspondence to: Majid Vafaei Jahan, Department of Software Engineering, Mashhad Branch - Islamic Azad University, Mashhad, Iran.
Email: |
Copyright © 2012 Scientific & Academic Publishing. All Rights Reserved.
One of the techniques to resolve the problem more quickly is using the multi-scale spatial dimension reduction. In classical theory, system analysis based on multi-scaling is extremely difficult, because it is dependent on the behavior of every component analysis and understanding the relationship between them. The new achievements in this field show that most systems cannot be scaled at any condition. Regardless to this property of the system, Kadanoff's theory shows a necessary condition of scaling. Based on this theory, the best condition of scaling occurs in the phase transition condition at the critical temperatures of material. In this condition, upper-scale system behavior is approximately similar to the main-scale system behavior. This article is benefited from this theory and is presented the new algorithm that is named Simulated Annealing Multi-Scaling (SAMS). This algorithm is based on the spin glass paradigm to solve the NP-complete portfolio selection problem as a case study. Due to many relationships between stocks, the problem scaling, is equivalent to loss of part of the data, hence the possibility to achieve the ground state decline so much. By using this theory, it is shown that the best time to change the scale of the problem with minimum error occurs during its phase transition. Tests on five major stock exchange data show, this algorithm, in addition to confirming Kadanoff's theory in application, has more convergence speed than traditional methods such as SA and also, provides the possibility of using parallel processing in optimization problems.
Keywords: Ising Spin Glass Model, Portfolio Selection Problem, Multi-Scaling, Kadanoff's Scaling Picture Theory, Parallel Processing
Cite this paper: Majid Vafaei Jahan, Multi Scale Spin Glass Based Portfolio Selection, Advances in Computing, Vol. 2 No. 1, 2012, pp. 6-11. doi: 10.5923/j.ac.20120201.02.
Figure 1. Glass with scale factor, in this glass, there are twenty spin |
Figure 2. Glass with scale factor, a glass with twenty spin renormalized to a glass with 2 spin that each one has ten spin |
(1) |
(2) |
(3) |
(4) |
Figure 3. Algorithm SAMS, based on Kadanoff's theory. Row 5, can be executed after renormalization for finding glass ground state; it is not part of SAMS algorithm |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
(10) |
(11) |
Figure 4. Probability density functions for covariances between assets in 5 major stock markets from 1992 to 1997 from data in [17] |
Figure 5. Phase Transition Temperature for five stock markets [17], this temperature is the same for all stocks |
[1] | Y. Bar-Yam, "About Enginerring Complex Systems: Multiscale Analysis and Evolutionary Engineering," Spiringer Verlag Berlin Heidelberg, pp: 16-31, (2005). |
[2] | Y. Bar-Yam, Yaneer, "Dynamics of Complex Systems," Addison Wesley Longman, Inc., pp: 146-180, (1997). |
[3] | D. Braha, Y. Bar-Yam "Topology of large-scale engineering problem-solving networks," Physical Review E, Vol. 69, 016113 (2004). |
[4] | D.P. Landau, K. Binder, "A Guide to Monte Carlo Simulations in Statistical Physics," Second Edition, Cambridge University Press, pp: 1-45 (2000). |
[5] | A. K. Hartmann, H. Rieger, "Optimization Algorithms in Physics," Wiley-VCH Verlag Co, pp: 46-121, (2002). |
[6] | J.Z. Justin, "Phase Transitions and Renormalization Group," Oxford University Press, pp: 79-92, (2007). |
[7] | J,Hasty, K. Wiesenfeld, "Renormalization of self-organized critical models," Annals of the New York Academy of Sciences, Issue Long-range correlations in Astrophysical Systems,Vol. 848, pp:9–17, (1998). |
[8] | M.E. Fisher, "Renormalization group theory: its basis and formulation in statistical physics," Reviews of Modern Physics, Vol. 70, No. 2, (1988). |
[9] | J. Houdayer and O.C. Martin, "Hierarchical approach for computing spin glass ground states," Physical Review E, Vol. 64, 056704, (2001). |
[10] | M.Vafaei Jahan, M.R. Akabazadeh-T, "From Local Search to Global Conclusions: Migrating Spin Glass-based Distributed Portfolio Selection," IEEE transaction on Evolutionary Computation, No. 14, Issue 4, pp:591-601, (2010). |
[11] | N. Kawashima, "Optimizataion Algorithms based on Renormalization Group," Progress of Theoretical Physics Supplement, Vol. 138; pp. 448-453(2000). |
[12] | E.Bolthausen, A.Bovier, "Spin Glasses," Springer-Verlag Berlin Heidelberg, pp: 17-49, (2007). |
[13] | H. Markowitz, "Portfolio Selection," Journal of Finance, No 7:77-91, (1952). |
[14] | Ran El-Yaniv, "Competitive Solutions for Online Financial Problems," ACM computing Surveys, Vol. 30, No. 1, March (1998). |
[15] | L. Ingber, "Simulated Annealing: Practice versus Theory," Mathematical Computer Modeling, Vol. 18, No. 11, Dec (1993). |
[16] | Y. Crama, M. Schyns, "Simulated Annealing for Complex Portfolio Selection Problems," European Journal of Operational Research 150, pp: 546-571, (2003). |
[17] | Portfolio selection benchmark data at "http://people.brunel.ac.uk/~mastjjb/jeb/orlib/portinfo.html" |
[18] | A. K. Hartmann, M. Weigt, "Phase Transitions in Combinatorial Optimization Problems, Basics, Algorithms and Statistical Mechanics," Wiley-VCH Verlag Co, pp: 1-91 (2005). |
[19] | D.Coppersmith, D.Gamarnik, M.Hajiaghayi, G.B. Sorkin, "Random max sat, Random max cut, and Their Phase Transitions," Journal of Random Structures and Algorithms, Vol. 24, Issue 4,pp:502-545, (2003). |