ON THE RELAXATION COMPLEXITY OF NONCONVEX QUADRATIC GLOBAL OPTIMIZATION

Tongli Zhang; Yong Xia

doi:10.23952/cot.2024.19

ON THE RELAXATION COMPLEXITY OF NONCONVEX QUADRATIC GLOBAL OPTIMIZATION

Tongli Zhang
, Yong Xia^*

^*此作品的通讯作者

数学科学学院

Nanjing Institute of Technology
Beihang University

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

We study the relaxation complexity for nonconvex quadratic global optimization, which is defined as the number of convex relaxation subproblems to be solved. The relaxation complexity for quadratic programming with fixed nonconvex-rank is known to be a polynomial function of the dimension. In this paper, we show that the relaxation complexity for nonconvex quadratic optimization with convex quadratic constraints may not depend on the dimension, as long as the objective function has a fixed nonconvex rank.

源语言	英语
文章编号	19
期刊	Communications in Optimization Theory
卷	2024
DOI	https://doi.org/10.23952/cot.2024.19
出版状态	已出版 - 2024

访问文件

10.23952/cot.2024.19

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{f13681cd5d9d45db874a52987d4090f1,

title = "ON THE RELAXATION COMPLEXITY OF NONCONVEX QUADRATIC GLOBAL OPTIMIZATION",

abstract = "We study the relaxation complexity for nonconvex quadratic global optimization, which is defined as the number of convex relaxation subproblems to be solved. The relaxation complexity for quadratic programming with fixed nonconvex-rank is known to be a polynomial function of the dimension. In this paper, we show that the relaxation complexity for nonconvex quadratic optimization with convex quadratic constraints may not depend on the dimension, as long as the objective function has a fixed nonconvex rank.",

keywords = "Dikin ellipsoid, Global optimization, L{\"o}wner-John ellipsoid, Quadratic constrained quadratic optimization",

author = "Tongli Zhang and Yong Xia",

note = "Publisher Copyright: {\textcopyright} 2024 Communications in Optimization Theory.",

year = "2024",

doi = "10.23952/cot.2024.19",

language = "英语",

volume = "2024",

journal = "Communications in Optimization Theory",

issn = "2051-2953",

publisher = "Mathematical Research Press",

}

TY - JOUR

T1 - ON THE RELAXATION COMPLEXITY OF NONCONVEX QUADRATIC GLOBAL OPTIMIZATION

AU - Zhang, Tongli

AU - Xia, Yong

PY - 2024

Y1 - 2024

N2 - We study the relaxation complexity for nonconvex quadratic global optimization, which is defined as the number of convex relaxation subproblems to be solved. The relaxation complexity for quadratic programming with fixed nonconvex-rank is known to be a polynomial function of the dimension. In this paper, we show that the relaxation complexity for nonconvex quadratic optimization with convex quadratic constraints may not depend on the dimension, as long as the objective function has a fixed nonconvex rank.

AB - We study the relaxation complexity for nonconvex quadratic global optimization, which is defined as the number of convex relaxation subproblems to be solved. The relaxation complexity for quadratic programming with fixed nonconvex-rank is known to be a polynomial function of the dimension. In this paper, we show that the relaxation complexity for nonconvex quadratic optimization with convex quadratic constraints may not depend on the dimension, as long as the objective function has a fixed nonconvex rank.

KW - Dikin ellipsoid

KW - Global optimization

KW - Löwner-John ellipsoid

KW - Quadratic constrained quadratic optimization

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

U2 - 10.23952/cot.2024.19

DO - 10.23952/cot.2024.19

M3 - 文章

AN - SCOPUS:105020071174

SN - 2051-2953

VL - 2024

JO - Communications in Optimization Theory

JF - Communications in Optimization Theory

M1 - 19

ER -

ON THE RELAXATION COMPLEXITY OF NONCONVEX QUADRATIC GLOBAL OPTIMIZATION

摘要

访问文件

其它文件与链接

指纹

引用此