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 & 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. doi: 10.1016/j.jbankfin.2005.12.006. Google Scholar

[2]

J. F. Bard, Some properties of the bilevel programming problem,, Journal of Optimization Theory and Applications, 68 (1991), 371. doi: 10.1007/BF00941574. Google Scholar

[3]

B. Colson, P. Marcotte and G. Savard, Bilevel programming: a survey,, A Quarterly Journal of Operations Research, 3 (2005), 87. Google Scholar

[4]

, DC Programming and DCA:, \url{http://lita.sciences.univ-metz.fr/~lethi/DCA.html}., (). Google Scholar

[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. Google Scholar

[6]

T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem,, SIAM J. Optimization, 8 (1998), 476. doi: 10.1137/S1052623494274313. Google Scholar

[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. doi: 10.1007/s10898-009-9507-y. Google Scholar

[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. doi: 10.1137/0913069. Google Scholar

[9]

R. Horst and V. T. Nguyen, DC Programming: Overview,, Journal of Optimization Theory and Application, 101 (1999), 1. doi: 10.1023/A:1021765131316. Google Scholar

[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. doi: 10.1023/A:1023047900333. Google Scholar

[11]

H. Markowitz, Portfolio selection,, Journal of Finance, 7 (1952), 77. doi: 10.2307/2975974. Google Scholar

[12]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970). Google Scholar

[13]

Marc C. Steinbach, Markowitz revisited mean variance model in financial protfolio a nalysis,, SIAM review, 43 (2001), 31. Google Scholar

[14]

H. A. Le Thi, Contribution à l'optimisation non convex and l'optimisation globale: Théorie, Algorithmes et Applications,, Habilitation à Diriger des recherches, (1997). Google Scholar

[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. Google Scholar

[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. doi: 10.1007/s10898-008-9325-7. Google Scholar

[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. doi: 10.1007/s10479-004-5022-1. Google Scholar

[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., (). Google Scholar

[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), (2009). Google Scholar

[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. doi: 10.1137/S1052623498342794. Google Scholar

[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. doi: 10.1016/0167-6377(96)00022-3. Google Scholar

[22]

H. Tuy, "Convex Analysis and Global Optimization,", Kluwer Academic Publisher, (1997). Google Scholar

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. doi: 10.1016/j.jbankfin.2005.12.006. Google Scholar

[2]

J. F. Bard, Some properties of the bilevel programming problem,, Journal of Optimization Theory and Applications, 68 (1991), 371. doi: 10.1007/BF00941574. Google Scholar

[3]

B. Colson, P. Marcotte and G. Savard, Bilevel programming: a survey,, A Quarterly Journal of Operations Research, 3 (2005), 87. Google Scholar

[4]

, DC Programming and DCA:, \url{http://lita.sciences.univ-metz.fr/~lethi/DCA.html}., (). Google Scholar

[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. Google Scholar

[6]

T. Pham Dinh and H. A. Le Thi, DC optimization algorihms for solving the trust region subproblem,, SIAM J. Optimization, 8 (1998), 476. doi: 10.1137/S1052623494274313. Google Scholar

[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. doi: 10.1007/s10898-009-9507-y. Google Scholar

[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. doi: 10.1137/0913069. Google Scholar

[9]

R. Horst and V. T. Nguyen, DC Programming: Overview,, Journal of Optimization Theory and Application, 101 (1999), 1. doi: 10.1023/A:1021765131316. Google Scholar

[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. doi: 10.1023/A:1023047900333. Google Scholar

[11]

H. Markowitz, Portfolio selection,, Journal of Finance, 7 (1952), 77. doi: 10.2307/2975974. Google Scholar

[12]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970). Google Scholar

[13]

Marc C. Steinbach, Markowitz revisited mean variance model in financial protfolio a nalysis,, SIAM review, 43 (2001), 31. Google Scholar

[14]

H. A. Le Thi, Contribution à l'optimisation non convex and l'optimisation globale: Théorie, Algorithmes et Applications,, Habilitation à Diriger des recherches, (1997). Google Scholar

[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. Google Scholar

[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. doi: 10.1007/s10898-008-9325-7. Google Scholar

[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. doi: 10.1007/s10479-004-5022-1. Google Scholar

[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., (). Google Scholar

[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), (2009). Google Scholar

[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. doi: 10.1137/S1052623498342794. Google Scholar

[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. doi: 10.1016/0167-6377(96)00022-3. Google Scholar

[22]

H. Tuy, "Convex Analysis and Global Optimization,", Kluwer Academic Publisher, (1997). Google Scholar

[1]

Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & 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 & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[3]

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 & Management Optimization, 2012, 8 (1) : 243-261. doi: 10.3934/jimo.2012.8.243

[4]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

[5]

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 & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[6]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020102

[7]

Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87

[8]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[9]

Rafał Kamocki, Marek Majewski. On the continuous dependence of solutions to a fractional Dirichlet problem. The case of saddle points. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2557-2568. doi: 10.3934/dcdsb.2014.19.2557

[10]

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 & Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014

[11]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092

[12]

Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091

[13]

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

[14]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[15]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

[16]

Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025

[17]

G.S. Liu, J.Z. Zhang. Decision making of transportation plan, a bilevel transportation problem approach. Journal of Industrial & Management Optimization, 2005, 1 (3) : 305-314. doi: 10.3934/jimo.2005.1.305

[18]

Shaoyong Lai, Qichang Xie. A selection problem for a constrained linear regression model. Journal of Industrial & Management Optimization, 2008, 4 (4) : 757-766. doi: 10.3934/jimo.2008.4.757

[19]

Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial & Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049

[20]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775

 Impact Factor: 

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]