Numerical Algebra, Control and Optimization (NACO)

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

Pages: 167 - 185, Volume 2, Issue 1, March 2012      doi:10.3934/naco.2012.2.167

       Abstract        References        Full Text (282.5K)       Related Articles       

Le Thi Hoai An - Laboratory of Theoretical and Applied Computer Science (LITA), Paul Verlaine - Metz University, Ile du Saulcy, 57045, Metz, France (email)
Tran Duc Quynh - Laboratory of Theorical and Applied computer Science LITA, UFR MIM, University Paul Verlaine of Metz, Ile du Saulcy-Metz 57045, France (email)
Pham Dinh Tao - Laboratory of Mathematics. National Institute for Applied Sciences, Rouen BP 08, Place Emile Blondel F 76131, Mont Saint Aignan Cedex, France (email)

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:  Bilevel Problem, DC Programming, DCA, branch and bound algorithm, portfolio selection problem.
Mathematics Subject Classification:  Secondary: 90C26, 90C30, 91G10.

Received: March 2011;      Revised: October 2011;      Available Online: March 2012.