Accelerating Branch and Bound Algorithm for Sum of Quadratic Ratios Problem

LI Xiaoai, LIU Jinwei, SHEN Peiping

Acta Mathematicae Applicatae Sinica ›› 2011, Vol. 34 ›› Issue (4) : 712-722.

PDF(335 KB)
中国科学院数学与系统科学研究院期刊网
PDF(335 KB)
Acta Mathematicae Applicatae Sinica ›› 2011, Vol. 34 ›› Issue (4) : 712-722. DOI: 10.12387/C2011078

Accelerating Branch and Bound Algorithm for Sum of Quadratic Ratios Problem

  • LI Xiaoai1, LIU Jinwei2, SHEN Peiping1
Author information +
History +

Abstract

The paper presents a new accelerating branch and bound algorithm for solving sum of quadratic ratios problem with nonconvex quadratic constraints (P). The algorithm establishes the linear relaxation programming problem (RLP) of problem (P) utilizing the linearizing technique. Through the successive refinement of the feasible region and the solution of a series of the linear programming problems, the upper and lower bounds of global optimal value are continuously updated. In order to accelerate convergence, a new deleting technique is given according to the optimality and feasibility. The proposed algorithm is proved to be convergent, and the numerical experiments show the efficiency and feasibility.  

Key words

sum of quadratic ratios / accelerating branch and bound / global optimization / deleting rule

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
LI Xiaoai, LIU Jinwei, SHEN Peiping. Accelerating Branch and Bound Algorithm for Sum of Quadratic Ratios Problem. Acta Mathematicae Applicatae Sinica, 2011, 34(4): 712-722 https://doi.org/10.12387/C2011078

References

[1] Colantoni C S, Manes R P. Programming, Profit Rates and Pricing Decisions. J. Accounting Review, 1969, 44: 467-481

[2] Sui Y K. The Expansion of Functions under Transformation and Its Application to Optimization. J. Computer Methods in Applied Mechanics and Engineering, 1994, 113: 253-262

[3] Benson H P. On the Global Optimization of Sums of Linear Fractional Function for Over a Convex Set. J. Journal of Optimization Theory and Applications, 2004, 121: 19-39

[4] Wang Y J, Shen P P. A Branch-and-Bound Algorithm to Globally Solve the Sum of Several Linear Ratios. J. Applied Mathematics and Computation, 2005, 168: 89-101

[5] Qu S J, Zhang K C. A Global Optimization Algorithm Using Parametric Linearization Relaxation. J. Applied Mathematics and Computation, 2007, 186: 763-771

[6] Shen P P, Chen Y Q. Solving Sum of Quadratic Ratios Fractional Programs Via Monotonic Function. J. Applied Mathematics and Computation, 2009, 121: 234-244

[7] Qu S J, Zhang K C. An Efficient Algorithm for Globally Minimizing Sum of Quadratic Ratios Problem with Nonconvex Quadrtic Constraints. J. Applied Mathematics and Computation, 2007, 189: 1624- 1636

[8] Li X A, Gu M N, Shen P P. An Efficient Algorithm of Global Optimization for Sum of Quadratic Ratios Problem with Nonconvex Quadratic Constraints. J. Mathematica Applicata, 2010, 2: 438-444

[9] Freund R W, Jarre F. Sloving the Sum-of-Ratios Problem by an Interior-point Method. J. Journal of Global Optimization, 2001,19: 83-102

[10] Shen P P, Li X I, Jiao H W. Accelerating Method of Global Optimization for Signomial Geometric Programming. J. Journal of Computational and Applied Mathematics, 2008, 214: 66-77

[11] An L T H, Tao P T. A Branch and Bound Method Via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems. J. Journal of Global Optimization, 1998, 13: 171-206

[12] Shen P P, Duan Y P. A Simplicial Branch and Duality Bound Algorithm for the Sum of Convex-convex Ratios Proplem. J. Journal of Computational and Applied Mathematics, 2009, 223: 145-158
PDF(335 KB)

223

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉