Global optimization for sum of linear ratios problem with coefficients. (English) Zbl 1098.65066

The following nonconvex optimization problem is considered: \[ \max f(x)\equiv \sum^m_{i=1}c_in_i(x)/d_i(x)\text{ subject to }x\in X\equiv\{x|Ax\leq b\}y, \] where \(m\geq 2\), \(n_i(x)\geq 0\), \(d_i(x)>0\) are for all \(x\in X\) affine functions on \(\mathbb R^n\), and \(c_i\) are constant coefficients, \(i=1,\dots,m\). The problem has applications e.g., in transportation planning, finance and investment, government planning, and other areas. A branch and bound algorithm for finding the global optimal solution of the problem is proposed, its convergence is proved, and its numerical effectiveness is demonstrated on smaller numerical examples with \(n=3\).


65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
Full Text: DOI


[1] Konno, H.; Watanabe, H., Bond portfolio optimization problems and their applications to index tracking, Journal of the Operations Society of Japan, 39, 295-306 (1996) · Zbl 0873.90009
[2] Falk, J. E.; Palocsay, S. W., Optimizing the sum of linear fractional functions, (Floudas, C. A.; Pardalos, P. M., Recent Advance in Global Optimization (1992), Princeton University Press: Princeton University Press Princeton, NJ)
[3] Konno, H.; Yajima, Y.; Matsui, T., Parametric simplex algorithms for solving a special class of nonconvex minimization problem, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[4] Falk, J. E.; Palocsay, S. W., Image space analysis of generalized fractional programs, Journal of Global Optimization, 4, 63-88 (1994) · Zbl 0809.90121
[5] Kuno, T., A branch and bound algorithm for maximizing the sum of several linear ratios, Journal of Global Optimization, 22, 155-174 (2002) · Zbl 1045.90071
[6] Konno, H.; Fukaish, K., A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems, Journal of Global Optimization, 18, 283-299 (2000) · Zbl 0971.90065
[7] Konno, H.; Abe, N., Minimization of the sum of three linear fractional functions, Journal of Global Optimization, 15, 419-432 (1999) · Zbl 0961.90115
[8] Konno, H.; Yamashita, H., Minimization of the sum and the product of several linear fractional functions over a polytope, Naval Research Logistics, 46, 583-596 (1999) · Zbl 0948.90132
[9] Benson, H. P., On the global optimization of sums of linear fractional functions over a convex set, Journal of Optimization Theory and Application, 121, 19-39 (2004) · Zbl 1140.90473
[10] Benson, H. P., Using concave envelopes to globally solve the nonlinear sum of ratios problem, Journal of Global Optimization, 22, 343-364 (2002) · Zbl 1045.90069
[11] Benson, H. P., On the construction of convex and concave envelope formulas for bilinear and fractional functions on quadrilaterals, Computational Optimization and Applications, 27, 5-22 (2004) · Zbl 1045.90068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.