1. Introduction

Most systems around us have superiority complex nature[1]. For adequate understanding of these systems, only recognition of its principal components is not enough. Because of identifying the relationship between them is more difficult than recognizing its individual components[1] and specially, it is more complicated for systems with emergent behavior[2,3]. In this case, heuristic algorithms such as genetic algorithm or simulation techniques such as Monte- Carlo methods usually help to find the optimal system's state. Because of the inherent low speed specification (with regards to accuracy) of these algorithms, scientists are encouraged to representing new methods to reach both accuracy and speed[4,5]. One of these techniques considered in this direction uses a physical property of materials such as multi-scaling property[6]. Since, scaling cannot be done at any condition and depend on recognizing individual system's components[7,8]; Kadafnoff's theory can help us to find the best time and conditions of scaling. Based on Kadanoff's theory, the best scaling condition of system is in phase transition at the critical temperatures[8]. In other words, the best time to build up the upper-scale of a system (to reduce the dimensionality of system's space) is during its phase transition. Despite, the number of variables in upper scale is less and relationships between them are weaker, and require less processing time[9] to find optimal state of the problem in upper scale; both systems (main scale and upper scale) have the same functional behavior, and the energy equations are used without significantly changes. Hence it is enough to provide the phase transition condition for the problem and rescale the problem into upper-scale to find the optimal state faster.

In this paper, a new optimization algorithm that is named SAMS based on spin glass scaling and Kadanoff's theory is presented and as a case study, the portfolio selection problem is solved. So first, the portfolio selection problem is mapped into long range spin glass as mentioned in paper[10], and then the glass is placed in phase transition situation. In this condition, the scale of the glass is changed into a upper scale glass and some smaller main scale glass. For each generated glasses, ground state is found with one of the heuristic methods such as simulated annealing (SA) and finally renormalized again to show the found ground state of the problem.

The experiments show, the speed of finding ground state has increased about fifty percent regardless having computation overhead.

So first, in Section 2, concepts of renormalization and multi-scaling are described, in Section 3, the proposed SAMS algorithm based on the kadanoff's theory and multi- scaling is explained. In Section 4, the portfolio selection problem and Markowitz model are defined and in Section 5, the portfolio selection solution by using long range spin glass, which is described in paper[10], is expressed again. Finally, in Section 6, experimental results and conclusions are presented.

2. Renormalization Group and Multi-Scaling

Renormalization group transformation is a process that all algorithms and formulas of a system in scale become represented into the algorithms and formulas in scale [8]. shows the scale factor and its numerical value is smaller than or equal to 1 and is greater than zero. Value 1, represents the main glass and, smaller than 1, indicates the glass in upper-scale. In renormalization group theory, first, the glass is clustered. It is assumed that each cluster of spins is a new spin in upper-scale glass. In new glass, with less spins, it is assumed the energy equations remain constant during the scaling and it can be used for upper-scale without any changes. It should be mentioned that there are various clustering algorithms and can be studied as sample in[9,11]. This article, dose not talks about the glass clustering; the desired clustering is more like making mesh. In other words, kind of division and regional position on the glass is performed. After clustering, for each smaller glass and upper- scale glass, ground state is calculated using heuristic algorithm. This operation can be performed in several stages as much as scaling allows.

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

Energy of each glass is calculated as follows[12]:

(1)

is the energy of the glass and is total number of spins in the glass. The sum runs over all pairs of nearest neighbors (in this paper, glass is long range spin glass, and each spin is nearest neighbor of all other spins), denotes the strength of the bond connecting spins and. describes a ferromagnetic interaction, while describes an anti-ferromagnetic interaction. The quantity is the external field acting on spin and describes the energy due to the spin's orientation. Also, the factor corrects for double counting of the interaction between every two neighboring spins. Here the task is to find a spin configuration that minimizes the energy of the spin glass, given

For calculating the energy of upper-scale glass, the strength of the bond between spins and external field energy must first be calculated. For this purpose, formula (2) is used for calculating the energy between spins and formula (3) is used for calculating the external field energy per spin[9].

(2)

(3)

is the total spin of each cluster and is the total spin in glass in upper-scale. So, the total number of spins of main scale glass is equal to.

Considering the above definitions and regarding to the renormalization theory the energy per glass in upper-scale is calculated as follows:

(4)

3. SAMS Algorithm

In Fig. (1), a summery of SAMS algorithm is shown. This algorithm is a combination of SA and multi-scale techniques regards to the renormalization process and used for solving optimization problems. SA is used for finding optimal state of each glass and scaling is used for creating glasses with different scale.

As shown in Fig. (3), first, glass is placed in phase transition condition and renormalized. In this condition, an upper-scale glass along with several smaller glasses is produced. For all produced glass, SA algorithm is applied. The results are glasses that are locally optimal. Now, the result of upper-scale glass is applied on main-scale glass, (by multiplying the amount of each spin in upper-scale glass), to demonstrate the glass's ground state.

Experiments show, the optimal glass's state, in regards to SAMS algorithm, is closer to ground state; but it is not ground state yet. The reason is clear: the renormalization formulas are approximate and accuracy is reduced from main-scale to upper-scale. Even, these conditions are worse for more scaling levels that cause glass can not specify the ground state clearly.

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

The above algorithm has been tested for portfolio selection problem based on spin glass paradigm. However, the state of upper-scale spins represents the better assets but this may not be optimal portfolio; also, it is largely influenced on finding better assets and causes the performance of the optimization algorithm increase.

4. Portfolio Selection Problem

Let us consider the Markowitz mean-variance model[13, 14] for the portfolio selection problem as stated below,

(2)

(3)

(4)

(5)

where is the number of different assets, is the mean return of asset , and is the covariance between returns of assets and. The decision variable represents the fraction of capital to be invested in asset . Eqs. (2)-(3) are two cost functions that should be solved with constraints (4) and (5). is the mean return of asset in intervals of time, i.e. , where is the asset value at the beginning and is the asset value at the end of each interval.

In this paper we change the multiobjective problem into a multimodal problem with single objective function as follows,

(6)

(7)

(8)

In Eq. (6), let be the risk aversion parameter. If then Eq. (6) represents maximum portfolio mean return (without considering the variance) and the optimal solution will be formed only by the asset with the greatest mean return. The case with represents minimizing the total variance associated with the portfolio (regardless of the mean returns) and the optimal solution will typically consist of several assets. Any value of inside the interval (0,1) represents a tradeoff between mean return and variance, generating a solution between the two extremes, and 1.

5. Solving Portfolio Selection Problem Using Spin Glass Paradigm

To present our method, we initially map the portfolio selection problem into a spin glass computational model and then find its ground state by looking at the objective function, Eq. (6), of the portfolio selection problem and comparing it with the spins energy function Eq. (1) of the spin glass model. We obtain the values for the interaction strength as follows [10]:

(9)

(10)

The decision variable represents the proportion of capital to be invested in asset i; and in spin glass, we can defineto be the state of spin i. So the problem of portfolio selection can be solved by minimizing the mapped function as in Eq. (6).

For finding the minimum of optimization function Eq. (6) with regard to constraints (7)-(8), we first randomly place the possible assets into a long range glass (Full connection glass). All of the spins in this structure are initialized to random values. Therefore, we can use some heuristic algorithm or methods such as SA to select the best assets by finding the ground state or minimum energy of the glass.

According to the SA algorithm, a spin is chosen randomly at every flip and the value of the selected spin is increased by . Accordingly, the value of neighboring spins changes to meet the constraints (7) and (8).

For the heating and cooling schedule, procedures related to SA are used, as in[15,16]. To do so, the temperature of the network is considered to be initially set to (at high temperatures all states can occur). Each time the changes are applied the temperature gradually decreases until it reaches near zero. Temperature variations can be governed by the following formula,

(11)

where n represents the number of epochs. The stop condition of algorithm is the iteration of single result in number of defined steps continually with regard to defined precision. For example all experiments' results have been measured by ten same results with a precision of .

6. Experimental Results

Experiments on the benchmark data were originally performed in[17]. These benchmark data are presented in text file format as follows:

Number of assets (N); and for each asset i (i=1,...,N): mean return as well as standard deviation of return; for all possible pairs of assets: i, j, correlation between asset i and asset j. The above data were taken from five major stock exchange markets, during the time period extending from March 1992 to September 1997. These five stock exchange markets include Hang Seng in Hong Kong (31 assets), Deutscher Aktien Index (DAX100) in Germany (85 assets), Financial Times London Stock Exchange (FTSE100) in Britain (89 assets), Standard & Poor's (S&P100) in USA (98 assets), and Nikkei in Japan (225 assets). Probability density function (pdf) of covariance P(J) of each stock market for the given data has been shown in Fig. (4).

As can be observed, the P(J) of the five given stock markets have small mean and variance.

All of the experiments were performed using Borland Delphi 6.0 running on a Pentium 2.4 GHz PC, under Windows XP operating system.

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

Table 1. Comparison between SA and SAMS, the time to find ground state with random initialization is more than time to find ground state after initializing with SAMS algorithm Productivity(%) Total time to find ground state with random initialization and using SAMS algorithm (ms) Time to find ground state after initializing with SAMS results (ms) Time to find ground state with random initialization (ms) Number of Assets 81 9610 2033 11221 32 assets Hang Seng 50 80433 38721 77669 90 Assets DAX100 52 86300 39780 84536 90 Assets FTSE100 74 86132 21827 85579 100 Assets S&P100 84 512034 216234 1402401 240 Assets Nikkei

6.1. Phase Transition for Portfolio Selection Problem

A phase transition typically refers to a transformation of a thermodynamic system from one state to another. This transformation is typically marked by a sudden change in some physical property that is the result of some small change in what is called an order parameter (e.g., temperature)[18,19]. Phase transition temperature in spin glasses is a sudden change that occurs in a state of glass. In other words, at this temperature, the probability of finding the ground state of the glass decreases significantly and glasses' states are unlikely to be a ground state. Fig. (8) illustrates phase transition temperature of spin glasses applied to the portfolio selection problems. As shown in this figure, the probability of reaching ground state () is equal to 1 in low temperatures, where E is the amount of glass energy and is the actual minimum of the energy function. As temperature rises, glass energy also changes and the probability of reaching ground state is expected to gradually decrease. However, this drop is delayed until phase transition, where a sudden drop occurs. After phase transition temperature (critical temperature), the probability of reaching ground state decreases significantly. As shown in Fig. (8), this temperature is approximately 5.8* 10^-5 for all of the five mentioned stocks. At this temperature, system is not in ground state and selecting any state as answer of the problem is unlikely to be a ground state.

After the spin glass was placed in phase transition condition, renormalization process is performed. In this case, the glass is divided into several smaller glasses. Also according to formulas (2) and (3), a upper-glass scale is produced. Now, SA algorithm applies for upper-scale glass and all main-scale glasses. The results show that the time to reach to optimal state reduced effectively. So that, if the starting temperature without using renormalization process is, then temperature, for the case with using renormalization process is approximately.

This means, the SA algorithm needs lower temperature for initializing and is caused increasing convergence speed of the algorithm.

Table (1), shows the time of convergence speed to finding spin glass ground state for two SA and SAMS algorithm. As shown, productivity (the ratio of the time of finding ground state that initialize with applying SAMS algorithm to the time of finding ground state with random initializing) is significant. For example, in Hang Seng stock market, productivity is 0.81 percent.

In this experiment, the scale factor is 0.5 and glass is divided into two separated glasses.

This experiment shows that dividing glasses into two separated glass cause higher convergence speed in finding its ground state but it may not find the ground state of the main glass respectively. However, the upper-scale glass ground state help to provide better initialization condition.

Advantages in using this algorithm can be expressed as follows: 1) Initializing glass with one thousandth of original temperature means higher convergence speed and savings in time and energy. 2) Many of inappropriate states that were searched by SA, was not explored by SAMS; because of exploiting in the range of optimal state. 3) Provides possibility of using parallel processing for each glass separately. 4) If the bond energy between spins is weak then the SAMS algorithm gives better response. This is because, loosely interaction between spins, as expressed in [7], increase the local behavior of each spin and causes the local search methods, have greater accuracy to find the optimal states.

7. Summary and Conclusions

In this article, a new optimization algorithm (SAMS) for solving problems based on spin glasses is presented. This algorithm, by using multi-scaling property of material, tries to break problem into smaller problems. Since scaling can not be done at any condition, Kadanoff's theory has been used to show the best conditions of scaling. Based on Kadanoff's theory, the best condition of scaling is in phase transition condition at critical temperature of material. So, this algorithm uses these two properties and solves the portfolio selection problem as case study. The experiments show, this algorithm, in addition to confirm Kadanoff's theory in application, has more convergence speed than traditional methods such as SA and also, provides possibility of using parallel processing in optimization problems.