Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems

Abstract

Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for nonconvex quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. [Exploiting sparsity in semidefinite programming via matrix completion I: General framework, SIAM J. Optim. 11(3) (2001), pp. 647–674] and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP relaxation of nonconvex QCQPs. Specifically, we prove that exploiting the aggregate sparsity reduces the number of second-order cones in the SOCP relaxation, and that we can simplify the matrix completion procedure by Fukuda et al. in both primal and dual of the SOCP relaxation problem without losing the max-determinant property. For numerical experiments, nonconvex QCQPs from the lattice graph and pooling problem are tested as their SOCP relaxations provide the same optimal value as the SDP relaxations. We demonstrate that exploiting the aggregate sparsity improves the computational efficiency of the SOCP relaxation for the same objective value as the SDP relaxation, thus much larger problems can be handled by the proposed SOCP relaxation than the SDP relaxation.

Keywords:

• Quadratic constrained quadratic programming
• semidefinite programming
• second-order cone programming
• aggregate sparsity
• chordal sparsity

AMS Classifications:

• 90C20
• 90C22
• 90C25
• 90C26

Acknowledgments

This research was conducted while the first author was a research student at the Department of Mathematical and Computing Science, Tokyo Institute of Technology.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This research was partially supported by Grant-in-Aid for Scientific Research (B) [grant number 18K11176].

Notes on contributors

Heejune Sheen

Heejune Sheen is a master student at H. Milton Stewart School of Industrial Systems and Engineering, Georgia Institute of Technology. He graduated from the Korea Advanced Institute of Science and Technology (KAIST) with B.S. in Mathematics. His research interests include statistics, machine learning, conic optimization, and convex optimization.

Makoto Yamashita

Makoto Yamashita is a professor at the Department of Mathematical and Computing Science in Tokyo Institute of Technology. He received his doctoral degree in 2004 at Tokyo Institute of Technology. His research interests include conic optimization, its applications and numerical methods.