# American Institute of Mathematical Sciences

2012, 2(1): 167-185. doi: 10.3934/naco.2012.2.167

## A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection

 1 Laboratory of Theoretical and Applied Computer Science (LITA), Paul Verlaine - Metz University, Ile du Saulcy, 57045, Metz, France 2 Laboratory of Theorical and Applied computer Science LITA, UFR MIM, University Paul Verlaine of Metz, Ile du Saulcy-Metz 57045, France 3 Laboratory of Mathematics. National Institute for Applied Sciences, Rouen BP 08, Place Emile Blondel F 76131, Mont Saint Aignan Cedex, France

Received  March 2011 Revised  October 2011 Published  March 2012

In this paper, we consider a class of bilevel programming problems where the upper objective function is convex quadratic while the lower objective function and the constraints are linear. The problem is first rewritten as minimizing a convex quadratic function subject to linear constraints and one concave constraint. Then, we use an exact penalty technique to reformulate the problem as a DC program. Afterward, DCA, an efficient algorithm in nonconvex programming, is developed to solve the resulting problem.
For globally solving the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). DCA is applied to compute upper bounds, while lower bounds are calculated via a DC relaxation of the DC constraint. The proposed algorithms, DCA and BB-DCA, are compared with the Branch-and-Bound algorithm without DCA (BB) on random data. The numerical results show that the proposed algorithms are efficient.
Finally, we consider an application of portfolio selection problems with the historical data related to the prices in the market of France, Luxembourg, United States and England during the period 2000-2007. The experimental results confirm the efficiency and the rapidity of DCA.
Citation: Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167
##### References:
 [1] G. J. Alexander and A. M. Baptista, A Portfolio selection with a drawdown constraint, Journal of Banking & Finance, 30 (2006), 3171-3189. doi: 10.1016/j.jbankfin.2005.12.006. [2] J. F. Bard, Some properties of the bilevel programming problem, Journal of Optimization Theory and Applications, 68 (1991), 371-378. doi: 10.1007/BF00941574. [3] B. Colson, P. Marcotte and G. Savard, Bilevel programming: a survey, A Quarterly Journal of Operations Research, 3 (2005), 87-107. [4] , DC Programming and DCA:, \url{http://lita.sciences.univ-metz.fr/~lethi/DCA.html}., (). [5] T. Pham Dinh and H. A. Le Thi, Convex analysis approach to DC programming: Theory, algorithms and applications, Acta Mathematica Vietnamica, 22 (1997), 289-355. [6] T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem, SIAM J. Optimization, 8 (1998), 476-505. doi: 10.1137/S1052623494274313. [7] T. Pham Dinh, N. Nguyen Canh and H. A. Le Thi, An efficient combination of DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs, Journal of Global Optimization, 48 (2010), 595-632. doi: 10.1007/s10898-009-9507-y. [8] P. Hansen, B. Jaumard and G. Savard, New branch-and-bound rules for for linear bilevel programming, SIAM Journal on Scientific and Statistical Computing, 13 (1992), 1194-1217. doi: 10.1137/0913069. [9] R. Horst and V. T. Nguyen, DC Programming: Overview, Journal of Optimization Theory and Application, 101 (1999), 1-43. doi: 10.1023/A:1021765131316. [10] D. M. Le and V. T. Nguyen, A global optimization method for solving convex quadratic bilevel programming problems, Journal of Global Optimization, 26 (2003), 199-219. doi: 10.1023/A:1023047900333. [11] H. Markowitz, Portfolio selection, Journal of Finance, 7 (1952), 77-99. doi: 10.2307/2975974. [12] R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, First edition, (1970). [13] Marc C. Steinbach, Markowitz revisited mean variance model in financial protfolio a nalysis, SIAM review, 43 (2001), 31-85. [14] H. A. Le Thi, Contribution à l'optimisation non convex and l'optimisation globale: Théorie, Algorithmes et Applications, Habilitation à Diriger des recherches, Université de Rouen, 1997. [15] H. A. Le Thi and T. Pham Dinh, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem, Optimization, 50 (2001), 93-120. [16] H. A. Le Thi, T. Pham Dinh, N. Nguyen Canh and T. Nguyen Van, DC programming techniques for solving a class of nonlinear bilevel programs, Journal of Global Optimization, 44 (2009), 313-337. doi: 10.1007/s10898-008-9325-7. [17] H. A. Le Thi and T. Pham Dinh, The DC (difference of convex functions) Programming and DCA revisited with DC models of real world non convex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1. [18] H. A. Le Thi, T. Pham Dinh and V. N. Huynh, Exact penalty and error bounds in DC programming,, to appear in Journal of Global Optimization., (). [19] H. A. Le Thi, T. Pham Dinh and V. N. Huynh, Convergence analysis of DCA for DC programming with subanalytic data, Research Report (2009), National Institute for Applied Sciences, Rouen. [20] H. A. Le Thi and T. Pham Dinh, Large scale global molecular optimization from exact distance matrices by a d.c. optimization approach, SIAM Journal on Optimization, 14 (2003), 77-114. doi: 10.1137/S1052623498342794. [21] H. A. Le Thi, T. Pham Dinh and D. M. Le, Numerical solution for optimization over the efficient set by DC optimization algorithms, Operation Research Letters, 19 (1996), 117-128. doi: 10.1016/0167-6377(96)00022-3. [22] H. Tuy, "Convex Analysis and Global Optimization," Kluwer Academic Publisher, First edition, 1997.

show all references

##### References:
 [1] G. J. Alexander and A. M. Baptista, A Portfolio selection with a drawdown constraint, Journal of Banking & Finance, 30 (2006), 3171-3189. doi: 10.1016/j.jbankfin.2005.12.006. [2] J. F. Bard, Some properties of the bilevel programming problem, Journal of Optimization Theory and Applications, 68 (1991), 371-378. doi: 10.1007/BF00941574. [3] B. Colson, P. Marcotte and G. Savard, Bilevel programming: a survey, A Quarterly Journal of Operations Research, 3 (2005), 87-107. [4] , DC Programming and DCA:, \url{http://lita.sciences.univ-metz.fr/~lethi/DCA.html}., (). [5] T. Pham Dinh and H. A. Le Thi, Convex analysis approach to DC programming: Theory, algorithms and applications, Acta Mathematica Vietnamica, 22 (1997), 289-355. [6] T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem, SIAM J. Optimization, 8 (1998), 476-505. doi: 10.1137/S1052623494274313. [7] T. Pham Dinh, N. Nguyen Canh and H. A. Le Thi, An efficient combination of DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs, Journal of Global Optimization, 48 (2010), 595-632. doi: 10.1007/s10898-009-9507-y. [8] P. Hansen, B. Jaumard and G. Savard, New branch-and-bound rules for for linear bilevel programming, SIAM Journal on Scientific and Statistical Computing, 13 (1992), 1194-1217. doi: 10.1137/0913069. [9] R. Horst and V. T. Nguyen, DC Programming: Overview, Journal of Optimization Theory and Application, 101 (1999), 1-43. doi: 10.1023/A:1021765131316. [10] D. M. Le and V. T. Nguyen, A global optimization method for solving convex quadratic bilevel programming problems, Journal of Global Optimization, 26 (2003), 199-219. doi: 10.1023/A:1023047900333. [11] H. Markowitz, Portfolio selection, Journal of Finance, 7 (1952), 77-99. doi: 10.2307/2975974. [12] R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, First edition, (1970). [13] Marc C. Steinbach, Markowitz revisited mean variance model in financial protfolio a nalysis, SIAM review, 43 (2001), 31-85. [14] H. A. Le Thi, Contribution à l'optimisation non convex and l'optimisation globale: Théorie, Algorithmes et Applications, Habilitation à Diriger des recherches, Université de Rouen, 1997. [15] H. A. Le Thi and T. Pham Dinh, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem, Optimization, 50 (2001), 93-120. [16] H. A. Le Thi, T. Pham Dinh, N. Nguyen Canh and T. Nguyen Van, DC programming techniques for solving a class of nonlinear bilevel programs, Journal of Global Optimization, 44 (2009), 313-337. doi: 10.1007/s10898-008-9325-7. [17] H. A. Le Thi and T. Pham Dinh, The DC (difference of convex functions) Programming and DCA revisited with DC models of real world non convex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1. [18] H. A. Le Thi, T. Pham Dinh and V. N. Huynh, Exact penalty and error bounds in DC programming,, to appear in Journal of Global Optimization., (). [19] H. A. Le Thi, T. Pham Dinh and V. N. Huynh, Convergence analysis of DCA for DC programming with subanalytic data, Research Report (2009), National Institute for Applied Sciences, Rouen. [20] H. A. Le Thi and T. Pham Dinh, Large scale global molecular optimization from exact distance matrices by a d.c. optimization approach, SIAM Journal on Optimization, 14 (2003), 77-114. doi: 10.1137/S1052623498342794. [21] H. A. Le Thi, T. Pham Dinh and D. M. Le, Numerical solution for optimization over the efficient set by DC optimization algorithms, Operation Research Letters, 19 (1996), 117-128. doi: 10.1016/0167-6377(96)00022-3. [22] H. Tuy, "Convex Analysis and Global Optimization," Kluwer Academic Publisher, First edition, 1997.
 [1] Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041 [2] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [3] Bhawna Kohli. Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3209-3221. doi: 10.3934/jimo.2020114 [4] Ana F. Carazo, Ignacio Contreras, Trinidad Gómez, Fátima Pérez. A project portfolio selection problem in a group decision-making context. Journal of Industrial and Management Optimization, 2012, 8 (1) : 243-261. doi: 10.3934/jimo.2012.8.243 [5] Bo Li, Yadong Shu. The skewness for uncertain random variable and application to portfolio selection problem. Journal of Industrial and Management Optimization, 2022, 18 (1) : 457-467. doi: 10.3934/jimo.2020163 [6] Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 [7] Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial and Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 [8] Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 [9] Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102 [10] Nazih Abderrazzak Gadhi. A note on the paper "Sufficient optimality conditions using convexifactors for optimistic bilevel programming problem". Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021103 [11] Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557 [12] Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 [13] Alireza Goli, Hasan Khademi Zare, Reza Tavakkoli-Moghaddam, Ahmad Sadeghieh. Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014 [14] Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092 [15] Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091 [16] Gabriella Pinzari. Global Kolmogorov tori in the planetary $\boldsymbol N$-body problem. Announcement of result. Electronic Research Announcements, 2015, 22: 55-75. doi: 10.3934/era.2015.22.55 [17] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [18] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [19] G.S. Liu, J.Z. Zhang. Decision making of transportation plan, a bilevel transportation problem approach. Journal of Industrial and Management Optimization, 2005, 1 (3) : 305-314. doi: 10.3934/jimo.2005.1.305 [20] Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025

Impact Factor: