Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming

Van Bong Nguyen, Ruey Lin Sheu, Yong Xia

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter μ and generate a family of quadratic subproblems (Pμ)′s subject to two quadratic constraints. Each (Pμ), if the problem dimension n≥3, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters [μ̲,μ¯]. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find μ numerically. Computational experiments show that our method solves the problem correctly and efficiently.

Original languageEnglish
Pages (from-to)399-416
Number of pages18
JournalJournal of Global Optimization
Volume64
Issue number2
DOIs
Publication statusPublished - 2016 Feb 1

Fingerprint

Rayleigh quotient
Semidefinite Programming
Unit Sphere
Polynomials
Decomposition
Experiments
Quadratic Constraint
Fractional Programming
Necessary Optimality Conditions
Line Search
Computational Experiments
Search Algorithm
Semidefinite programming
Lemma
Critical point
Polynomial time
NP-complete problem
Decompose
Interval

All Science Journal Classification (ASJC) codes

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

Cite this

@article{eac5e723cadf4faaab03ee1ad81fa6f1,
title = "Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming",
abstract = "The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter μ and generate a family of quadratic subproblems (Pμ)′s subject to two quadratic constraints. Each (Pμ), if the problem dimension n≥3, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters [μ̲,μ¯]. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find μ∗ numerically. Computational experiments show that our method solves the problem correctly and efficiently.",
author = "Nguyen, {Van Bong} and Sheu, {Ruey Lin} and Yong Xia",
year = "2016",
month = "2",
day = "1",
doi = "10.1007/s10898-015-0315-2",
language = "English",
volume = "64",
pages = "399--416",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "2",

}

Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming. / Nguyen, Van Bong; Sheu, Ruey Lin; Xia, Yong.

In: Journal of Global Optimization, Vol. 64, No. 2, 01.02.2016, p. 399-416.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming

AU - Nguyen, Van Bong

AU - Sheu, Ruey Lin

AU - Xia, Yong

PY - 2016/2/1

Y1 - 2016/2/1

N2 - The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter μ and generate a family of quadratic subproblems (Pμ)′s subject to two quadratic constraints. Each (Pμ), if the problem dimension n≥3, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters [μ̲,μ¯]. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find μ∗ numerically. Computational experiments show that our method solves the problem correctly and efficiently.

AB - The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter μ and generate a family of quadratic subproblems (Pμ)′s subject to two quadratic constraints. Each (Pμ), if the problem dimension n≥3, can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters [μ̲,μ¯]. We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find μ∗ numerically. Computational experiments show that our method solves the problem correctly and efficiently.

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

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

U2 - 10.1007/s10898-015-0315-2

DO - 10.1007/s10898-015-0315-2

M3 - Article

AN - SCOPUS:84957441996

VL - 64

SP - 399

EP - 416

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 2

ER -