On Chebyshev Center of the Intersection of Two Ellipsoids

Xiaoli Cen; Yong Xia; Runxuan Gao; Tianzhi Yang

doi:10.1007/978-3-030-21803-4_14

On Chebyshev Center of the Intersection of Two Ellipsoids

Xiaoli Cen
, Yong Xia^*
, Runxuan Gao
, Tianzhi Yang

^*Corresponding author for this work

School of Mathematical Sciences

Beihang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

We study the problem of finding the smallest ball covering the intersection of two ellipsoids, which is also known as the Chebyshev center problem (CC). Semidefinite programming (SDP) relaxation is an efficient approach to approximate (CC). In this paper, we first establish the worst-case approximation bound of (SDP). Then we show that (CC) can be globally solved in polynomial time. As a by-product, one can randomly generate Celis-Dennis-Tapia subproblems having positive Lagrangian duality gap with high probability.

Original language	English
Title of host publication	Optimization of Complex Systems
Subtitle of host publication	Theory, Models, Algorithms and Applications, 2019
Editors	Hoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
Publisher	Springer Verlag
Pages	135-144
Number of pages	10
ISBN (Print)	9783030218027
DOIs	https://doi.org/10.1007/978-3-030-21803-4_14
State	Published - 2020
Event	6th World Congress on Global Optimization, WCGO 2019 - Metz, France Duration: 8 Jul 2019 → 10 Jul 2019

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	991
ISSN (Print)	2194-5357
ISSN (Electronic)	2194-5365

Conference

Conference	6th World Congress on Global Optimization, WCGO 2019
Country/Territory	France
City	Metz
Period	8/07/19 → 10/07/19

Keywords

Approximation bound
CDT subproblem
Chebyshev center
Polynomial solvability
Semidefinite programming

Access to Document

10.1007/978-3-030-21803-4_14

Cite this

Cen, X., Xia, Y., Gao, R., & Yang, T. (2020). On Chebyshev Center of the Intersection of Two Ellipsoids. In H. A. Le Thi, H. M. Le, & T. Pham Dinh (Eds.), Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019 (pp. 135-144). (Advances in Intelligent Systems and Computing; Vol. 991). Springer Verlag. https://doi.org/10.1007/978-3-030-21803-4_14

@inproceedings{3c07f7f64bcb42c59d6a12799efcbd43,

title = "On Chebyshev Center of the Intersection of Two Ellipsoids",

abstract = "We study the problem of finding the smallest ball covering the intersection of two ellipsoids, which is also known as the Chebyshev center problem (CC). Semidefinite programming (SDP) relaxation is an efficient approach to approximate (CC). In this paper, we first establish the worst-case approximation bound of (SDP). Then we show that (CC) can be globally solved in polynomial time. As a by-product, one can randomly generate Celis-Dennis-Tapia subproblems having positive Lagrangian duality gap with high probability.",

keywords = "Approximation bound, CDT subproblem, Chebyshev center, Polynomial solvability, Semidefinite programming",

author = "Xiaoli Cen and Yong Xia and Runxuan Gao and Tianzhi Yang",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 6th World Congress on Global Optimization, WCGO 2019 ; Conference date: 08-07-2019 Through 10-07-2019",

year = "2020",

doi = "10.1007/978-3-030-21803-4\_14",

language = "英语",

isbn = "9783030218027",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "135--144",

editor = "\{Le Thi\}, \{Hoai An\} and Le, \{Hoai Minh\} and \{Pham Dinh\}, Tao",

booktitle = "Optimization of Complex Systems",

address = "德国",

}

Cen, X, Xia, Y, Gao, R & Yang, T 2020, On Chebyshev Center of the Intersection of Two Ellipsoids. in HA Le Thi, HM Le & T Pham Dinh (eds), Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019. Advances in Intelligent Systems and Computing, vol. 991, Springer Verlag, pp. 135-144, 6th World Congress on Global Optimization, WCGO 2019, Metz, France, 8/07/19. https://doi.org/10.1007/978-3-030-21803-4_14

On Chebyshev Center of the Intersection of Two Ellipsoids. / Cen, Xiaoli; Xia, Yong; Gao, Runxuan et al.
Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019. ed. / Hoai An Le Thi; Hoai Minh Le; Tao Pham Dinh. Springer Verlag, 2020. p. 135-144 (Advances in Intelligent Systems and Computing; Vol. 991).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On Chebyshev Center of the Intersection of Two Ellipsoids

AU - Cen, Xiaoli

AU - Xia, Yong

AU - Gao, Runxuan

AU - Yang, Tianzhi

PY - 2020

Y1 - 2020

N2 - We study the problem of finding the smallest ball covering the intersection of two ellipsoids, which is also known as the Chebyshev center problem (CC). Semidefinite programming (SDP) relaxation is an efficient approach to approximate (CC). In this paper, we first establish the worst-case approximation bound of (SDP). Then we show that (CC) can be globally solved in polynomial time. As a by-product, one can randomly generate Celis-Dennis-Tapia subproblems having positive Lagrangian duality gap with high probability.

AB - We study the problem of finding the smallest ball covering the intersection of two ellipsoids, which is also known as the Chebyshev center problem (CC). Semidefinite programming (SDP) relaxation is an efficient approach to approximate (CC). In this paper, we first establish the worst-case approximation bound of (SDP). Then we show that (CC) can be globally solved in polynomial time. As a by-product, one can randomly generate Celis-Dennis-Tapia subproblems having positive Lagrangian duality gap with high probability.

KW - Approximation bound

KW - CDT subproblem

KW - Chebyshev center

KW - Polynomial solvability

KW - Semidefinite programming

UR - https://www.scopus.com/pages/publications/85068375136

U2 - 10.1007/978-3-030-21803-4_14

DO - 10.1007/978-3-030-21803-4_14

M3 - 会议稿件

AN - SCOPUS:85068375136

SN - 9783030218027

T3 - Advances in Intelligent Systems and Computing

SP - 135

EP - 144

BT - Optimization of Complex Systems

A2 - Le Thi, Hoai An

A2 - Le, Hoai Minh

A2 - Pham Dinh, Tao

PB - Springer Verlag

T2 - 6th World Congress on Global Optimization, WCGO 2019

Y2 - 8 July 2019 through 10 July 2019

ER -

On Chebyshev Center of the Intersection of Two Ellipsoids

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this