Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming

Rujun Jiang; Duan Li

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

Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming

Rujun Jiang, Duan Li^*

^*Corresponding author for this work

Department of Data Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

2 Citations (Scopus)

Abstract

In this paper, we review recent development in semidefinite programming (SDP) based convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. QCQP problems have been well known as NP-hard nonconvex problems. We focus on convex relaxations of QCQP, which forms the base of global algorithms for solving QCQP. We review SDP relaxations, reformulation-linearization technique, SOC-RLT constraints and various other techniques based on lifting and linearization.

Original language	English
Title of host publication	Optimization of Complex Systems
Subtitle of host publication	Theory, Models, Algorithms and Applications
Editors	Hoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
Publisher	Springer Nature Switzerland AG
Pages	213-220
ISBN (Electronic)	9783030218034
ISBN (Print)	9783030218027
DOIs	https://doi.org/10.1007/978-3-030-21803-4_22
Publication status	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)
Abbreviated title	WCGO 2019
Place	France
City	Metz
Period	8/07/19 → 10/07/19

Access Output

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

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Jiang, R., & Li, D. (2020). Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming. In H. A. L. Thi, H. M. Le, & T. P. Dinh (Eds.), Optimization of Complex Systems: Theory, Models, Algorithms and Applications (pp. 213-220). (Advances in Intelligent Systems and Computing; Vol. 991). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-030-21803-4_22

Jiang, Rujun ; Li, Duan. / Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming. Optimization of Complex Systems: Theory, Models, Algorithms and Applications. editor / Hoai An Le Thi ; Hoai Minh Le ; Tao Pham Dinh. Springer Nature Switzerland AG, 2020. pp. 213-220 (Advances in Intelligent Systems and Computing).

@inproceedings{7380f010aaf5431fbfd136d37cbb3f2e,

title = "Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming",

abstract = "In this paper, we review recent development in semidefinite programming (SDP) based convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. QCQP problems have been well known as NP-hard nonconvex problems. We focus on convex relaxations of QCQP, which forms the base of global algorithms for solving QCQP. We review SDP relaxations, reformulation-linearization technique, SOC-RLT constraints and various other techniques based on lifting and linearization.",

author = "Rujun Jiang and Duan Li",

year = "2020",

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

language = "English",

isbn = "9783030218027",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Nature Switzerland AG",

pages = "213--220",

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

booktitle = "Optimization of Complex Systems",

address = "Switzerland",

note = "6th World Congress on Global Optimization (WCGO 2019), WCGO 2019 ; Conference date: 08-07-2019 Through 10-07-2019",

}

Jiang, R & Li, D 2020, Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming. in HAL Thi, HM Le & TP Dinh (eds), Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Advances in Intelligent Systems and Computing, vol. 991, Springer Nature Switzerland AG, pp. 213-220, 6th World Congress on Global Optimization (WCGO 2019), Metz, France, 8/07/19. https://doi.org/10.1007/978-3-030-21803-4_22

Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming. / Jiang, Rujun; Li, Duan.
Optimization of Complex Systems: Theory, Models, Algorithms and Applications. ed. / Hoai An Le Thi; Hoai Minh Le; Tao Pham Dinh. Springer Nature Switzerland AG, 2020. p. 213-220 (Advances in Intelligent Systems and Computing; Vol. 991).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming

AU - Jiang, Rujun

AU - Li, Duan

PY - 2020

Y1 - 2020

N2 - In this paper, we review recent development in semidefinite programming (SDP) based convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. QCQP problems have been well known as NP-hard nonconvex problems. We focus on convex relaxations of QCQP, which forms the base of global algorithms for solving QCQP. We review SDP relaxations, reformulation-linearization technique, SOC-RLT constraints and various other techniques based on lifting and linearization.

AB - In this paper, we review recent development in semidefinite programming (SDP) based convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. QCQP problems have been well known as NP-hard nonconvex problems. We focus on convex relaxations of QCQP, which forms the base of global algorithms for solving QCQP. We review SDP relaxations, reformulation-linearization technique, SOC-RLT constraints and various other techniques based on lifting and linearization.

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85068379620&origin=recordpage

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

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

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783030218027

T3 - Advances in Intelligent Systems and Computing

SP - 213

EP - 220

BT - Optimization of Complex Systems

A2 - Thi, Hoai An Le

A2 - Le, Hoai Minh

A2 - Dinh, Tao Pham

PB - Springer Nature Switzerland AG

T2 - 6th World Congress on Global Optimization (WCGO 2019)

Y2 - 8 July 2019 through 10 July 2019

ER -

Jiang R, Li D. Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming. In Thi HAL, Le HM, Dinh TP, editors, Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Springer Nature Switzerland AG. 2020. p. 213-220. (Advances in Intelligent Systems and Computing). Epub 2019 Jun 15. doi: 10.1007/978-3-030-21803-4_22

Semidefinite Programming Based Convex Relaxation for Nonconvex Quadratically Constrained Quadratic Programming

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this