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.     

An algorithm for a class of nonlinear fractional problems using ranking of the vertices

In this note we consider an algorithm for quasiconcave nonlinear fractional programming problems, based on ranking the vertices of a linear fractional programming problem and techniques from global optimization.     

A branch and bound algorithm for globally solving a class of nonconvex programming problems

A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.     

Necessary optimality conditions for nonsmooth generalized semi-infinite programming problems

This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated.     

Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Generalized fractional programming: Algorithms and numerical experimentation

Several algorithms to solve the generalized fractional program are summarized and compared numerically in the linear case. These algorithms are iterative procedures requiring the solution of a linear programming problem at each iteration in the linear case. The most efficient algorithm is obtained by marrying the Newton approach within the Dinkelbach approach for fractional programming.     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Accelerating method of global optimization for signomial geometric programming

Signomial geometric programming (SGP) has been an interesting problem for many authors recently. Many methods have been provided for finding locally optimal solutions of SGP, but little progress has been made for global optimization of SGP. In this paper we propose a new accelerating method for global optimization algorithm of SGP using a suitable deleting technique. This technique offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of SGP does not exist, and can be seen as an accelerating device for global optimization algorithm of SGP problem. Compared with the method of Shen and Zhang [Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput. 150 (2004) 99–114], numerical results show that the computational efficiency is improved obviously by using this new technique in the number of iterations, the required saving list length and the execution time of the algorithm.     

The bounds of feasible space on constrained nonconvex quadratic programming

This paper presents a method to estimate the bounds of the radius of the feasible space for a class of constrained nonconvex quadratic programmings. Results show that one may compute a bound of the radius of the feasible space by a linear programming which is known to be a P$P$-problem [N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395]. It is proposed that one applies this method for using the canonical dual transformation [D.Y. Gao, Canonical duality theory and solutions to constrained nonconvex quadratic programming, J. Global Optimization 29 (2004) 377–399] for solving a standard quadratic programming problem.     

The ellipsoid method and its consequences in combinatorial optimization

L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.).     

Farkas-type results for fractional programming problems

Considering a constrained fractional programming problem, within the present paper we present some necessary and sufficient conditions, which ensure that the optimal objective value of the considered problem is greater than or equal to a given real constant. The desired results are obtained using the Fenchel–Lagrange duality approach applied to an optimization problem with convex or difference of convex (DC) objective functions and finitely many convex constraints. These are obtained from the initial fractional programming problem using an idea due to Dinkelbach. We also show that our general results encompass as special cases some recently obtained Farkas-type results.     

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.     

The finite criss-cross method for hyperbolic programming

In this paper the finite criss-cross method is generalized to solve hyperbolic (fractional linear) programming problems. Just as in the case of linear or quadratic programming the criss-cross method can be initialized with any, not necessarily feasible basic solution. It is known that if the feasible region of the problem is unbounded then some of the known algorithms fail to solve the problem. Our criss-cross algorithm does not have such drawback. Finiteness of the procedure is proved under the usual mild assumptions. Some small numerical examples illustrate the main features of the algorithm and show that our method generates different iterates than other earlier published methods.     

Fractional programming by lower subdifferentiability techniques

The notion of lower subdifferentiability is applied to the analysis of convex fractional programming problems. In particular, duality results and optimality conditions are presented, and the applicability of a cutting-plane algorithm using lower subgradients is discussed. These methods are useful also in generalized fractional programming, where, in the linear case, the performance of the cutting-plane algorithm is compared with that of the most efficient version of the Dinkelbach method, which is based on the solution of a parametric linear programming problem.The authors wish to thank Mr. Jaume Timoneda for his help in the implementation of the numerical methods on the computer and the referees for valuable comments and suggestions; the present improved statement and proof of Proposition 2.1 is due to one of them. Financial support from the Dirección General de Investigación Científica y Técnica (DGICYT), under project PS89-0058, is gratefully acknowledged.     

Farkas' Lemma, other theorems of the alternative, and linear programming in infinite-dimensional spaces: a purely linear-algebraic approach

We briefly consider several formulations of Farkas' Lemma first. Then we assume the setting of two vector spaces, one of them being linearly ordered, over a linearly ordered field till the end of this article. In this setting, we state a generalized version of Farkas' Lemma and prove it in a purely linear-algebraic way. Afterwards, we present Theorems of Motzkin, Tucker, Carver, Dax, and some other theorems of the alternative that characterize consistency of a finite system of linear inequalities. We also mention the Key Theorem, which is a related result. Finally, we use Farkas' Lemma to prove the Duality Theorem for linear programming (with a finite number of linear constraints). The Duality Theorem that is proved here covers, among others, linear programming in a real vector space of finite or infinite dimension and lexicographic linear programming.     

Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterised by the existence of two optimisation problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimisation problem. In this paper we focus on the class of bilevel problems in which the upper level objective function is linear multiplicative, the lower level one is linear and the common constraint region is a bounded polyhedron. After replacing the lower level problem by its Karush–Kuhn–Tucker conditions, the existence of an extreme point which solves the problem is proved by using a penalty function approach. Besides, an algorithm based on the successive introduction of valid cutting planes is developed obtaining a global optimal solution. Finally, we generalise the problem by including upper level constraints which involve both level variables.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

Generalized linear fractional programming under interval uncertainty

Data in many real-life engineering and economical problems suffer from inexactness. Herein we assume that we are given some intervals in which the data can simultaneously and independently perturb. We consider a generalized linear fractional programming problem with interval data and present an efficient method for computing the range of optimal values. The method reduces the problem to solving from two to four real-valued generalized linear fractional programs, which can be computed in polynomial time using an appropriate interior point method solver.