A branch-and-cut approach to portfolio selection with marginal risk control in a linear conic programming framework

Abstract

Marginal risk represents the risk contribution of an individual asset to the risk of the entire portfolio. In this paper, we investigate the portfolio selection problem with direct marginal risk control in a linear conic programming framework. The optimization model involved is a nonconvex quadratically constrained quadratic programming (QCQP) problem. We first transform the QCQP problem into a linear conic programming problem, and then approximate the problem by semidefinite programming (SDP) relaxation problems over some subrectangles. In order to improve the lower bounds obtained from the SDP relaxation problems, linear and quadratic polar cuts are introduced for designing a branch-and-cut algorithm, that may yield an ∈-optimal global solution (with respect to feasibility and optimality) in a finite number of iterations. By exploring the special structure of the SDP relaxation problems, an adaptive branch-and-cut rule is employed to speed up the computation. The proposed algorithm is tested and compared with a known method in the literature for portfolio selection problems with hundreds of assets and tens of marginal risk control constraints.

Keywords

Portfolio selection / linear conic programming / branch-and-cut

References

[1] Al-Khayyal F, Larsen C, Van Voorhis T. A relaxation method for nonconvex quadratically constrained quadratic programs. Journal of Global Optimization, 1995, 6: 215-230.

[2] Alizadeh F, Haeberly J-P, Overton M. Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, 1998, 8: 746-768.

[3] Anstreicher K. Semidefinite programming versus the reformulation -linearization technique for nonconvex quadratically constrained quadratic programming. Journal of Global Optimization, 2009, 43: 471-484.

[4] Audet C, Hansen P, Jaumard B, Savard G. A branch and cut algorithm for non-convex quadratically constrained quadratic programming. Mathematical Programming, 2000, 87: 131-152.

[5] Ben-Tal A, Nemirovskii A. Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, 2001, Philadelphia: Society for Industrial and Applied Mathematics.

[6] Bertsimas D, Lauprete G, Samarov A. Shortfall as a risk measure: properties, optimization and applications. Journal of Economics Dynamics and Control, 2004, 28: 1353-1381.

[7] Bremner D, Fukuda K, Marzetta A. Primal-dual methods for vertex and facet enumeration. Discrete and Computational Geometry, 1998, 20: 333-357.

[8] Burer S, Saxena A. Lee J, Leyer S. The MILP Road to MIQCP. Mixed Integer Nonlinear Programming, 2012 373-405.

[9] Deng Z, Fang S-C, Jin Q, Xing W. Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme. European Journal of Operational Research, 2013, 229: 21-28.

[10] Dowd K. Beyond Value at Risk: The New Science of Risk Managemet, 1999, New Jersey: John Wiley & Sons

[11] Fang S-C, Xing W. Linear Conic Optimization, 2013, Beijing: Science Press

[12] Grant M, Boyd S. CVX: Matlab Software for Disciplined Convex Programming, version 2.0 beta, 2013

[13] Grinold R, Kahn R. Active Portfolio Management: A Quantitative Approach for Producing Superior Returns and Controlling Risk, 1999, (2nd Edition) New York: McGraw-Hill

[14] Guo X, Deng Z, Fang S-C, Xing W. Quadratic optimization over one first-order cone. To appear in: Journal of Industrial and Management Optimization, 2013

[15] Huang F, Sun L, Wang Y. Mean-variance model based on filters of minimum spanning tree. Journal of Systems Science and Systems Engineering, 2011, 20: 495-506.

[16] Kim S, Kojima M. Second order cone programming relaxation of nonconvex quadratic optimization problems. Optimization Methods and Software, 2001, 15: 201-224.

[17] Konno H, Yamazaki H. Mean-absolute deviation portfolio optimization model and its applications to Tokyo stock market. Management Science, 1991, 37: 519-531.

[18] Markowitz H. Portfolio selection. Journal of Finance, 1952, 7: 77-91.

[19] Matsui T. NP-hardness of linear multiplicative programming and related problems. Journal of Global Optimization, 1996, 9: 113-119.

[20] Murty K, Kabadi S. Some NP-Complete problems in quadratic and non-linear programming. Mathematical Programming, 1987, 39: 117-129.

[21] Nazareth J. The homotopy principle and algorithms for linear programming. SIAM Journal on Optimization, 1991, 1: 316-332.

[22] Pardalos P, Sandstrom M, Zopounidis C. On the use of optimization models for portfolio selection: A review and some computational results. Computational Economics, 1997, 7: 227-244.

[23] Philippe J. Value at Risk: The New Benchmark for Managing Financial Risk, 2006, 3rd Edition New York: McGraw-Hill

[24] Raber U. A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. Journal of Global Optimization, 1998, 13: 417-432.

[25] Sahinidis N. BARON: a general purpose optimizaton software package. Journal of Global Optimization, 1996, 8: 201-205.

[26] Saxena A, Bonami P, Lee J. Convex relaxations of nonconvex mixed integer quadratically constrained programs: projected formulations. Mathematical Programming, 2011, 130: 359-413.

[27] Sherali H, Adams W. A Reformulated-Linerization Technique for Solving Discrete and Continuous Nonconvex Problems, 1999, Dordrecht: Kluwer Academic Publishers.

[28] Sherali H, Tuncbilek C. A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization, 1995, 7: 1-31.

[29] Shor N. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 1987, 25: 1-11.

[30] Tian Y, Fang S-C, Deng Z, Xing W. Computable representation of the cone of nonnegative quadratic forms over a general second-order-cone and its application to completely positive programming. Journal of Industrial and Management Optimization, 2013, 9: 703-721.

[31] Yang G, Huang S, Chen W. An utilities based approach for multi-period dynamic portfolio selection. Journal of Systems Science and Systems Engineering, 2007, 16: 277-286.

[32] Zhu S, Li D, Sun X. Portfolio selection with marginal risk control. The Journal of Computational Finance, 2010, 14: 3-28.