A Global Optimization Algorithm for Solving Linearly Constrained Quadratic Fractional Problems

Abstract

This paper first proposes a new and enhanced second order cone programming relaxation using the simultaneous matrix diagonalization technique for the linearly constrained quadratic fractional programming problem. The problem has wide applications in statics, economics and signal processing. Thus, fast and effective algorithm is required. The enhanced second order cone programming relaxation improves the relaxation effect and computational efficiency compared to the classical second order cone programming relaxation. Moreover, although the bound quality of the enhanced second order cone programming relaxation is worse than that of the copositive relaxation, the computational efficiency is significantly enhanced. Then we present a global algorithm based on the branch and bound framework. Extensive numerical experiments show that the enhanced second order cone programming relaxation-based branch and bound algorithm globally solves the problem in less computing time than the copositive relaxation approach.

Keywords

• second order cone programming relaxation
• copositive relaxation
• branch-and-bound algorithm
• global optimization