Full Text: PDF
DOI: 10.23952/cot.2024.19
Received July 2, 2023; Accepted October 2, 2023; Published online January 30, 2024
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.
How to Cite this Article:
T. Zhang, Y. Xia, On the relaxation complexity of nonconvex quadratic global optimization, Commun. Optim. Theory 2024 (2024) 19.