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.

     

A new algorithm for generalized fractional programs

A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution of the primal problem. We also consider a variant of this new algorithm, based on scaling the “dual” parametric function. The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears that contrary to the primal approach, the “dual” approach is less influenced by scaling. This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, the Netherlands and was supported by J.N.I.C.T. (Portugal) under contract BD/707/90-RM.     

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 inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

An interior-point method for fractional programs with convex constraints

We present an interior-point method for a class of fractional programs with convex constraints. The proposed algorithm converges at a polynomial rate, similarly as in the case of a convex problem, even though fractional programs are only pseudo-convex. Here, the rate of convergence is measured in terms of the area of two-dimensional convex setsC _k containing the origin and certain projections of the optimal points, and the area ofC _k is reduced by a constant factorc < 1 at each iteration. The factorc depends only on the self-concordance parameter of a barrier function associated with the feasible set. We present an outline of a practical implementation of the proposed method, and we report results of some preliminary numerical experiments.Corresponding author.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Image space analysis of generalized fractional programs

The solution of a particular nonconvex program is usually very dependent on the structure of the problem. In this paper we identify classes of nonconvex problems involving either sums or products of ratios of linear terms which may be treated by analysis in a transformed space. In each class, the image space is defined by a mapping which associates a new variable with each original ratio of linear terms. In the image space, optimization is easy in certain directions, and the overall solution may be realized by sequentially optimizing in these directions.In addition to these ratio problems, we also show how to use image space analysis to treat the subclass of problems whose objective is to optimize a product of linear terms. For each class of nonconvex problems, we present an algorithm that locates global solutions by computing both upper and lower bounds on the solution and then solving a sequence of linear programming sub-problems. We also demonstrate the algorithms described in this paper by solving several example problems.     

A proximal point algorithm for generalized fractional programs

In this paper, the problem of solving generalized fractional programs will be addressed. This problem has been extensively studied and several algorithms have been proposed. In this work, we propose an algorithm that combines the proximal point method with a continuous min–max formulation of discrete generalized fractional programs. The proposed method can handle non-differentiable convex problems with possibly unbounded feasible constraints set, and solves at each iteration a convex program with unique dual solution. It generates two sequences that approximate the optimal value of the considered problem from below and from above at each step. For a class of functions, including the linear case, the convergence rate is at least linear.     

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.     

A global optimization algorithm for linear fractional and bilinear programs

In this paper a deterministic method is proposed for the global optimization of mathematical programs that involve the sum of linear fractional and/or bilinear terms. Linear and nonlinear convex estimator functions are developed for the linear fractional and bilinear terms. Conditions under which these functions are nonredundant are established. It is shown that additional estimators can be obtained through projections of the feasible region that can also be incorporated in a convex nonlinear underestimator problem for predicting lower bounds for the global optimum. The proposed algorithm consists of a spatial branch and bound search for which several branching rules are discussed. Illustrative examples and computational results are presented to demonstrate the efficiency of the proposed algorithm.     

An improved algorithm for generalized comparison of minisatellites

One of the most important objects in genetic mapping and forensic studies are minisatellites. They consist of a heterogeneous tandem array of short repeat units called variants. The evolution of minisatellites is realized by tandem duplication and tandem deletion of variants. Jeffrey et al. proposed a method to obtain the sequence of variants, called maps. Bérard and Rivals designed the first algorithm of comparison of two minisatellite maps under an evolutionary model including deletion, insertion, mutation, amplification and contraction. The complexity of this first algorithm was O(n⁴) in time and O(n³) in space where n is the size of the maps. In this paper we propose a more efficient algorithm using the same generic evolutionary model which is O(n³) in time and O(n²) in space. Our algorithm with this better efficiency can even solve generalized and more refined models.     

Solving sum of quadratic ratios fractional programs via monotonic function

In this paper, a branch-reduce-bound algorithm is proposed for globally solving a sum of quadratic ratios fractional programming with nonconvex quadratic constraints. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and the numerical experiments are given to show the feasibility of the proposed algorithm.     

A unifying approach to solve some classes of rank-three multiplicative and fractional programs involving linear functions

The aim of this paper is to propose a solution algorithm for solving a class of low-rank programs involving linear functions and having a polyhedral feasible region. In particular, the proposed solution method solves in an unifying approach some classes of rank-three multiplicative and fractional programs. The algorithm is based on the so called optimal level solutions method. Some optimality conditions are used to improve the performance of the proposed algorithm. Results of a computational test are provided.     

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.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Rates of convergence for a method of centers algorithm

Convergence of a method of centers algorithm for solving nonlinear programming problems is considered. The algorithm is defined so that the subproblems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the Fritz John or the Kuhn-Tucker optimality conditions. Under stronger assumptions, linear convergence rates are established for the sequences of objective function, constraint function, feasible point, and multiplier values.This work was supported in part by the National Aeronautics and Space Administration, Predoctoral Traineeship No. NsG(T)-117, and by the National Science Foundation, Grants No. GP-25081 and No. GK-32710.The author wishes to thank Donald M. Topkis for his valuable criticism of an earlier version of this paper and a referee for his helpful comments.     

Partial linearization for generalized fractional programming

An algorithm based on partial linearization is proposed to deal with generalized fractional programs. This algorithm is shown to be equivalent to the so called generalized Dinkelbach's algorithm applying to this problem. Hence we have another setting for this last algorithm.This research was supported by NSERC (grant A8312) and FCAR (grant 0899).