Abstract
We consider a fractional programming problem (P) which minimizes a ratio of quadratic functions subject to a two-sided quadratic constraint. On one hand, (P) can be solved under some technical conditions by the Dinkelbach iterative method [W. Dinkelbach, On nonlinear fractional programming, Manag. Sci. 13 (1967), pp. 492–498] which has dominated the development of the area for nearly half a century. On the other hand, some special case of (P), typically the one in Beck and Teboulle [A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program. Ser. A 118 (2009), pp. 13–35], could be directly solved via an exact semi-definite reformulation, rather than iteratively. In this paper, by a recent breakthrough of Xia et al. [S-Lemma with equality and its applications. Available at http://arxiv.org/abs/1403.2816] on the S-lemma with equality, we propose to analyse (P) with three cases and show that each of them admits an exact SDP relaxation. As a result, (P) can be completely solved in polynomial time without any condition. Finally, the paper is presented with many interesting examples to illustrate the idea of our approach and to visualize the structure of the problem.
| Original language | English |
|---|---|
| Pages (from-to) | 701-719 |
| Number of pages | 19 |
| Journal | Optimization Methods and Software |
| Volume | 31 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2016 Jul 3 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Software
- Control and Optimization
- Applied Mathematics
Cite this
}
An SDP approach for quadratic fractional problems with a two-sided quadratic constraint. / Nguyen, Van Bong; Sheu, Ruey-Lin; Xia, Yong.
In: Optimization Methods and Software, Vol. 31, No. 4, 03.07.2016, p. 701-719.Research output: Contribution to journal › Article
TY - JOUR
T1 - An SDP approach for quadratic fractional problems with a two-sided quadratic constraint
AU - Nguyen, Van Bong
AU - Sheu, Ruey-Lin
AU - Xia, Yong
PY - 2016/7/3
Y1 - 2016/7/3
N2 - We consider a fractional programming problem (P) which minimizes a ratio of quadratic functions subject to a two-sided quadratic constraint. On one hand, (P) can be solved under some technical conditions by the Dinkelbach iterative method [W. Dinkelbach, On nonlinear fractional programming, Manag. Sci. 13 (1967), pp. 492–498] which has dominated the development of the area for nearly half a century. On the other hand, some special case of (P), typically the one in Beck and Teboulle [A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program. Ser. A 118 (2009), pp. 13–35], could be directly solved via an exact semi-definite reformulation, rather than iteratively. In this paper, by a recent breakthrough of Xia et al. [S-Lemma with equality and its applications. Available at http://arxiv.org/abs/1403.2816] on the S-lemma with equality, we propose to analyse (P) with three cases and show that each of them admits an exact SDP relaxation. As a result, (P) can be completely solved in polynomial time without any condition. Finally, the paper is presented with many interesting examples to illustrate the idea of our approach and to visualize the structure of the problem.
AB - We consider a fractional programming problem (P) which minimizes a ratio of quadratic functions subject to a two-sided quadratic constraint. On one hand, (P) can be solved under some technical conditions by the Dinkelbach iterative method [W. Dinkelbach, On nonlinear fractional programming, Manag. Sci. 13 (1967), pp. 492–498] which has dominated the development of the area for nearly half a century. On the other hand, some special case of (P), typically the one in Beck and Teboulle [A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program. Ser. A 118 (2009), pp. 13–35], could be directly solved via an exact semi-definite reformulation, rather than iteratively. In this paper, by a recent breakthrough of Xia et al. [S-Lemma with equality and its applications. Available at http://arxiv.org/abs/1403.2816] on the S-lemma with equality, we propose to analyse (P) with three cases and show that each of them admits an exact SDP relaxation. As a result, (P) can be completely solved in polynomial time without any condition. Finally, the paper is presented with many interesting examples to illustrate the idea of our approach and to visualize the structure of the problem.
UR - http://www.scopus.com/inward/record.url?scp=84928386408&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928386408&partnerID=8YFLogxK
U2 - 10.1080/10556788.2015.1029575
DO - 10.1080/10556788.2015.1029575
M3 - Article
AN - SCOPUS:84928386408
VL - 31
SP - 701
EP - 719
JO - Optimization Methods and Software
JF - Optimization Methods and Software
SN - 1055-6788
IS - 4
ER -