The nearest correlation matrix problem: Solution by differential evolution method of global optimization

Mishra, SK (2007): The nearest correlation matrix problem: Solution by differential evolution method of global optimization.

Abstract

Correlation matrices have many applications, particularly in marketing and financial economics - such as in risk management, option pricing and to forecast demand for a group of products in order to realize savings by properly managing inventories, etc.

Various methods have been proposed by different authors to solve the nearest correlation matrix problem by majorization, hypersphere decomposition, semi-definite programming, or geometric programming, etc. In this paper we propose to obtain the nearest valid correlation matrix by the differential evaluation method of global optimization.

We may draw some conclusions from the exercise in this paper. First, the ‘nearest correlation matrix problem may be solved satisfactorily by the evolutionary algorithm like the differential evolution method/Particle Swarm Optimizer. Other methods such as the Particle Swarm method also may be used. Secondly, these methods are easily amenable to choice of the norm to minimize. Absolute, Frobenius or Chebyshev norm may easily be used. Thirdly, the ‘complete the correlation matrix problem’ can be solved (in a limited sense) by these methods. Fourthly, one may easily opt for weighted norm or un-weighted norm minimization. Fifthly, minimization of absolute norm to obtain nearest correlation matrices appears to give better results.

In solving the nearest correlation matrix problem the resulting valid correlation matrices are often near-singular and thus they are on the borderline of non-semi-positive-definiteness. One finds difficulty in rounding off their elements even at 6th or 7th places after decimal, without running the risk of making the rounded off matrix non-positive definite. Such matrices are, therefore, difficult to handle. It is possible to obtain more robust positive definite valid correlation matrices by constraining the determinant (the product of eigenvalues) of the resulting correlation matrix to take on a value significantly larger than zero. But this can be done only at the cost of a compromise on the criterion of ‘nearness.’ The method proposed by us does it very well.

• Item Type: MPRA Paper
• Institution: North-Eastern Hill University, Shillong (India)
• Language: English
• Keywords: Correlation matrix; product moment; nearest; complete; positive semi-definite; majorization; hypersphere decomposition; semi-definite programming; geometric programming; Particle Swarm; Differential Evolution; Particle Swarm Optimization; Global Optimization; risk management; option pricing; financial economics; marketing; computer program; Fortran; norm; absolute; maximum; Frobenius; Chebyshev; Euclidean
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling; G - Financial Economics > G0 - General > G00 - General; C - Mathematical and Quantitative Methods > C8 - Data Collection and Data Estimation Methodology ; Computer Programs > C88 - Other Computer Software; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; G - Financial Economics > G1 - General Financial Markets > G19 - Other

References

• Al-Subaihi, AA (2004). “Simulating Correlated Multivariate Pseudorandom Numbers”, At www.jstatsoft.org/counter.php?id=85&url=v09/i04/paper.pdf&ct=1

• Anjos, MF, Higham, NJ, Takouda, PL and Wolkowicz, H (2003) “A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem”, Preliminary Research Report, Dept. of Combinatorics & Optimization, Waterloo, Ontario.

• Barett, WW, Johnson, CR and Lundquist, M (1989). “Determinantal Formulae for Matrix Completions Associated with Chordal Graphs”. Linear Algebra and its Applications, 121:265–289.

• Barrett, WW, Johnson, CR and Loewy, R (1998). “Critical Graphs for the Positive Definite Completion Problem”. SIAM Journal of Matrix Analysis and Applications, 20:117–130.

• Budden, M, Hadavas, P, Hoffman, L and Pretz, C (2007) “Generating Valid 4 x 4 Correlation Matrices”, Applied Mathematics E-Notes, 7:53-59.

• Chesney, M and Scott, L (1989). “Pricing European Currency Options: A Comparison of the Modified Black-Scholes Model and a Random Variance Model”. Journal of Financial and Quantitative Analysis, 24:267–284.

• Glass, G and Collins, J (1970) “Geometric Proof of the Restriction on the Possible Values of rxy when rxz and ryx are Fixed”, Educational and Psychological Measurement, 30:37-39.

• Grone, R, Johnson, CR, Sá, EM and Wolkowicz, H (1984).” Positive Definite Completions of Partial Hermitian Matrices”. Linear Algebra and its Applications, 58:109–124.

• Grubisic, I and Pietersz, R (2004) “Efficient Rank Reduction of Correlation Matrices”, Working Paper Series, SSRN, http://ssrn.com/abstract=518563

• Helton, JW, Pierce, S and Rodman, L (1989). “The Ranks of Extremal Positive Semidefinite Matrices with given Sparsity Pattern”. SIAM Journal on Matrix Analysis and its Applications, 10:407–423.

• Heston, SL (1993). “A Closed-form Solution for Options with stochastic Volatility with Applications to Bond and Currency Options”. The Review of Financial Studies, 6:327–343.

• Higham, NJ (2002). “Computing the Nearest Correlation Matrix – A Problem from Finance”, IMA Journal of Numerical Analysis, 22, pp. 329-343.

• Johnson, C (1990). “Matrix Completion Problems: A Survey”. Matrix Theory and Applications, 40:171–198.

• Kahl, C and Günther, M (2005). “Complete the Correlation Matrix”. http://www.math.uni-wuppertal.de/~kahl/publications/CompleteTheCorrelationMatrix.pdf

• Laurent, M (2001). “Matrix Completion Problems”. The Encyclopedia of Optimization, 3:221–229. • Marsaglia, G. and Olkin, I (1984). “Generating Correlation Matrices”. SIAM Journal on Scientific and Statistical Computing, 5(2): 470-475.

• Mishra, SK (2004) “Optimal Solution of the Nearest Correlation Matrix Problem by Minimization of the Maximum Norm". http://ssrn.com/abstract=573241

• Mishra, SK (2006) “Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions”. http://ssrn.com/abstract=933827

• Mishra, SK (2007) “Completing Correlation Matrices of Arbitrary Order by Differential Evolution Method of Global Optimization: A Fortran Program”. Available at SSRN http://ssrn.com/abstract=988373

• Olkin, I (1981) “Range Restrictions for Product-Moment Correlation Matrices”, Psychometrika, 46:469-472.

• Pietersz, R and Groenen, PJF (2004) “Rank Reduction of Correlation Matrices by Majorization”, Econometric Institute Report EI 2004-11, Erasmus Univ. Rotterdam.

• Rebonato, R and Jäckel, P (1999) “The Most General Methodology to Create a Valid Correlation Matrix for Risk Management and Option Pricing Purposes”, Quantitative Research Centre, NatWest Group, http://www.rebonato.com/CorrelationMatrix.pdf

• Schöbel, R and Zhu, J (1999). “Stochastic Volatility With an Ornstein Uhlenbeck Process: An Extension”. European Finance Review, 3:23–46, ssrn.com/abstract=100831.

• Stanley, J and Wang, M (1969) “Restrictions on the Possible Values of r12, given r13 and r23” , Educational and Psychological Measurement, 29, pp.579-581.

• Storn, R and Price, K (1995) "Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces": Technical Report, International Computer Science Institute, Berkley.

• Tyagi, R and Das, C (1999) “Grouping Customers for Better Allocation of Resources to Serve Correlated Demands”, Computers and Operations Research, 26:1041-1058.

• Xu, K and Evers, P (2003) “Managing Single Echelon Inventories through Demand Aggregation and the Feasibility of a Correlation Matrix”, Computers and Operations Research, 30:297-308.