Technical Summary: Joint-Range Inequalities for Nonconvex QCQPs

Problem Statement

The paper addresses the challenge of generating effective cutting planes for nonconvex Quadratically Constrained Quadratic Programs (QCQPs), a core class of problems in Mixed-Integer Nonlinear Programming (MINLP). While standard relaxations like Reformulation-Linearization-Technique (RLT) and Semidefinite Programming (SDP) relaxations (e.g., Shor's relaxation) provide convex approximations, they often suffer from a trade-off between tightness and sparsity. Specifically, eigenvalue reformulations and dense SDP constraints typically destroy the sparsity of the original problem, leading to computationally expensive cuts that are difficult to integrate into MINLP solvers. The authors seek a framework to derive strong, valid inequalities that preserve the sparsity of the underlying QCQP formulation while exploiting nonconvex geometry.

Methodology: Project-Then-Lift Approach

The authors propose a "project-then-lift" strategy inspired by Mixed-Integer Rounding (MIR) inequalities used in Mixed-Integer Linear Programming (MILP). The methodology proceeds as follows:

1. Base Inequalities and Projection:
   Starting from two base valid inequalities for the extended QCQP formulation (involving variables $x$ and lifted matrix $X$), the authors define an affine map $A_{JR}$ that projects these inequalities into a two-dimensional image space. Let the base inequalities be $\phi_i + \langle \Theta_i, X \rangle + \theta_i^\top x \geq 0$ for $i=1,2$. The projection maps feasible $(X, x)$ pairs to a vector $y = (y_1, y_2)$ where $y_i$ corresponds to the left-hand side of the $i$-th inequality.

2. Joint Range Analysis:
   The core of the method analyzes the joint range $F(\mathbb{R}^n)$ of the two quadratic functions $f_1(x)$ and $f_2(x)$ associated with the base inequalities. The set of feasible projected points is the intersection of this joint range with a simplicial cone $K_{JR}$ defined by the base inequalities.

   • Nonconvex Case: The authors characterize the closed convex hull of the joint range when it is nonconvex. They show that under specific conditions (linear dependence of quadratic parts), the joint range takes an explicit nonconvex form, such as the boundary or exterior of a parabolic bowl.
   • Convex Case: When the joint range is convex, they provide a Semidefinite Programming (SDP) representation.

3. Hull Characterization and Inequality Derivation:
   The authors derive a closed-form description of the convex hull of the projected set ($H_{JR} = \text{cl}(\text{conv}(F(\mathbb{R}^n) \cap K_{JR}))$).

   • For nonconvex cases, the hull is described by intersecting the simplicial cone with the parabolic bowl or its complement, often resulting in "secant" cuts (intersection cuts) defined by the points where the cone's rays exit the nonconvex set.
   • For convex cases, the hull is described via support functions, leading to an SDP-constrained separation problem.

4. Lifting and Sparsity Preservation:
   The valid inequalities derived in the 2D image space are lifted back to the original $(X, x)$ space using the inverse of the affine map. Crucially, because the projection is based on only two base inequalities, the resulting lifted inequalities inherit the sparsity (support) of those base inequalities. This avoids the density issues associated with full SDP relaxations.

5. Secant Mixed-Joint-Range Inequalities:
   Extending the MIR concept, the authors introduce "secant mixed-joint-range inequalities." These involve extracting "mixed" terms (fractional linear combinations or continuous variables) from the base inequalities to form a core pair that satisfies the nonconvex parabolic conditions. This allows the method to handle more complex structures similar to how MIR handles fractional terms in MILP.

Key Contributions

• Closed-Form Convex Hulls: The paper provides a complete, closed-form characterization of the convex hull for the intersection of a simplicial cone and a nonconvex joint range of two quadratic functions. This includes explicit geometric descriptions for various configurations (e.g., apex inside/outside the parabolic bowl, recession rays).
• New Cut Families: The authors introduce joint-range inequalities and secant mixed-joint-range inequalities. These are valid for the extended QCQP formulation and are derived via intersection cuts in the projected 2D space.
• Sparsity Preservation: Unlike standard SDP-based cuts, the proposed inequalities are sparse. The support of each lifted inequality is strictly controlled by the support of the two base inequalities used to generate it.
• SDP Representation for Convex Cases: For convex joint ranges, the authors provide a semidefinite representation that offers a sparse route to linearize Shor's SDP relaxation.
• Algorithmic Classification: An algorithm is presented to classify the joint range as convex or nonconvex and to determine its specific geometric shape (e.g., parabolic boundary, solid region, or punctured plane).

Results

The paper reports preliminary geometric experiments comparing the strength of the proposed joint-range inequalities against the standard first-level RLT relaxation.

• Metric: The strength is measured by the ratio of the area of the intersection between the projected RLT relaxation and the joint-range hull to the area of the projected RLT relaxation alone. A lower ratio indicates a stronger cut (greater area reduction).
• Findings:
  • In "unclipped" cases where the joint range is entirely contained within the cone, the cuts provide no additional reduction (ratio = 1).
  • In non-trivial nonconvex cases (e.g., "Chord-Truncated Bowl" and "Ray-Truncated Bowl"), the joint-range hull significantly reduces the projected area. The shifted geometric mean of the area ratio ranged from approximately 0.108 to 0.490 across different dimensions and configurations.
  • The convex joint-range cases (Case 7) also demonstrated substantial area reduction (ratios between 0.219 and 0.403).
  • The results suggest that the proposed approach can substantially tighten the projected relaxation constructed via RLT.

Significance and Claims

The authors claim that this work bridges the gap between the geometric strength of intersection cuts and the computational necessity of sparsity in MINLP solvers.

• Separation of Geometry and Dimension: The primary significance is the decoupling of the difficult geometric step (handling nonconvexity) from the ambient dimension. The complex geometry is resolved in a low-dimensional (2D) space where closed-form solutions exist, while the final cuts remain sparse in the high-dimensional original space.
• Exploitation of Nonconvexity: The framework explicitly exposes and exploits nonconvex joint ranges, which are inaccessible to approaches relying solely on "hidden convexity" (like the S-lemma) or standard convex relaxations.
• Generalization of MIR: The approach generalizes the successful project-then-lift paradigm of MIR inequalities to the nonlinear QCQP domain, offering a mechanism to generate strong cuts without requiring dense matrix constraints.
• Future Directions: The authors modestly note that a systematic study within a full MINLP solver is beyond the current scope. They identify the automation of selecting effective base inequality pairs as a primary direction for future research, suggesting that heuristics similar to those used for MIR separation could be adapted to "align" quadratic coefficients to induce the necessary nonconvex geometry.