Global optimization for a class of fractional programming problems

Shu Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Wenxun Xing

Research output: Contribution to journalArticle

22 Citations (Scopus)

Abstract

This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the "problem-defining" matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.

Original languageEnglish
Pages (from-to)337-353
Number of pages17
JournalJournal of Global Optimization
Volume45
Issue number3
DOIs
Publication statusPublished - 2009 Nov 1

Fingerprint

Fractional Programming
Global optimization
Global Optimization
Quadratic Function
Duality Gap
Global Minimizer
Quasi-Newton
Nonconvex Optimization
Nonconvex Problems
Line Search
Optimality Conditions
Search Methods
Fractional
Optimization Problem
Numerical Results
Class
Fractional programming

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this

Fang, Shu Cherng ; Gao, David Y. ; Sheu, Ruey-Lin ; Xing, Wenxun. / Global optimization for a class of fractional programming problems. In: Journal of Global Optimization. 2009 ; Vol. 45, No. 3. pp. 337-353.
@article{57a15506d534485bbd66f33a66878946,
title = "Global optimization for a class of fractional programming problems",
abstract = "This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the {"}problem-defining{"} matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.",
author = "Fang, {Shu Cherng} and Gao, {David Y.} and Ruey-Lin Sheu and Wenxun Xing",
year = "2009",
month = "11",
day = "1",
doi = "10.1007/s10898-008-9378-7",
language = "English",
volume = "45",
pages = "337--353",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "3",

}

Global optimization for a class of fractional programming problems. / Fang, Shu Cherng; Gao, David Y.; Sheu, Ruey-Lin; Xing, Wenxun.

In: Journal of Global Optimization, Vol. 45, No. 3, 01.11.2009, p. 337-353.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Global optimization for a class of fractional programming problems

AU - Fang, Shu Cherng

AU - Gao, David Y.

AU - Sheu, Ruey-Lin

AU - Xing, Wenxun

PY - 2009/11/1

Y1 - 2009/11/1

N2 - This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the "problem-defining" matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.

AB - This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the "problem-defining" matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.

UR - http://www.scopus.com/inward/record.url?scp=70349694498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349694498&partnerID=8YFLogxK

U2 - 10.1007/s10898-008-9378-7

DO - 10.1007/s10898-008-9378-7

M3 - Article

VL - 45

SP - 337

EP - 353

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 3

ER -