Solution Methods For Several Kinds Of Fractional Programming Problems

Fractional programming is widely used in computer vision,bond portfolio optimization,management science,economic and trade balance,image processing and many other fields.The lack of general global convergence criteria and possible non-convexity bring great challenge in both theory study and algorithm implementation for solving fractional programs.Most of the current global optimization algorithms are designed for special fractional programs,such as linear fractional programming,quadratic programming and generalized geometric programming,and the performance of the algorithm is not so good.In this regard,this paper studies the issues of designing efficient relaxation programs,partition rules and accelerating techniques based on existing theories and algorithm basis;In addition,combined with the known global optimization technique,this study also discusses how to develop global optimization algorithm with high performance and powerful solving ability.Global convergence is proved and a large amount of numerical experiments are tested to illustrate computing stability and execution efficiency of the presented algorithms.The main contents are as follows: 1.For sum of affine fractional programs,by utilizing auxiliary variables and monotonic transformation,an equivalent problem of the original problem is established.Based on the special structure of the equivalent problem and the dimensions of inner and outer space,inner-space and(or)outcome space linear relaxation programming is designed.By integrating new accelerating technique into branch and bound algorithm framework,a deterministic global optimization algorithm is developed for solving the sum of affine ratios program.Global convergence of the algorithm is proved and numerical results of some computational examples show that the algorithm is efficient and feasible.2.Aim at the generalized linear multiplicative programming,an equivalent problem with bilinear structure is constructed.A linear relaxation program and a convex relaxation program are designed based on the bilinear property of the equivalent problem,respectively.Deterministic global optimization algorithms are presented based on the relaxation programs.In order to improve the convergence speed of the algorithm,local probe strategy and proportionate partition techniques are studied.Global convergence of the algorithm is proved,and the feasibility and robustness of the algorithm is indicated by the results of numerical experiments and a random test.3.A parametric linear relaxation method is presented for quadratically constrained sum of quadratic ratios program.A deterministic global optimization algorithm is developed for solving the presented problem by combining reduction accelerating technique with branch and bound algorithm scheme.The global convergence property of the algorithm is proved,and some computational examples from recent literature and a large-scale randomized test are performed to verify the computing efficiency and robustness of the algorithm.4.In allusion to the mixed integer quadratically constrained quadratic programming problem,by using matrix elementary transformation of the original problem,a mixed integer bilinear equivalent problem is obtained.The linear relaxation programming problem is established based on convex envelope of bilinear terms and continuous relaxation.By combining linear relaxation with reduction-adjusting technique,a branch and bound algorithm for solving the presented algorithm is developed.The convergence property of the algorithm is proved and some numerical examples are carried out to validate the performance of the proposed algorithm.5.Consider the geometric polynomial programming problem,by utilizing variable substitution and monotonic transformation skills,an equivalent generalized geometric programming problem is proposed.Combining both arithmetic-geometric mean inequality and first-order Taylor approximation of generalized polynomials,a series of convex approximate sub-problems are established for solving the equivalent problem.Based on general inner approximation algorithm scheme,the presented algorithm is designed and convergence property of the algorithm is proved,results of numerical examples show that the algorithm has high efficiency and powerful flexibility.