A new algorithm for the general quadratic programming problems with box constraints
Numerical Algorithms - 2009
Tóm tắt
In this paper, we propose a new branch-and-bound algorithm for the general quadratic problems with box constraints. We, first, transform the problem into a separable form by D. C. decomposition and Cholesky factorization of a positive definite matrix. Then a lower bounding technique is derived and a branch-and-bound algorithm is presented based on the lower bounding and rectangular bisection. Finally, preliminary computational results are reported.
Từ khóa
Tài liệu tham khảo
Bajirov, A.M., Rubinov, A.M.: Global optimization of marginal functions with applications to economic equilibrium. J. Glob. Optim. 20, 215–237 (2001)
Coleman, T.F., Hulbert, L.A.: A direct active set algorithm for large sparse quadratic programs with simple bounds. Math. Program. 45, 373–406 (1989)
De Angelis, P.L., Pardalos, P.M., Toraldo, G.: Quadratic programming with box constraints. In: Bomze, I.M., et al. (eds.) Developments in Global Optimization. Kluwer Academic, Dordrecht (1997)
Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Nav. Res. Logist. Q. 40, 373–392 (1993)
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic, Dordrecht (1995)
Konnoc, H.: Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints. Math. Program. 89, 233–250 (2001)
Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is np-hard. J. Glob. Optim. 1, 15–22 (1991)
Sherali, H.D., Smith, E.P.: A global optimization approach to a water distribution network design problem. J. Glob. Optim. 11, 107–132 (1997)
Le Thi, H.A., Pham Dinh, T.: Solving a class of linearly constrained indefinite quadratic problems by d.c. algorithm. J. Glob. Optim. 11, 253–285 (1997)
Le Thi, H.A., Pham Dinh, T.: A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrainednonconvex quadratic problems. J. Glob. Optim. 13, 171–206 (1998)
Vandenbussche, D., Nemhauser, G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. Ser. A (2004)
Vavasis, S.A.: Approximate algorithms for indefinite quadratic programming. Math. Program. 57, 279–311 (1992)
Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic progrmming problems with box constraints. J. Glob. Optim. 13, 151–170 (1998)
Ye, Y.: On the affine scaling algorithm for nonconvex quadratic programming. Math. Program. 56, 285–300 (1992)