An SDP approach for quadratic fractional problems with a two-sided quadratic constraint

Van Bong Nguyen, Ruey-Lin Sheu, Yong Xia

Research output: Contribution to journalArticle

9 Citations (Scopus)

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 languageEnglish
Pages (from-to)701-719
Number of pages19
JournalOptimization Methods and Software
Volume31
Issue number4
DOIs
Publication statusPublished - 2016 Jul 3

Fingerprint

Quadratic Constraint
Fractional Programming
Quadratic Function
Lemma
Equality
Fractional
Convex optimization
Ellipsoid
Iterative methods
Computer programming
Reformulation
Convex Optimization
Nonlinear Programming
Polynomial time
Polynomials
Minimise
Iteration

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Optimization
  • Applied Mathematics

Cite this

@article{d31e8551343a47bc8851b98306a500bc,
title = "An SDP approach for quadratic fractional problems with a two-sided quadratic constraint",
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.",
author = "Nguyen, {Van Bong} and Ruey-Lin Sheu and Yong Xia",
year = "2016",
month = "7",
day = "3",
doi = "10.1080/10556788.2015.1029575",
language = "English",
volume = "31",
pages = "701--719",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",
number = "4",

}

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 journalArticle

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 -