Document Open Access Logo

Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises

Authors Ludovic Calès, Apostolos Chalkis, Ioannis Z. Emiris, Vissarion Fisikopoulos

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.19.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Ludovic Calès
Apostolos Chalkis
Ioannis Z. Emiris
Vissarion Fisikopoulos

Cite As Get BibTex

Ludovic Calès, Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.19

Abstract

We examine volume computation of general-dimensional polytopes and more general convex bodies, defined as the intersection of a simplex by a family of parallel hyperplanes, and another family of parallel hyperplanes or a family of concentric ellipsoids. Such convex bodies appear in modeling and predicting financial crises. The impact of crises on the economy (labor, income, etc.) makes its detection of prime interest for the public in general and for policy makers in particular. Certain features of dependencies in the markets clearly identify times of turmoil. We describe the relationship between asset characteristics by means of a copula; each characteristic is either a linear or quadratic form of the portfolio components, hence the copula can be constructed by computing volumes of convex bodies.
We design and implement practical algorithms in the exact and approximate setting, we experimentally juxtapose them and study the tradeoff of exactness and accuracy for speed. We analyze the following methods in order of increasing generality: rejection sampling relying on uniformly sampling the simplex, which is the fastest approach, but inaccurate for small volumes; exact formulae based on the computation of integrals of probability distribution functions, which are the method of choice for intersections with a single hyperplane; an optimized Lawrence sign decomposition method, since the polytopes at hand are shown to be simple with additional structure; Markov chain Monte Carlo algorithms using random walks based on the hit-and-run paradigm generalized to nonlinear convex bodies and relying on new methods for computing a ball enclosed in the given body, such as a second-order cone program; the latter is experimentally extended to non-convex bodies with very encouraging results. Our C++ software, based on CGAL and Eigen and available on github, is shown to be very effective in up to 100 dimensions. Our results offer novel, effective means of computing portfolio dependencies and an indicator of financial crises, which is shown to correctly identify past crises.

Subject Classification

Keywords
  • Polytope volume
  • convex body
  • simplex
  • sampling
  • financial portfolio

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Y. Abbasi-Yadkori, P.L. Bartlett, V. Gabillon, and A. Malek. Hit-and-run for sampling and planning in non-convex spaces. In Proc. 20th Intern. Conf. Artificial Intelligence &Stat. (AISTATS), pages 888-895, 2017. URL: http://proceedings.mlr.press/v54/abbasi-yadkori17a.html.
  2. M. Maswood Ali. Content of the frustum oa a simplex. Pacific J. Math., 48(2):313-322, 1973. Google Scholar
  3. A. Banerjee and C-H. Hung. Informed momentum trading versus uninformed "naive" investors strategies. J. Banking &Finance, 35(11):3077-3089, 2011. Google Scholar
  4. M. Billio, L. Calès, and D. Guéguan. A cross-sectional score for the relative performance of an allocation. Intern. Review Appl. Financial Issues &Economics, 3(4):700-710, 2011. Google Scholar
  5. M. Billio, M. Getmansky, and L. Pelizzon. Dynamic risk exposures in hedge funds. Comput. Stat. &Data Analysis, 56(11):3517-3532, 2012. URL: http://dx.doi.org/10.1016/j.csda.2010.08.015.
  6. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, UK, 2004. Google Scholar
  7. B. Büeler, A. Enge, and K. Fukuda. Exact volume computation for polytopes: A practical study. In G. Kalai and G.M. Ziegler, editors, Polytopes: Combinatorics and Computation, volume 29 of Math. &Statistics, pages 131-154. Birkhäuser, Basel, 2000. Google Scholar
  8. L. Cal\a`es, A. Chalkis, I.Z. Emiris, and V. Fisikopoulos. Practical volume computation of structured convex bodies, and an application to modeling portfolio dependencies and financial crises. CoRR, arXiv:1803.05861, March 2018. URL: https://arxiv.org/abs/1803.05861.
  9. K. Chandrasekaran, D. Dadush, and S. Vempala. Thin partitions: Isoperimetric inequalities and sampling algorithms for some nonconvex families. CoRR, abs/0904.0583, 2009. URL: http://arxiv.org/abs/0904.0583.
  10. B. Cousins and S. Vempala. A cubic algorithm for computing Gaussian volume. In Proc. Symp. on Discrete Algorithms, pages 1215-1228. SIAM/ACM, 2014. Google Scholar
  11. K. Daniel and T.J. Moskowitz. Momentum crashes. J. Financial Economics, 122(2):221-247, 2016. Google Scholar
  12. H.A. David. Order statistics. Wiley, New York, 2 edition, 1981. Google Scholar
  13. L. Devroye. Non-uniform Random Variate Generation. Springer, Berlin, 1986. Google Scholar
  14. A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems. In Proc. European Control Conference (ECC), pages 3071-3076, 2013. Google Scholar
  15. M. Lo Duca, A. Koban, M. Basten, E. Bengtsson, B. Klaus, P. Kusmierczyk, J.H. Lang, C. Detken, and T. Peltonen. A new database for financial crises in european countries. Technical Report 13, European Central Bank and European Systemic Risk Board, Frankfurt am Main, Germany, 2017. Google Scholar
  16. M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, 1991. URL: http://dx.doi.org/10.1145/102782.102783.
  17. M.E. Dyer and A.M. Frieze. On the complexity of computing the volume of a polyhedron. SIAM J. Comput., 17(5):967-974, 1988. URL: http://dx.doi.org/10.1137/0217060.
  18. G. Elekes. A geometric inequality and the complexity of computing volume. Discrete &Computational Geometry, 1:289-292, 1986. Google Scholar
  19. I.Z. Emiris and V. Fisikopoulos. Practical polytope volume approximation. ACM Trans. Math. Soft., 2018. To appear. Prelim. version: Proc. Sympos. on Comput. Geometry, 2014. Google Scholar
  20. E. Erdougan and G. Iyengar. An active set method for single-cone second-order cone programs. SIAM J. Optimization, 17(2):459-484, 2006. URL: http://dx.doi.org/10.1137/040612592.
  21. J. Griffin, X. Ji, and J. Martin. Momentum investing and business cycle risk: Evidence from pole to pole. J. Finance, 58(6):2515-2547, 2003. Google Scholar
  22. C. Grimme. Picking a uniformly random point from an arbitrary simplex. Technical report, Information Systems and Statistics, Munster U., Germany, 2015. Google Scholar
  23. N. Jegadeesh and S. Titman. Returns to buying winners and selling losers: Implications for stock market efficiency. J. Finance, 48:65-91, 1993. Google Scholar
  24. J. Lawrence. Polytope volume computation. Math. of Computation, 57(195):259-271, 1991. Google Scholar
  25. O. Ledoit and M. Wolf. Honey, I shrunk the sample covariance matrix. J. Portfolio Management, 30(4):110-119, 2004. URL: http://dx.doi.org/10.3905/jpm.2004.110.
  26. Y.T. Lee and S.S. Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. CoRR, abs/1710.06261, 2017. URL: http://arxiv.org/abs/1710.06261.
  27. Y.T. Lee and S.S. Vempala. Geodesic walks in polytopes. In Proc. ACM Symp. on Theory of Computing, pages 927-940. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055416.
  28. L. Lovász. Hit-and-run mixes fast. Math. Programming, 86:443-461, 1999. URL: http://dx.doi.org/10.1007/s101070050099.
  29. H. Markowitz. Portfolio selection. J. Finance, 7(1):77-91, 1952. URL: http://dx.doi.org/10.1111/j.1540-6261.1952.tb01525.x.
  30. A.M. Mathai. On linear combinations of independent exponential variables. Communications in Statistics: Theory &Methods, 2007. Google Scholar
  31. A.A. Mohsenipour and S.B. Provost. On approximating the distribution of quadratic forms in gamma random variables and exponential order statistics. J. Statistical Theory &Appl., 12(2):173-184, 2013. Google Scholar
  32. I. Pouchkarev. Performance evaluation of constrained portfolios. PhD thesis, Erasmus Research Institute of Management, The Netherlands, 2005. Google Scholar
  33. I. Pouchkarev, J. Spronk, and J Trinidad. Dynamics of the spanish stock market through a broadband view of the IBEX 35 index. Estudios Econom. Aplicada, 22(1):7-21, 2004. Google Scholar
  34. R.Y. Rubinstein and D.P. Kroese. Simulation and the Monte Carlo method. Wiley Interscience, New York, 2007. Google Scholar
  35. R.Y. Rubinstein and B. Melamed. Modern simulation and modeling. Wiley, New York, 1998. Google Scholar
  36. P. Scheurle and K. Spremann. Size, book-to-market, and momentum during the business cycle. Review of Managerial Science, 4(3):201–215, 2010. Google Scholar
  37. N.A. Smith and R.W. Tromble. Sampling uniformly from the unit simplex. Technical report, Center for Language and Speech Processing, Johns Hopkins U., 2004. Google Scholar
  38. G. Varsi. The multidimensional content of the frustum of the simplex. Pacific J. Math., 46:303-314, 1973. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact