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

Heejune Sheen, Makoto YamashitaOptim. Methods Softw 2022 · OpenReview

Abstract

Quadratic Constrained Quadratic Programming (QCQP) is a fundamental yet computationally challenging class of optimization problems. While Semidefinite Programming (SDP) relaxations offer high accuracy, they often fail to scale to large-scale instances due to memory and time constraints. This paper proposes a highly efficient method for solving QCQPs by exploiting "aggregate sparsity" within Second-Order Cone Programming (SOCP) relaxations. By demonstrating that SOCP relaxations do not require the complex chordal extensions or additional consistency constraints typical of sparse SDP approaches, the authors achieve computational speedups of up to four orders of magnitude. The method is particularly effective for large-scale problems where traditional relaxations encounter memory limits.

Introduction

Quadratic Constrained Quadratic Programming (QCQP) serves as a critical framework for modeling complex systems in fields ranging from radar detection to power systems engineering. However, when these problems are non-convex, they are generally NP-hard, necessitating the use of convex relaxations to find approximate solutions.

The "gold standard" for such approximations has long been the Semidefinite Programming (SDP) relaxation. While SDP provides high-quality bounds, its computational cost and memory requirements grow quadratically with the number of variables, making it impractical for large-scale datasets. Second-Order Cone Programming (SOCP) relaxations offer a lighter alternative; however, they are traditionally viewed as "weaker" (less accurate) and have not been fully optimized to exploit the inherent sparsity of modern optimization problems. This paper bridges that gap, presenting a framework that makes SOCP relaxations both significantly faster and capable of handling much larger problem instances than previously possible.

Methodology: Exploiting Aggregate Sparsity

The core of the proposed approach lies in the exploitation of aggregate sparsity—the combined pattern of non-zero entries across all data matrices within a QCQP. The authors introduce three key innovations that differentiate their SOCP approach from traditional sparse SDP methods:

1. Sparsity Exploitation without Chordal Extension

In sparse SDP relaxations, researchers typically rely on "chordal extensions" (adding edges to a graph to facilitate decomposition) and "consistency constraints" to ensure that overlapping sub-matrices remain synchronized. The authors prove that for SOCP relaxations, these steps are mathematically redundant. One can exploit the raw aggregate sparsity pattern directly, greatly simplifying the problem structure.

2. Reduced Cone Count

By focusing exclusively on the non-zero entries defined by the aggregate sparsity pattern, the method significantly reduces the number of second-order cones required. This reduction directly translates to lower memory consumption and faster solver iterations.

3. Simplified Matrix Completion

The paper establishes a "maximum determinant" property for SOCP. They demonstrate that an optimal solution consistent with the original problem can be recovered through a simple procedure: filling missing entries with zeros. This avoids the recursive, clique-based completion algorithms required in the SDP context.

Experimental Setup

The effectiveness of the sparse SOCP method was evaluated using two distinct test suites:

  • Lattice Graphs: Synthetic QCQP instances based on grid-like structures. These were used to measure how the algorithm scales as the dimensionality ($n$) and the number of constraints ($m$) increase.
  • The Pooling Problem: A standard non-convex optimization benchmark from the chemical and petroleum industries. The authors tested 10 specific instances where SOCP relaxations are known to provide the same accuracy as SDP relaxations.

Key Results

Computational Speedups

The most striking result was observed in the lattice graph experiments. For a problem size of $n = 169^2$, a standard "Full" SOCP relaxation required 15,397 seconds (over 4 hours) to solve. In contrast, the "Sparse" SOCP approach completed the same task in just 1.71 seconds. This represents a speedup of approximately 9,000x.

Memory Efficiency

In the pooling problem benchmarks, both the SDP relaxation and the Full SOCP relaxation frequently triggered "Out of Memory" (OOM) errors on larger instances. The Sparse SOCP method solved all instances successfully. Even in cases where memory was not a limiting factor, the sparse approach was consistently 3 to 6 times faster than the full relaxation.

Accuracy Preservation

Numerical results confirmed the theoretical proofs: the sparse SOCP relaxation attains the exact same objective value as the full SOCP relaxation. This ensures that the massive gains in speed do not come at the cost of solution quality relative to the standard SOCP baseline.

Discussion and Future Work

While the proposed method offers dramatic performance improvements, it is important to note the "relaxation gap." SOCP is generally a weaker relaxation than SDP for arbitrary QCQPs. Therefore, this method is most impactful for specific problem classes—such as those with non-positive off-diagonal elements—where SOCP and SDP values are guaranteed to coincide.

Future research will explore applying these sparsity-exploitation techniques to higher-level relaxations, such as the SDSOS (Scaled Diagonally Dominant Sum-of-Squares) hierarchy. This could provide a middle ground, offering more accuracy than SOCP while maintaining a significant speed advantage over full SDP. Additionally, the authors aim to extend these techniques to general polynomial optimization problems.

Summary updated

BibTeX
@inproceedings{sheen2022exploiting,
  author = {Heejune Sheen and Makoto Yamashita},
  title = {{Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems}},
  booktitle = {Optim. Methods Softw},
  year = {2022},
  url = {https://openreview.net/forum?id=EV5hyP60Qw},
}
Figure