A simultaneous diagonalization-based quadratic convex reformulation for nonconvex quadratically constrained quadratic program. (2nd September 2022)

• Record Type: Journal Article
• Authors: Zhou, Jing; Chen, Shenghong; Yu, Siying; Tian, Ye
• Is Part Of: Optimization. Volume 71:Number 9(2022)
• Page Start: 2529
• Page End: 2545
• Publication Date: 2022-09-02
• Subjects: Quadratic convex reformulation -- branch-and-bound algorithm -- quadratically constrained quadratic program -- simultaneous diagonalization; 90C30 -- 90C26; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1865347
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : This paper proposes a novel quadratic convex reformulation (QCR) for the nonconvex quadratic program with convex quadratic constraints. This new QCR is based on the technique of simultaneous diagonalization which has become one of the hottest tools in the area of quadratic programming. We first demonstrate that the 'best' QCR can be achieved by solving a Shor relaxation of the original problem. Then, we design a branch-and-bound algorithm based on the proposed QCR for obtaining the global optimal solution. Numerical experiments with extended Celis–Dennis–Tapia problem and optimal spectrum sharing problem are conducted to show that our proposed QCR well balances the bound quality and computing efficiency, hence it is very competitive with two state-of-the-art QCRs when they are executed by the same branch-and-bound scheme.