Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

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.     

双层线性分式规划求顶点的算法

基于双层线性分式规划的性质,讨论了上层不带约束的双层线性分式规划模型,给出了求其所有顶点的算法.此算法为进一步进行双层线性分式规划的灵敏度分析打下了坚实的基础,通过例子对算法进行了检验,并利用结果进行了灵敏度分析.     

Efficiency Conditions and Duality for a Class of Multiobjective Fractional Programming Problems

A class of constrained multiobjective fractional programming problems is considered from a viewpoint of the generalized convexity. Some basic concepts about the generalized convexity of functions, including a unified formulation of generalized convexity, are presented. Based upon the concept of the generalized convexity, efficiency conditions and duality for a class of multiobjective fractional programming problems are obtained. For three types of duals of the multiobjective fractional programming problem, the corresponding duality theorems are also established.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

Goal programming with linear fractional criteria

In this paper we present an extension of goal programming to include linear fractional criteria. The extension forms a natural link between goal programming (GP) and multiple objective linear fractional programming (MOLFP).     

Duality in disjunctive linear fractional programming

In this note a dual problem is formulated for a given class of disjunctive linear fractional programming problems. This result generalizes to fractional programming the duality theorem of disjunctive linear programming originated by Balas. Two examples are given to illustrate the result.     

On robust duality for fractional programming with uncertainty data

In this paper, we present a duality theory for fractional programming problems in the face of data uncertainty via robust optimization. By employing conjugate analysis, we establish robust strong duality for an uncertain fractional programming problem and its uncertain Wolfe dual programming problem by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. We show that our results encompass as special cases some programming problems considered in the recent literature. Moreover, we also show that robust strong duality always holds for linear fractional programming problems under scenario data uncertainty or constraint-wise interval uncertainty, and that the optimistic counterpart of the dual is tractable computationally.     

Global optimization for sum of generalized fractional functions

This paper considers the solution of generalized fractional programming (GFP) problem which contains various variants such as a sum or product of a finite number of ratios of linear functions, polynomial fractional programming, generalized geometric programming, etc. over a polytope. For such problems, we present an efficient unified method. In this method, by utilizing a transformation and a two-part linearization method, a sequence of linear programming relaxations of the initial nonconvex programming problem are derived which are embedded in a branch-and-bound algorithm. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

On Linear Fractional Programming Problem and its Computation Using a Neural Network Model

In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity. We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove certain results involving the neural network model. A computational experience is also reported.      

A modified objective function method for solving nonlinear multiobjective fractional programming problems

A new method is used for solving nonlinear multiobjective fractional programming problems having V-invex objective and constraint functions with respect to the same function η. In this approach, an equivalent vector programming problem is constructed by a modification of the objective fractional function in the original nonlinear multiobjective fractional problem. Furthermore, a modified Lagrange function is introduced for a constructed vector optimization problem. By the help of the modified Lagrange function, saddle point results are presented for the original nonlinear fractional programming problem with several ratios. Finally, a Mond-Weir type dual is associated, and weak, strong and converse duality results are established by using the introduced method with a modified function. To obtain these duality results between the original multiobjective fractional programming problem and its original Mond-Weir duals, a modified Mond-Weir vector dual problem with a modified objective function is constructed.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

Optimality conditions for nondifferentiable minimax fractional programming with complex variables

We show that a minimax fractional programming problem is equivalent to a minimax nonfractional parametric problem for a given parameter in complex space. We establish the necessary and sufficient optimality conditions of nondifferentiable minimax fractional programming problem with complex variables under generalized convexities.     

Restoration of efficiency in a goal programming problem with linear fractional criteria

The problem resulting from a goal programming problem with linear fractional criteria is not easy to solve due to the non-linear constraints inherent in its formulation. This paper introduces a simple and reliable test to establish whether a linear fractional goal programming problem has solutions that verify all goals and, if so, how to find them by solving a linear programming problem. This paper also outlines a new technique for restoring efficiency based on a minimax philosophy. An example is presented.     

具有(F,α,ε)-G凸的分式半无限规划问题的ε-最优性

首次引入了（F,α,ε）-G凸函数,（F,α,ε）-G拟凸函数和（F,α,ε）-G伪凸函数等概念,对已有的凸函数进行了推广,研究了涉及这类函数的一类分式半无限规划的ε-最优性条件,得到了一些有意义的结果．这些结果不仅是现有某些结果的推广,而且为诸如资源分配,投资组合等问题的研究提供了依据,也为理论上研究分式规划提供了参考．     

Duality for minmax programming involving V-invex functions

Sufficient optimality conditions and duality results for a class of minmax programming problems are obtained under V-invexity type assumptions on objective and constraint functions. Applications of these results to certain fractional and generalized fractional programming problems are also presented     

Optimality conditions and duality for a minimax fractional programming with generalized convexity

We establish the sufficient conditions for generalized fractional programming from a viewpoint of the generalized convexity. When the sufficient conditions are utilized, the corresponding duality theorems are derived for two types of duals of the generalized fractional programming. We extend the corresponding results of several authors.     

Continuous-Time Generalized Fractional Programming Problems. Part I: Basic Theory

This study, that will be presented as two parts, develops a computational approach to a class of continuous-time generalized fractional programming problems. The parametric method for finite-dimensional generalized fractional programming is extended to problems posed in function spaces. The developed method is a hybrid of the parametric method and discretization approach. In this paper (Part I), some properties of continuous-time optimization problems in parametric form pertaining to continuous-time generalized fractional programming problems are derived. These properties make it possible to develop a computational procedure for continuous-time generalized fractional programming problems. However, it is notoriously difficult to find the exact solutions of continuous-time optimization problems. In the accompanying paper (Part II), a further computational procedure with approximation will be proposed. This procedure will yield bounds on errors introduced by the numerical approximation. In addition, both the size of discretization and the precision of an approximation approach depend on predefined parameters.     

Mixed Duality without Constraint Qualification for Nonsmooth Fractional Programming

A class of nonsmooth multiobjective fractional programming is formulated. We establish the necessary and sufficient optimality conditions without the need of a constraint qualification. Then a mixed dual is introduced for a class of nonsmooth fractional programming problems, and various duality theorems are established without a constraint qualification.     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

A method of solving fully fuzzified linear fractional programming problems

In this paper, we propose a method of solving the fully fuzzified linear fractional programming problems, where all the parameters and variables are triangular fuzzy numbers. We transform the problem of maximizing a function with triangular fuzzy value into a deterministic multiple objective linear fractional programming problem with quadratic constraints. We apply the extension principle of Zadeh to add fuzzy numbers, an approximate version of the same principle to multiply and divide fuzzy numbers and the Kerre’s method to evaluate a fuzzy constraint. The results obtained by Buckley and Feuring in 2000 applied to fractional programming and disjunctive constraints are taken into consideration here. The method needs to add extra zero-one variables for treating disjunctive constraints. In order to illustrate our method we consider a numerical example.