S-lemma with equality and its applications

Yong Xia, Shu Wang, Ruey Lin Sheu

Research output: Contribution to journalArticle

19 Citations (Scopus)

Abstract

Let (Formula presented.) and (Formula presented.) be two quadratic functions having symmetric matrices (Formula presented.) and (Formula presented.). The S-lemma with equality asks when the unsolvability of the system (Formula presented.) implies the existence of a real number (Formula presented.) such that (Formula presented.). The problem is much harder than the inequality version which asserts that, under Slater condition, (Formula presented.) is unsolvable if and only if (Formula presented.) for some (Formula presented.). In this paper, we show that the S-lemma with equality does not hold only when the matrix (Formula presented.) has exactly one negative eigenvalue and (Formula presented.) is a non-constant linear function ((Formula presented.)). As an application, we can globally solve (Formula presented.) as well as the two-sided generalized trust region subproblem (Formula presented.) without any condition. Moreover, the convexity of the joint numerical range (Formula presented.) where (Formula presented.) is a (possibly non-convex) quadratic function and (Formula presented.) are affine functions can be characterized using the newly developed S-lemma with equality.

Original languageEnglish
Pages (from-to)513-547
Number of pages35
JournalMathematical Programming
Volume156
Issue number1-2
DOIs
Publication statusPublished - 2016 Mar 1

Fingerprint

Lemma
Equality
Quadratic Function
Trust Region Subproblem
Affine Function
Numerical Range
Symmetric matrix
Linear Function
Convexity

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Cite this

Xia, Yong ; Wang, Shu ; Sheu, Ruey Lin. / S-lemma with equality and its applications. In: Mathematical Programming. 2016 ; Vol. 156, No. 1-2. pp. 513-547.
@article{1dd3912181fd4f15a04c28dec2a706e2,
title = "S-lemma with equality and its applications",
abstract = "Let (Formula presented.) and (Formula presented.) be two quadratic functions having symmetric matrices (Formula presented.) and (Formula presented.). The S-lemma with equality asks when the unsolvability of the system (Formula presented.) implies the existence of a real number (Formula presented.) such that (Formula presented.). The problem is much harder than the inequality version which asserts that, under Slater condition, (Formula presented.) is unsolvable if and only if (Formula presented.) for some (Formula presented.). In this paper, we show that the S-lemma with equality does not hold only when the matrix (Formula presented.) has exactly one negative eigenvalue and (Formula presented.) is a non-constant linear function ((Formula presented.)). As an application, we can globally solve (Formula presented.) as well as the two-sided generalized trust region subproblem (Formula presented.) without any condition. Moreover, the convexity of the joint numerical range (Formula presented.) where (Formula presented.) is a (possibly non-convex) quadratic function and (Formula presented.) are affine functions can be characterized using the newly developed S-lemma with equality.",
author = "Yong Xia and Shu Wang and Sheu, {Ruey Lin}",
year = "2016",
month = "3",
day = "1",
doi = "10.1007/s10107-015-0907-0",
language = "English",
volume = "156",
pages = "513--547",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

S-lemma with equality and its applications. / Xia, Yong; Wang, Shu; Sheu, Ruey Lin.

In: Mathematical Programming, Vol. 156, No. 1-2, 01.03.2016, p. 513-547.

Research output: Contribution to journalArticle

TY - JOUR

T1 - S-lemma with equality and its applications

AU - Xia, Yong

AU - Wang, Shu

AU - Sheu, Ruey Lin

PY - 2016/3/1

Y1 - 2016/3/1

N2 - Let (Formula presented.) and (Formula presented.) be two quadratic functions having symmetric matrices (Formula presented.) and (Formula presented.). The S-lemma with equality asks when the unsolvability of the system (Formula presented.) implies the existence of a real number (Formula presented.) such that (Formula presented.). The problem is much harder than the inequality version which asserts that, under Slater condition, (Formula presented.) is unsolvable if and only if (Formula presented.) for some (Formula presented.). In this paper, we show that the S-lemma with equality does not hold only when the matrix (Formula presented.) has exactly one negative eigenvalue and (Formula presented.) is a non-constant linear function ((Formula presented.)). As an application, we can globally solve (Formula presented.) as well as the two-sided generalized trust region subproblem (Formula presented.) without any condition. Moreover, the convexity of the joint numerical range (Formula presented.) where (Formula presented.) is a (possibly non-convex) quadratic function and (Formula presented.) are affine functions can be characterized using the newly developed S-lemma with equality.

AB - Let (Formula presented.) and (Formula presented.) be two quadratic functions having symmetric matrices (Formula presented.) and (Formula presented.). The S-lemma with equality asks when the unsolvability of the system (Formula presented.) implies the existence of a real number (Formula presented.) such that (Formula presented.). The problem is much harder than the inequality version which asserts that, under Slater condition, (Formula presented.) is unsolvable if and only if (Formula presented.) for some (Formula presented.). In this paper, we show that the S-lemma with equality does not hold only when the matrix (Formula presented.) has exactly one negative eigenvalue and (Formula presented.) is a non-constant linear function ((Formula presented.)). As an application, we can globally solve (Formula presented.) as well as the two-sided generalized trust region subproblem (Formula presented.) without any condition. Moreover, the convexity of the joint numerical range (Formula presented.) where (Formula presented.) is a (possibly non-convex) quadratic function and (Formula presented.) are affine functions can be characterized using the newly developed S-lemma with equality.

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

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

U2 - 10.1007/s10107-015-0907-0

DO - 10.1007/s10107-015-0907-0

M3 - Article

AN - SCOPUS:84958116091

VL - 156

SP - 513

EP - 547

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -