An SDP approach for non-convex quadratic fractional programming problems

  • 阮 文蓬

Student thesis: Doctoral Thesis


In this dissertation we are concerned with two types of quadratic fractional programming problems: one is a single ratio quadratic fractional problem with a twosided quadratic constraint (P) and the other is a sum-of-ratios problem (Q) Although we pose the problems (P) and (Q) in the form of ratios of quadratic functions after some parameterization scheme the fractional structure can be exchanged with a family of special types of quadratically constrained quadratic programming (QCQP) problems The QCQP problem is a long-standing difficult non-convex optimization problem which has attracted much attention in literature Therefore in dealing with (P) and (Q) we not only face the traditional QCQP problem but also an additional parameter coming from the ratio structure Since we feel that we can address the two issues all together we directly attack the quadratic fractional programming but apparently many results are new and useful to QCQP alone Our main idea is to probe the hidden convexity of (P) and (Q) in spite that both (P) and (Q) are themselves non-convex Our main tool is a powerful mechanism known as the S-lemma together with the semi-definite relaxation and the rank-one decomposition technique In order to apply the aforementioned tools for solving (P) and (Q) we transform or divide the problems into a few subcases; study new versions of S-lemma; and modify the rank-one decomposition procedure As a result we prove that (P) is indeed in the class of P and the NP-hard problem (Q) can be reduced to a much simpler one-dimensional search problem Our solution method is novel and can be easily implemented on the computer Our computational results show that the algorithms are very efficient in finding the global optimal solution compared with other existing methods
Date of Award2015 Jun 17
Original languageEnglish
SupervisorRuey-Lin Sheu (Supervisor)

Cite this