Geometric properties for level sets of quadratic functions

Research output: Contribution to journalArticle

Abstract

In this paper, we study some fundamental geometrical properties related to the S-procedure. Given a pair of quadratic functions (g, f), it asks when “g(x)=0⟹f(x)≥0” can imply “(∃ λ∈ R) (∀ x∈ Rn) f(x) + λg(x) ≥ 0. ” Although the question has been answered by Xia et al. (Math Program 156:513–547, 2016), we propose a neat geometric proof for it (see Theorem 2): the S-procedure holds when, and only when, the level set { g= 0 } cannot separate the sublevel set { f< 0 }. With such a separation property, we proceed to prove that, for two polynomials (g, f) both of degree 2, the image set of g over { f< 0 } , g({ f< 0 }) , is always connected (see Theorem 4). It implies that the S-procedure is a kind of the intermediate value theorem. As a consequence, we know not only the infimum of g over { f≤ 0 } , but the extended results when g over { f≤ 0 } is unbounded from below or bounded but unattainable. The robustness and the sensitivity analysis of an optimization problem involving the pair (g, f) automatically follows. All the results in this paper are novel and fundamental in control theory and optimization.

Original languageEnglish
Pages (from-to)349-369
Number of pages21
JournalJournal of Global Optimization
Volume73
Issue number2
DOIs
Publication statusPublished - 2019 Feb 15

Fingerprint

Quadratic Function
Level Set
Intermediate value theorem
Control theory
Sensitivity analysis
Imply
Separation Property
Geometric proof
Polynomials
Control Theory
Sensitivity Analysis
Robustness
Optimization Problem
Polynomial
Optimization

All Science Journal Classification (ASJC) codes

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

Cite this

@article{aeb08fc6b67b4b9e9d2857f9fb7de01d,
title = "Geometric properties for level sets of quadratic functions",
abstract = "In this paper, we study some fundamental geometrical properties related to the S-procedure. Given a pair of quadratic functions (g, f), it asks when “g(x)=0⟹f(x)≥0” can imply “(∃ λ∈ R) (∀ x∈ Rn) f(x) + λg(x) ≥ 0. ” Although the question has been answered by Xia et al. (Math Program 156:513–547, 2016), we propose a neat geometric proof for it (see Theorem 2): the S-procedure holds when, and only when, the level set { g= 0 } cannot separate the sublevel set { f< 0 }. With such a separation property, we proceed to prove that, for two polynomials (g, f) both of degree 2, the image set of g over { f< 0 } , g({ f< 0 }) , is always connected (see Theorem 4). It implies that the S-procedure is a kind of the intermediate value theorem. As a consequence, we know not only the infimum of g over { f≤ 0 } , but the extended results when g over { f≤ 0 } is unbounded from below or bounded but unattainable. The robustness and the sensitivity analysis of an optimization problem involving the pair (g, f) automatically follows. All the results in this paper are novel and fundamental in control theory and optimization.",
author = "Nguyen, {Huu Quang} and Sheu, {Ruey Lin}",
year = "2019",
month = "2",
day = "15",
doi = "10.1007/s10898-018-0706-2",
language = "English",
volume = "73",
pages = "349--369",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "2",

}

Geometric properties for level sets of quadratic functions. / Nguyen, Huu Quang; Sheu, Ruey Lin.

In: Journal of Global Optimization, Vol. 73, No. 2, 15.02.2019, p. 349-369.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Geometric properties for level sets of quadratic functions

AU - Nguyen, Huu Quang

AU - Sheu, Ruey Lin

PY - 2019/2/15

Y1 - 2019/2/15

N2 - In this paper, we study some fundamental geometrical properties related to the S-procedure. Given a pair of quadratic functions (g, f), it asks when “g(x)=0⟹f(x)≥0” can imply “(∃ λ∈ R) (∀ x∈ Rn) f(x) + λg(x) ≥ 0. ” Although the question has been answered by Xia et al. (Math Program 156:513–547, 2016), we propose a neat geometric proof for it (see Theorem 2): the S-procedure holds when, and only when, the level set { g= 0 } cannot separate the sublevel set { f< 0 }. With such a separation property, we proceed to prove that, for two polynomials (g, f) both of degree 2, the image set of g over { f< 0 } , g({ f< 0 }) , is always connected (see Theorem 4). It implies that the S-procedure is a kind of the intermediate value theorem. As a consequence, we know not only the infimum of g over { f≤ 0 } , but the extended results when g over { f≤ 0 } is unbounded from below or bounded but unattainable. The robustness and the sensitivity analysis of an optimization problem involving the pair (g, f) automatically follows. All the results in this paper are novel and fundamental in control theory and optimization.

AB - In this paper, we study some fundamental geometrical properties related to the S-procedure. Given a pair of quadratic functions (g, f), it asks when “g(x)=0⟹f(x)≥0” can imply “(∃ λ∈ R) (∀ x∈ Rn) f(x) + λg(x) ≥ 0. ” Although the question has been answered by Xia et al. (Math Program 156:513–547, 2016), we propose a neat geometric proof for it (see Theorem 2): the S-procedure holds when, and only when, the level set { g= 0 } cannot separate the sublevel set { f< 0 }. With such a separation property, we proceed to prove that, for two polynomials (g, f) both of degree 2, the image set of g over { f< 0 } , g({ f< 0 }) , is always connected (see Theorem 4). It implies that the S-procedure is a kind of the intermediate value theorem. As a consequence, we know not only the infimum of g over { f≤ 0 } , but the extended results when g over { f≤ 0 } is unbounded from below or bounded but unattainable. The robustness and the sensitivity analysis of an optimization problem involving the pair (g, f) automatically follows. All the results in this paper are novel and fundamental in control theory and optimization.

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

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

U2 - 10.1007/s10898-018-0706-2

DO - 10.1007/s10898-018-0706-2

M3 - Article

AN - SCOPUS:85054635589

VL - 73

SP - 349

EP - 369

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 2

ER -