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

Le  Thi Hoai An; Tran Duc Quynh; Pham Dinh Tao

doi:10.3934/naco.2012.2.167

Article Contents

2012, Volume 2, Issue 1: 167-185. Doi: 10.3934/naco.2012.2.167

This issue Previous Article Identification of water quality model parameters using artificial bee colony algorithm Next Article On some inverse singular value problems with Toeplitz-related structure

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
2.
Laboratory of Theorical and Applied computer Science LITA, UFR MIM, University Paul Verlaine of Metz, Ile du Saulcy-Metz 57045
3.
Laboratory of Mathematics. National Institute for Applied Sciences, Rouen BP 08, Place Emile Blondel F 76131, Mont Saint Aignan Cedex

Received: March 2011

Revised: October 2011

Published: March 2012

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Secondary: 90C26, 90C30, 91G10.

Citation:

Related Papers

Cited by

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: 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.