A deterministic global optimization algorithm.

*(English)*Zbl 1114.65062The purpose of this paper is to introduce a new deterministic global optimization algorithm to solve a general linear sum of ratios programming problem (LFP). At first, an equivalent optimization problem (LFP1) of LFP is derived by exploiting the characteristics of the constraints of LFP. By a new linearizing method the linearization relaxation function of the objective function of LFP1 is proposed. Then the linear relaxation programming (RLP) of LFP1 is obtained which allows it to be incorporated into a branch-and-bound scheme. The proposed branch and bound algorithm is convergent to the global minimum through the successive refinement of the linear relaxation of the feasible region of the objection function and the solutions of a series of RLP. Finally, the numerical tests show the feasibility and efficiency of the proposed method.

Reviewer: Nada Djuranović-Miličić (Belgrade)

##### MSC:

65K05 | Numerical mathematical programming methods |

90C32 | Fractional programming |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |

##### Keywords:

general linear sum of ratios; linearization relaxation; branch and bound algorithm; convergence; numerical examples
PDF
BibTeX
XML
Cite

\textit{Y. Ji} et al., Appl. Math. Comput. 185, No. 1, 382--387 (2007; Zbl 1114.65062)

Full Text:
DOI

##### References:

[1] | Konno, H.; Watanabe, H., Bond portfolio optimization problems and their application to index tracking: a partial optimization approach, Journal of the operations research society of Japan, 39, 295-306, (1996) · Zbl 0873.90009 |

[2] | Konno, H.; Inori, M., Bond portfolio optimization by bilinear fractional programming, Journal of the operations research society of Japan, 32, 143-158, (1989) · Zbl 0675.90011 |

[3] | Charnes, A.; Cooper, W.W., Programming with linear fractional functionk, Naval research logistick quarterly, 9, 181-186, (1962) · Zbl 0127.36901 |

[4] | Konno, H.; Yajima, Y.; Maktkui, T., Parametric simples algorithms for solving a special class of nonconvex minimization problems, Journal of global optimization, 1, 65-81, (1991) |

[5] | Konno, H.; Abe, N., Minimization of the sum of three linear fractional functions, Journal of global optimization, 15, 419-432, (2002) · Zbl 0961.90115 |

[6] | 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 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.