PaperlayerView exact revision on arXiv

Source-linked AI summary

General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming

Jaehyun Park, Stephen Boyd

arXiv:1703.07870v2math.OC

TL;DR

General nonconvex QCQPs lack broadly applicable specialized methods, while global approaches may be too expensive at scale. The paper introduces Suggest-and-Improve, combining candidate generation with local improvement and relaxation-based bounds, and implements these heuristics in an open-source Python package. The framework provides approximate solutions across general QCQPs, while specialized methods can outperform it on problems tailored to their structure.

  • Problem

    General nonconvex QCQPs often lack available specialized methods, while global methods have exponential running time and are unsuitable for medium- to large-scale problems.

  • Method

    Suggest-and-Improve generates candidate points, then applies local improvement methods, using relaxations to obtain candidates and lower bounds.

  • Results

    The framework generalizes multiple known methods and provides heuristics for approximate solutions to general QCQPs without specialized methods.

  • Takeaways & Limitations

    The accompanying QCQP Python package offers an accessible implementation of the paper's heuristics for NP-hard QCQPs without specialized methods.

  • Takeaways & Limitations

    The package is not intended to compete with specialized methods, which will almost certainly perform better on tailored problem classes.

Abstract

from arXiv · show

We introduce the Suggest-and-Improve framework for general nonconvex quadratically constrained quadratic programs (QCQPs). Using this framework, we generalize a number of known methods and provide heuristics to get approximate solutions to QCQPs for which no specialized methods are available. We also introduce an open-source Python package QCQP, which implements the heuristics discussed in the paper.

1 Introduction

The paper frames general nonconvex QCQPs as broadly applicable but generally difficult optimization problems, motivating polynomial-time heuristics when specialized or global methods are unavailable. Its Suggest-and-Improve framework generates candidate points and then locally improves them, while several tractable special cases and relaxations provide useful starting points or bounds.

  • Motivation: Global QCQP methods certify optimality but can require exponential time, motivating polynomial-time methods for approximate solutions.The paper targets medium- to large-scale problems without available specialized methods.
  • Problem class: General QCQPs allow arbitrary symmetric quadratic objective and constraint matrices, so the resulting optimization problem is generally nonconvex.Affine constraints, quadratic equalities, and Boolean constraints can all be represented within the framework.
  • Tractable cases: Several tractable cases include convex QCQPs, one-variable problems, interval-constrained problems, and single-constraint QCQPs.Single-constraint QCQPs remain polynomial-time solvable even when the objective and constraint are nonconvex.
  • Relaxations: Relaxations can produce candidate points or lower bounds, including a polynomial-time relaxation whose optimal value lower-bounds the QCQP optimum.Sampling from a semidefinite relaxation may yield infeasible points, but these are acceptable candidates for subsequent improvement.
  • Suggest-and-Improve: Suggest-and-Improve first finds a candidate point, then runs a local method that returns a point no worse under lexicographic constraint violation and objective value.Candidate points need not be feasible, and the framework permits randomized, parallel, and compositional methods.

2 Examples and applications

The paper shows that many optimization, combinatorial, mixed-integer, rank-constrained, and signal-recovery problems can be expressed as QCQPs. These formulations use auxiliary variables and quadratic constraints to encode higher-order products, integrality, partitions, graph structures, and application-specific relationships.

  • Polynomial optimization: Polynomial optimization problems can be converted to QCQPs by introducing variables for products and quadratic equality constraints for their definitions.A degree-d term requires at most d−1 new variables and constraints in the described construction.
  • Mixed-integer optimization: Mixed-integer quadratic programs can be represented as QCQPs by replacing integer-valued variables with nonconvex quadratic inequalities alongside box and linear constraints.The construction encodes each integer variable's allowed discrete values through quadratic constraints.
  • Rank constraints: Rank constraints Rank(X) ≤ k can be encoded with auxiliary matrices U and V and the quadratic equality X = UV.The factorization introduces pq quadratic equality constraints in the matrix entries.
  • Partitioning and graph problems: Two-way and k-way partitioning problems use Boolean or indicator variables with quadratic constraints enforcing memberships and cluster assignments.Maximum cut, graph bisection, and clique are presented as related QCQP formulations.
  • Graph applications: Maximum cut and maximum clique admit QCQP formulations using Boolean constraints, graph weights or adjacency matrices, and quadratic compatibility constraints.Maximum cut maximizes a Laplacian quadratic form, while clique constraints exclude selecting nonadjacent vertices together.
  • Applications: 3-SAT, digital-signal maximum likelihood estimation, and phase retrieval can also be formulated as quadratic feasibility or optimization problems.These formulations encode clauses, Boolean variables, linear measurements, or magnitude constraints through quadratic relations.

3 Relaxations and bounds

The section develops tractable relaxations for nonconvex QCQPs that provide bounds on the optimum and candidate points for the Suggest-and-Improve framework. Spectral, Lagrangian, and semidefinite relaxations are related, while randomized procedures and iterative constraint generation help recover feasible solutions or tighten bounds.

  • General relaxation principle: Relaxations enlarge the feasible set, yielding lower bounds for minimization problems, while feasible relaxation points can serve as starting points for local improvement.The section’s goal is to implement Suggest through tractable relaxations and obtain lower bounds on the optimal value.
  • Spectral relaxation: Spectral relaxation replaces the QCQP constraints with one aggregated quadratic constraint using nonnegative multipliers, producing a tractable problem whose optimum is a lower bound.Because every original feasible point remains feasible in the relaxation, the relaxed optimum bounds the original optimum from below.
  • Spectral relaxation: For two-way partitioning, the spectral solution uses the maximum eigenvalue and eigenvector of W, giving f_rl = nλ_max as an upper bound and sign rounding as a feasible lower-bound candidate.Thus, one eigenvalue-eigenvector computation supplies both bounds on f⋆.
  • Lagrangian relaxation: Lagrangian relaxation is equivalent to selecting the multipliers that achieve the best spectral bound, then using those multipliers to construct a spectral candidate point.Strong duality connects the Lagrangian and spectral formulations, and the resulting candidate can be passed to subsequent methods.
  • Semidefinite relaxation: Semidefinite relaxation lifts the problem by replacing X = xx^T with a semidefinite constraint, producing a lower bound; rank-one optimal solutions recover exact original solutions.The relaxation is tight when the original QCQP is convex, and affine inequalities can iteratively approximate its semidefinite constraint.
  • Semidefinite relaxation: For two-way partitioning with W ⪰ 0, randomized rounding produces feasible points with expected objective at least (2/π)f_sdr, and a few samples often exceed this bound.This gives an explicit bridge from the semidefinite bound to feasible solutions.

4 Local methods

The paper develops local methods for QCQPs, combining problem-specific feasibility heuristics with general coordinate descent and penalty CCP procedures. These methods seek feasible or improved points without guaranteeing convergence in general.

  • General limitations: The local methods are heuristic: general feasibility is NP-hard, and coordinate descent may terminate unsuccessfully rather than converge.The paper also notes that sparse quadratic data affects the cost of coefficient evaluation in coordinate updates.
  • Special cases: Problem-specific heuristics exploit structure to construct feasible points for partitioning, beamforming, and maximum-clique QCQPs.For partitioning, sign-based and ranking-based projections produce feasible points; beamforming scales a candidate until feasibility; maximum clique greedily builds a clique.
  • Special cases: The maximum-clique heuristic orders variables by decreasing value and adds a node whenever the maintained set remains a clique.The resulting clique is maximal, meaning no excluded node can be added while preserving the clique property.
  • Coordinate descent: Coordinate descent first minimizes maximum constraint violation one coordinate at a time, using one-variable QCQP solves and bisection on the violation level.Phase I ends when a feasible point is found or when no coordinate improves the maximum violation, in which case a new candidate point is needed.
  • Coordinate descent: After feasibility, coordinate descent optimizes the objective one coordinate at a time while maintaining feasibility, producing a feasible point and an upper bound on f ⋆.Phase II may stop before all improving directions are exhausted.
  • Convex-concave procedure: Penalty CCP rewrites indefinite quadratic functions as differences of convex quadratics, convexifies them iteratively, and increases a constraint-violation penalty.The method can start from an infeasible point, but its performance depends on the initial point, penalty parameters, and the chosen convex decomposition.

5 Implementation

The QCQP package extends CVXPY to recognize and process nonconvex QCQPs, exposing modular Suggest-and-Improve methods for generating candidates and improving them. A worked example demonstrates spectral initialization followed by coordinate descent reaching a feasible globally optimal solution for a small partitioning problem.

  • Package and parser: QCQP is an open-source Python package that accepts high-level QCQPs and implements the Suggest-and-Improve framework through CVXPY.The parser is extended to recognize quadratic expressions, including quadratic forms, matrix fractions, and products of affine expressions.
  • Usage: The package accepts nonconvex CVXPY problem objects even when CVXPY cannot solve them directly because of nonconcave objectives or nonconvex constraints.Users pass the problem to the QCQP constructor before invoking suggest() and improve().
  • Suggest methods: The package provides RANDOM, SPECTRAL, and SDR Suggest methods for generating candidate points and exposing corresponding spectral or SDR bounds.Suggest candidates need not be feasible and can be randomized or parallelized.
  • Improve methods: The available Improve methods are coordinate descent, penalty CCP through DCCP, and two-phase ADMM, and multiple Improve methods can be composed sequentially.Each method returns the current objective value and maximum constraint violation.
  • Example: 31.2954 matched 31.2954 for the spectral bound and n*lambda_max in the n = 10 partitioning example.Coordinate descent then produced Objective: 23.1687 and Maximum violation: 0.0000; enumeration of 1024 feasible points verified global optimality.

6 Numerical examples

The numerical examples apply Suggest-and-Improve combinations to Boolean least squares and secondary user multicast beamforming, showing that effective Suggest and Improve pairings depend on the problem. The experiments also expose feasibility and runtime trade-offs among the heuristics.

  • 6.1 Boolean least squares: All three Improve methods produced a feasible point for every candidate in the Boolean least squares experiment.The tested methods were rounding, two-phase coordinate descent, and penalty CCP.
  • 6.1 Boolean least squares: In the Boolean least squares instance, coordinate descent on SDR-based candidates found the best feasible objective value, 988, compared with the global value 920.Random rounding achieved 2719, while spectral and SDR rounding achieved 1605 and 1098, respectively.
  • 6.1 Boolean least squares: Two-phase coordinate descent found the best Boolean least squares point faster than penalty CCP and two-phase ADMM, while Gurobi required 1793 seconds to find the optimum.The reported comparison concerns this problem instance and includes the solve time of relaxations for the heuristic methods.
  • 6.2 Secondary user multicast beamforming: In the multicast beamforming instance, penalty CCP on SDR-based candidates found the best feasible objective value, 1.30, while spectral and semidefinite relaxations yielded lower bounds of 1.11 and 1.27.Penalty CCP could not produce a feasible point from the spectral-relaxation solution.
  • 6.2 Secondary user multicast beamforming: For multicast beamforming, coordinate descent performed poorly, whereas ADMM with SDR candidates reached 1.86 and penalty CCP achieved 1.30.Coordinate descent achieved 9.62 from random candidates and 2.51 from SDR candidates.
  • 6.2 Secondary user multicast beamforming: Applying ADMM followed by coordinate descent outperformed either heuristic alone, but reversing their order did not find a good feasible point.The authors present individual Improve methods as building blocks for problem-dependent sequences.

A Solving QCQP with one variable

The one-variable QCQP can be solved by representing its feasible set as disjoint intervals and minimizing the quadratic over those intervals. A balanced binary search tree supports an O(m log m) construction of the feasible set.

  • Feasible-set structure: The intersection of m constraint sets is a collection of at most m + 1 disjoint, potentially unbounded intervals.The bound follows inductively because intersecting with one additional constraint can introduce at most one interval.
  • Data structure: A balanced binary search tree maintains the disjoint feasible intervals while intersections update endpoints, remove intervals, or insert an interval when p_i < 0.Intervals are ordered by their left endpoints.
  • Complexity: The feasible set is computed in O(m log m) time because each tree operation takes O(log m), with O(m) total insertions, deletions, and modifications.The operation counts are bounded by m insertions, at most m deletions, and at most 2m modifications.
  • Objective minimization: The quadratic objective is minimized by evaluating interval endpoints and, when p_0 > 0, checking the unconstrained minimizer.This procedure applies to the resulting collection of disjoint intervals.

B Solving QCQP with one constraint

The one-constraint QCQP is transformed using an eigenvalue decomposition and, when necessary, reduced to an equality-constrained problem. The resulting Lagrangian conditions yield a scalar equation in the multiplier that can be solved numerically, with separate handling for singular cases.

  • Problem reduction: If a feasible point z already satisfies the inequality, it is optimal; otherwise complementary slackness implies that every optimum satisfies the constraint with equality.This reduces the problem to its equality-constrained version.
  • Eigenvalue transformation: An eigenvalue decomposition P = QΛQ^T transforms the problem into rotated variables ˆx, ˆz, and ˆq.The transformed variables are defined by ˆz = Q^Tz, ˆq = Q^Tq, and ˆx = Q^Tx.
  • Lagrangian method: The equality-constrained problem is handled through the Lagrangian L(ˆx, ν) = ˆx^T(I + νΛ)ˆx + (νˆq − 2ˆz)^Tˆx + νc + ∥ˆz∥^2.The multiplier ν encodes the quadratic equality constraint.
  • Positive-definite case: When I + νΛ is positive definite, minimizing the Lagrangian gives ˆx as a function of ν, and substituting it into the equality constraint produces a nonlinear scalar equation.The multiplier must remain in the range 1 + νλ_i > 0 for every i.
  • Numerical solution: The scalar equation is solved by bisection or Newton’s method because its left-hand side decreases monotonically in ν.A solution in the positive-definite range yields the corresponding ˆx.
  • Singular case: When I + νΛ is positive semidefinite and singular, there are at most two candidate multiplier values, which are checked using the KKT conditions.The resulting solution is mapped back as x⋆ = Qˆx.

C Splitting quadratic forms

The paper compares representations of an indefinite quadratic form as P+ − P−, balancing computational cost, sparsity, numerical stability, and additional curvature. It presents simple spectral choices and a difference-of-Cholesky construction with tunable robustness and sparsity trade-offs.

  • C Splitting quadratic forms: Splitting P into P+ − P− matters because convex-concave procedure performance can vary drastically with the chosen convex and concave parts.The desired representation should also address runtime, memory, numerical stability, and additional curvature.
  • C.2 Simple representations: A shifted-identity representation preserves P’s off-diagonal sparsity and is easy to compute, but can introduce substantial additional curvature when the shift is large.The shift is chosen using a bound on the magnitude of an extreme eigenvalue.
  • C.2 Simple representations: The full eigenvalue decomposition introduces no additional curvature, but costs O(n^3) time and generally produces dense P+ and P− even when P is sparse.Its positive and negative eigenvalue components preserve the norm of P.
  • C.3 Cholesky-like representations: Cholesky factorization supplies a recursive positive-definite representation with dense cost of (1/3)n^3 flops, while sparse pivoting heuristics can accelerate sparse cases.The factorization is defined for positive-definite P.
  • C.3 Cholesky-like representations: LDL decomposition exists for all symmetric matrices and avoids square roots, but 2-by-2 blocks in D cannot be directly transformed into the desired positive-semidefinite difference form.This limits a direct conversion of indefinite LDL factorizations.
  • C.4 Difference-of-Cholesky representation: The difference-of-Cholesky method handles arbitrary indefinite matrices and uses δ > 0 to prevent division by numbers with magnitude below the robustness threshold.It can also use pivoting and sparsity-promoting heuristics inherited from Cholesky methods.
  • C.4 Difference-of-Cholesky representation: The recursive difference-of-Cholesky construction targets lower-triangular L_1 and L_2 with P = L_1L_1^T − L_2L_2^T, splitting into cases based on the sign and magnitude of the leading scalar a.For a < 0, the method applies to −P and swaps the factors.
  • C.4 Difference-of-Cholesky representation: The method’s free vectors v_1 and v_2 allow trading nonzeros between L_1 and L_2, adding a sparsity choice unavailable in the other representations.Setting v_1 = 0 or v_2 = 0 gives a concrete version of this trade-off.

D Source examples

The appendix provides complete scripts and sample implementations of Suggest-and-Improve examples using the open-source QCQP package. It emphasizes close correspondence between the algorithm description and concise code.

  • Source examples: The appendix includes the full script used in §5.3 and sample implementations for the numerical examples in §6.The implementations use the open-source QCQP package.
  • Source examples: The code emphasizes similarity to Algorithm 1.1 and keeps the implementations short.

D.1 Sample usage

This example constructs a nonconvex Boolean QCQP, obtains a spectral-relaxation suggestion, improves it with coordinate descent, and compares it with an enumerated optimum.

  • The example models maximization of x^T W x subject to x_i^2 = 1 using CVXPY and QCQP.
  • The spectral heuristic solves a relaxation and reports its bound alongside n times the largest eigenvalue of W.
  • The relaxed solution is formed from the eigenvector associated with the largest eigenvalue, scaled by sqrt(n).
  • Coordinate descent then improves the suggested point while reporting the objective and maximum constraint violation.
  • Enumeration evaluates all 2^n Boolean assignments to identify the optimal objective and corresponding sign vector.

D.2 Boolean least squares

This example applies the framework to Boolean least squares by using semidefinite relaxation for initialization and coordinate descent for improvement.

  • The problem minimizes ||Ax - b||_2^2 subject to Boolean constraints x_i^2 = 1.
  • The semidefinite-relaxation heuristic supplies a starting point and reports the SDR bound.
  • Coordinate descent attempts to improve the starting point while reporting the objective value and maximum constraint violation.

D.3 Secondary user multicast beamforming

This example formulates a multicast beamforming QCQP with quadratic channel constraints, uses semidefinite relaxation for initialization, and applies ADMM for improvement.

  • The formulation uses real block matrices derived from complex channel data for intended and interfering users.
  • It minimizes the squared norm of x while requiring intended-user received power to be at least tau and interfering-user power to be at most eta.
  • Semidefinite relaxation provides a starting point for a local method and reports the SDR bound.
  • ADMM is used to improve the starting point, with rho set to sqrt(m+l), while objective value and maximum violation are reported.
Loading 1703.07870v2…