A global optimization algorithm for sum of linear ratios problem. (English) Zbl 1271.90046

Gao, Yuelin; Jin, Siqiao

J. Appl. Math. 2013, Article ID 276245, 7 p. (2013).

Summary: We equivalently transform the sum of linear ratios programming problem into bilinear programming problem, then by using the linear characteristics of convex envelope and concave envelope of double variables product function, linear relaxation programming of the bilinear programming problem is given, which can determine the lower bound of the optimal value of original problem. Therefore, a branch and bound algorithm for solving sum of linear ratios programming problem is put forward, and the convergence of the algorithm is proved. Numerical experiments are reported to show the effectiveness of the proposed algorithm.

MSC:

90C05

Linear programming

References:

[1]	H. Konno and H. Watanabe, “Bond portfolio optimization problems and their applications to index tracking: a partial optimization approach,” Journal of the Operations Research Society of Japan, vol. 39, no. 3, pp. 295-306, 1996. · Zbl 0873.90009
[2]	J. E. Falk and S. W. Palocsay, “Optimizing the sum of linear fractional functions,” in Recent Advances in Global Optimization (Princeton, NJ, 1991), Princeton Series in Computer Science, pp. 221-258, Princeton University Press, Princeton, NJ, USA, 1992.
[3]	R. Horst, P. M. Pardalos, and N. V. Thoai, Introduction to Global Optimization, vol. 48 of Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2nd edition, 2000. · Zbl 0966.90073
[4]	H. Konno, Y. Yajima, and T. Matsui, “Parametric simplex algorithms for solving a special class of nonconvex minimization problems,” Journal of Global Optimization, vol. 1, no. 1, pp. 65-81, 1991. · Zbl 0746.90056
[5]	H. Konno and N. Abe, “Minimization of the sum of three linear fractional functions,” Journal of Global Optimization, vol. 15, no. 4, pp. 419-432, 1999. · Zbl 0961.90115
[6]	P.-P. Shen and C.-F. Wang, “Global optimization for sum of linear ratios problem with coefficients,” Applied Mathematics and Computation, vol. 176, no. 1, pp. 219-229, 2006. · Zbl 1098.65066
[7]	W. Yanjun, S. Peiping, and L. Zhian, “A branch-and-bound algorithm to globally solve the sum of several linear ratios,” Applied Mathematics and Computation, vol. 168, no. 1, pp. 89-101, 2005. · Zbl 1079.65071
[8]	H. P. Benson, “Solving sum of ratios fractional programs via concave minimization,” Journal of Optimization Theory and Applications, vol. 135, no. 1, pp. 1-17, 2007. · Zbl 1145.90089
[9]	H. W. Jiao and Q. G. Feng, “Global optimization for sum of linear ratios problem using new pruning technique,” Mathematical Problem in Engineering, vol. 2008, Article ID 646205, 12 pages, 2008. · Zbl 1173.90543
[10]	C.-F. Wang and P.-P. Shen, “A global optimization algorithm for linear fractional programming,” Applied Mathematics and Computation, vol. 204, no. 1, pp. 281-287, 2008. · Zbl 1159.65064