Convergence of interval-type algorithms for generalized fractional programming

The purpose of this paper is to analyze the convergence of interval-type algorithms for solving the generalized fractional program. They are characterized by an interval [LB _k , UB _k ] including*, and the length of the interval is reduced at each iteration. A closer analysis of the bounds LB _k and UB _k allows to modify slightly the best known interval-type algorithm NEWMODM accordingly to prove its convergence and derive convergence rates similar to those for a Dinkelbach-type algorithm MAXMODM under the same conditions. Numerical results in the linear case indicate that the modifications to get convergence results are not obtained at the expense of the numerical efficiency since the modified version BFII is as efficient as NEWMODM and more efficient than MAXMODM.This research was supported by NSERC (Grant A8312) and FCAR (Grant 0899).     

An algorithm for generalized fractional programs

An algorithm is suggested that finds the constrained minimum of the maximum of finitely many ratios. The method involves a sequence of linear (convex) subproblems if the ratios are linear (convex-concave). Convergence results as well as rate of convergence results are derived. Special consideration is given to the case of (a) compact feasible regions and (b) linear ratios.The research of S. Schaible was supported by Grant Nos. A4534 and A5408 from NSERC. The authors thank two anonymous referees for their helpful remarks.     

Convergence of a Dinkelbach-type algorithm in generalized fractional programming

The convergence of a Dinkelbach-type algorithm in generalized fractional programming is obtained by considering the sensitivity of a parametrized problem. We show that the rate of convergence is at least equal to (1+5)/2 when regularity conditions hold in a neighbourhood of the optimal solution. We give also a necessary and sufficient condition for the convergence to be quadratic (which will be verified in particular in the linear case) and an idea of its implementation in the convex case.

---

Zusammenfassung Die Konvergenz eines Verfahrens i. S. von Dinkelbach zur Lösung verallgemeinerter Quotientenprogramme wird durch Untersuchung der Sensitivität eines parametrisierten Problems abgeleitet. Es wird gezeigt, daß die Konvergenzrate durch (1+5)/2 nach unten beschränkt ist, falls gewisse Regularitätsbedingungen in einer Umgebung der Optimallösung erfüllt sind. Ferner wird eine notwendige und hinreichende Bedingung zur quadratischen Konvergenz hergeleitet. Es wird gezeigt, wie diese im Falle konvexer Probleme implementiert werden kann.

     

On Generalized Linearity of Quadratic Fractional Functions

Quadratic fractional functions are proved to be quasilinear if and only if they are pseudo-linear. For these classes of functions, some characterizations are provided by means of the inertia of the quadratic form and the behavior of the gradient of the function itself. The study is then developed showing that generalized linear quadratic fractional functions share a particular structure. Therefore it is possible to suggest a sort of canonical form for those functions. A wider class of functions given by the sum of a quadratic fractional function and a linear one is also studied. In this case generalized linearity is characterized by means of simple conditions. Finally, it is deepened on the role played by generalized linear quadratic fractional functions in optimization problems.     

An approach to find redundant objective function(s) and redundant constraint(s) in multi-objective nonlinear stochastic fractional programming problems

Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists.     

Lifting, tilting and fractional programming revisited

Lifting, tilting and fractional programming, though seemingly different, reduce to a common optimization problem. This connection allows us to revisit key properties of these three problems on mixed integer linear sets. We introduce a simple common framework for these problems, and extend known results from each to the other two.     

Parametric linear fractional programming for an unbounded feasible region

Parametric analysis in linear fractional programming is significantly more complicated in case of an unbounded feasible region. We propose procedures which are based on a modified version of Martos' algorithm or a modification of Charnes-Cooper's algorithm, applying each to problems where either the objective function or the right-hand side is parametrized.     

A change of variable formula for the 2D fractional Brownian motion of Hurst index bigger or equal to 1/4

We prove a change of variable formula for the 2D fractional Brownian motion of index H bigger or equal to 1/4. For H strictly bigger than 1/4, our formula coincides with that obtained by using the rough paths theory. For H=1/4 (the more interesting case), there is an additional term that is a classical Wiener integral against an independent standard Brownian motion.     

A Finite Algorithm for a Class of Nonlinear Multiplicative Programs

The nonconvex problem of minimizing the product of a strictly convex quadratic function and the p-th power of a linear function over a convex polyhedron is considered. Some theoretical properties of the problem, such as the existence of minimum points and the generalized convexity of the objective function, are deepened on and a finite algorithm which solves the problem is proposed.     

Vector-valued lagrangian and multiobjective fractional programming duality

A class of multiobjective fractional programming problems is considered and duality results are established in terms of properly efficient solutions of the primal and dual programs. Further a vector-valued ratio type Lagrangian is introduced and certain vector saddlepoint results are presented.     

Optimization of chance constraint programming with sum-of-fractional objectives – An application to assembled printed circuit board problem

This paper presents a procedure to solve a chance constraint programming problem with sum-of-fractional objectives. The problem and the solution procedure are described with the help of a practical problem – assembled printed circuit boards (PCBs). Errors occurring during assembling PCBs are in general classified into three kinds, viz. machine errors, manual errors and other errors. These errors may lead to the rejection of the major portion of the production and hence result the manufacturer a huge loss. The problem is decomposed to have two objective functions; one is a sum-of-fractional objectives and the other is a non-linear objective with bounded constraints. The interest is to maximize the sum-of-fractional objectives and to minimize the non-linear objective, subject to stochastic and non-stochastic bounded environment. The first problem deals with the maximization of the profit (maximizing sum-of-fractional objectives) and the second deals with the minimization of the loss (errors), so as to obtain the maximum profit after removing the number of defective PCBs.     

The Complexity of Minimum Ratio Spanning Tree Problems

We examine the complexity of two minimum spanning tree problems with rational objective functions. We show that the Minimum Ratio Spanning Tree problem is NP-hard when the denominator is unrestricted in sign, thereby sharpening a previous complexity result. We then consider an extension of this problem where the objective function is the sum of two linear ratios whose numerators and denominators are strictly positive. This problem is shown to be NP-hard as well. We conclude with some results characterizing sufficient conditions for a globally optimal solution.     

On the pseudolinearity of quadratic fractional functions

The main result is a new characterization of the pseudolinearity of quadratic fractional functions. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA-T043276 and OTKA-K60480.     

非凸异分母分式多目标规划解的充分条件及对偶定理

指出了文[6]中的一个错误，基于不变凸性，对异分母分式多目标规划进行了讨论．在简单的正交假设下，给出了一系列解的充分条件，并建立了Mond－Weir型对偶定理．     

A new look at fractional programming

The parametric approach to fractional programming problems is examined and a new format is proposed for it. The latter reflects the fact that the approach as a whole capitalizes on a first-order necessary and sufficient optimality condition pertaining to differentiable pseudolinear functions.     

A sequential method for a class of pseudoconcave fractional problems

The aim of the paper is to maximize a pseudoconcave function which is the sum of a linear and a linear fractional function subject to linear constraints. Theoretical properties of the problem are first established and then a sequential method based on a simplex-like procedure is suggested.