Research On Theory And Algorithms Of Quadratic Fractional Programming

Fractional programming is a kind of important non-linear mathematical programming problem.It has been widely used in the fields of economy,finance,image processing and portfolio investment.This paper mainly studies two kinds of fractal programming problems: the ratio of quadratic functions with single-sided quadratic constraints and the ratio of quadratic functions with two-sided quadratic constraints.two-sided constraints are the more general form of single-sided constraints.This paper focuses on single-sided constraints and tries to extend the conclusions and algorithms of single-sided constraints to two-sided constraints.Because of the non-convex property of the objective function of quadratic fractional programming,it is difficult to solve the global optimal solution of this kind of problem.At present,the known algorithms are mainly divided into two categories.One is to solve a series of QCQP problems by using Dinkelbach parameterization technique;the other is to transform the primal problem into SDP problem,to find the optimal value of the original problem,and then to solve a QCQP problem.Unfortunately,these two algorithms have high computational complexity and are not suitable for large-scale problems.This paper presents a very efficient algorithm for quadratic fractional programming with quadratic constraints.Starting with the study of its Lagrange dual problem,this paper estimates the upper and lower bounds of the optimal Lagrange multiplier,and proves the strong duality of the primal problem and the dual problem.The value of the optimal Lagrange multiplier is approximated by dichotomy.In each step,only one minimum eigenvalue or minimum generalized eigenvalue problem is solved,and then the global optimal solution of the quadratic fractional programming problem can be obtained.Because this algorithm only needs to solve the minimum eigenvalue problem,the computational efficiency of this algorithm is very high for large-scale sparse problems.The numerical experiments in this paper prove the correctness of this algorithm,and show that it has great advantages in computational complexity compared with other algorithms.