Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems |
| |
Authors: | Ricardo G Ródenas M Luz López Doroteo Verastegui |
| |
Institution: | (1) Departamento de Matemáticas Escuela Universitaria Politécnica de Almadén, Universidad de Castilla-La Mancha, Castilla, Espana |
| |
Abstract: | Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the
optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter.
In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability
of the algorithm will depend on the possibility of solving the subproblems.
Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional
programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability
of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied.
We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae
to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient
conditions for the convergence of these modifications.
Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional
programming to evaluate the efficiency of these methods have been carried out. |
| |
Keywords: | Fractional Programming Parametric Optimization Nonconvex Programming Nonlinear Programming AMS subject classification 90C32 90C31 90C26 90C30 |
本文献已被 SpringerLink 等数据库收录! |