Source-linked AI summary
Consensus-ADMM for General Quadratically Constrained Quadratic Programming
Kejun Huang, Nicholas D. Sidiropoulos
TL;DR
General non-convex QCQPs are NP-hard, motivating methods that avoid the scalability and feasibility difficulties of standard relaxations. The paper reformulates QCQPs as consensus optimization and applies ADMM so each update becomes a QCQP-1, then evaluates the approach on engineering applications. The resulting algorithms consistently show favorable performance compared with prior methods, but convergence guarantees remain limited for this non-convex setting.
Problem
General non-convex QCQPs are NP-hard, while semidefinite relaxation can be difficult at large dimensions and may not produce feasible points.
Method
Consensus ADMM reformulates a general QCQP so each iteration requires solving multiple QCQP-1 subproblems, which can be solved optimally despite indefinite quadratic terms.
Results
The proposed algorithms consistently exhibited favorable performance compared with prior state-of-the-art methods across feasibility pursuit, multicast beamforming, and phase retrieval.
Takeaways & Limitations
The framework provides a broadly applicable approach with scalable custom implementations for non-convex QCQP applications.
Takeaways & Limitations
The algorithm is a heuristic for an NP-hard problem, and existing non-convex ADMM convergence results do not apply because the augmented Lagrangian is not monotonic in numerical experience.
Abstract
from arXiv · showhide
Non-convex quadratically constrained quadratic programming (QCQP) problems have numerous applications in signal processing, machine learning, and wireless communications, albeit the general QCQP is NP-hard, and several interesting special cases are NP-hard as well. This paper proposes a new algorithm for general QCQP. The problem is first reformulated in consensus optimization form, to which the alternating direction method of multipliers (ADMM) can be applied. The reformulation is done in such a way that each of the sub-problems is a QCQP with only one constraint (QCQP-1), which is efficiently solvable irrespective of (non-)convexity. The core components are carefully designed to make the overall algorithm more scalable, including efficient methods for solving QCQP-1, memory efficient implementation, parallel/distributed implementation, and smart initialization. The proposed algorithm is then tested in two applications: multicast beamforming and phase retrieval. The results indicate superior performance over prior state-of-the-art methods.
1 Introduction
General non-convex QCQPs are difficult and existing relaxations or restrictions have important scalability and feasibility limitations. The paper proposes consensus ADMM so each iteration decomposes into efficiently solvable single-constraint QCQPs.
- General QCQPs minimize a quadratic objective under quadratic equality or inequality constraints and are generally NP-hard.
- Semidefinite relaxation replaces X = xxH with X ⪰ xxH, producing a convex problem, a lower bound, and sometimes an exact rank-one solution.Higher-rank solutions can sometimes yield approximate feasible solutions through randomization.
- SDR becomes difficult for large dimensions because it squares the variable count, with general-purpose interior-point complexity as high as O(n^6.5).Randomization may also fail to produce a feasible point when feasibility is difficult to identify.
- Convex restriction methods preserve feasibility from a feasible initialization, but infeasible initialization can make the restricted constraint set empty.FPP-SCA addresses this by adding constraint slacks and penalizing their ℓ1 norm, though each iteration remains non-trivial to solve.
- The proposed framework uses consensus ADMM to decompose a general QCQP into m QCQP-1 subproblems, each solvable optimally despite indefinite quadratic terms.Consensus variables and scaled dual variables enable parallel auxiliary updates, while the x-update is an unconstrained quadratic minimization.
- Consensus-ADMM updates can be parallelized and made efficient through problem splitting, although the non-convex framework lacks the standard convex ADMM convergence guarantee.The paper motivates practical initialization and parameter choices because the algorithm is applied to an NP-hard problem.
2 General algorithmic framework
The paper reformulates general QCQPs for consensus-ADMM, making each auxiliary update a QCQP-1 while establishing a weaker KKT-point convergence result under stated assumptions.
- Algorithmic framework: Consensus-ADMM transforms the general QCQP into iterations whose auxiliary-variable updates are QCQP-1 problems.QCQP-1 updates remain optimally solvable even when their quadratic terms are indefinite.
- Algorithmic framework: The x-update is an unconstrained quadratic minimization requiring sufficiently large ρ when A0 is indefinite.When A0 + mρI is positive semidefinite, the update reduces to a linear system whose Cholesky factorization can be cached.
- Convergence: ADMM convergence guarantees for convex problems do not directly extend to this non-convex QCQP algorithm.The cited stronger result cannot be applied because the augmented Lagrangian is not monotonic in numerical experience, even for large ρ.
- Convergence: Under the theorem’s assumptions, every limit point of the x-iterates is a KKT point of the original QCQP.The assumptions include well-defined z-updates and the stated additional condition in the theorem.
3 Efficient zi-updates
The auxiliary QCQP-1 subproblems are solved through strong duality and eigen-decomposition, reducing the general update to a unique scalar root-finding problem.
- General QCQP-1 solution: Each z-update can be solved to optimality because QCQP-1 has strong duality, although general SDP updates are computationally undesirable.The paper therefore develops specialized numerical updates rather than relying on general-purpose SDP algorithms.
- Rank-one constraints: For rank-one constraints, the update is a projection onto an affine subspace after representing the quadratic constraint as a linear constraint with unknown phase.In the real case, the unknown phase becomes an unknown sign.
- Higher-rank constraints: For higher-rank A, eigen-decomposition transforms the QCQP-1 into diagonal coordinates and yields z̃ = (I + µΛ)^−1ζ̃.The Lagrange multiplier µ is determined by substituting this expression into the constraint.
- Higher-rank constraints: The multiplier µ is found by solving a scalar nonlinear equation whose feasible-region function is strictly decreasing and therefore has a unique solution.Bisection or Newton’s method can locate the root when the constraint set is non-empty.
- Higher-rank constraints: A QCQP-1 with p distinct eigenvalues reduces to a polynomial of degree 2p + 1, or 2p when b = 0.Orders at least five generally require numerical root-finding because closed-form expressions are unavailable.
- Bounded quadratic constraints: When A is bounded quadratically from both sides, the update effectively rounds the unconstrained point to the closest active bound.The appropriate bound is selected according to whether the unconstrained value lies above, within, or below the permitted interval.
4 Implementation issues
The implementation section addresses memory, initialization, parameter tuning, and parallelism, including a reduced-memory form and a feasibility-first initialization procedure.
- Memory-efficient implementation: The original consensus formulation can require O(mn) intermediate memory for m constraints and x ∈ C^n.This is especially problematic when constraint matrices are structured and cheap to describe.
- Memory-efficient implementation: For suitable structured rank-one constraints, the implementation reduces explicit memory from O(mn) to O(m + n).The reduced form tracks aggregate variables instead of storing every auxiliary and dual vector explicitly.
- Constraint variations: The same update framework accommodates inequality and bound constraints by modifying local and associated scalar updates while leaving the remaining updates unchanged.For a ≥ inequality, only the nonnegative part of the relevant square-root expression is retained.
- Initialization and parameter setting: The algorithm is heuristic for the generally NP-hard QCQP, making initialization and parameter tuning especially important.The penalty parameter ρ trades off objective decrease against agreement with the constraint-satisfying auxiliary variables.
- Initialization and parameter setting: A feasibility-only consensus-ADMM phase can generate an initialization, with updates independent of ρ and typically faster convergence when a feasible point exists.Repeated failure after multiple trials provides numerical evidence that the problem may be infeasible.
- Parallel and distributed implementation: Independent auxiliary updates and parallelizable matrix-vector products allow the method to achieve p-fold acceleration with p shared-memory processors.Distributed agents can aggregate local constraint contributions and communicate them to a master node for the x-update.
5 Applications and numerical experiments
The paper evaluates consensus-ADMM in QCQP applications after presenting its feasibility, implementation, and algorithmic framework, using MATLAB experiments on an eight-core desktop.
- Experimental setup: The numerical experiments apply the proposed consensus-ADMM framework to specific QCQP applications and compare it with state-of-the-art algorithms.The experiments were performed in MATLAB on a Linux desktop with 8 Intel i7 cores and 32GB of RAM.
- Feasibility applications: Consensus ADMM is presented as an alternative feasibility strategy that drives constraint-local variables toward consensus while targeting a small ℓ2-norm feasible point.This differs from FPP-SCA’s use of per-constraint slacks and an ℓ1 penalty.
- Feasibility applications: The feasibility algorithm is specified for generally Hermitian indefinite and full-rank constraint matrices in Algorithm 3.The section introduces the algorithm before application-specific numerical comparisons.
15 repeat
Experiments compare consensus-ADMM with prior methods on feasible-point pursuit and multicast beamforming, including larger-scale and interference-constrained settings. The results emphasize comparable solution quality, shorter runtimes, scalability, and simple updates.
- Feasible point pursuit: Consensus-ADMM achieves similar performance to FPP-SCA with a much shorter execution time on feasible-point pursuit problems.The algorithm uses elementary operations and simple iterations, making lower-level implementation straightforward.
- Feasible point pursuit: 8 minutes and about 104 iterations produced a feasible point with smallest norm for n = 100 and m = 200, with only about 0.45dB loss from the SDR lower bound.Finding only a feasible point required about 200 iterations, while FPP-SCA needed more than 25 minutes for a similar result.
- Single-group multicast beamforming: Multicast beamforming minimizes transmit power while guaranteeing the required SNR for every receiver.The experiments consider non-convex QCQP formulations with perfect CSI at the transmitter.
- Single-group multicast beamforming: The n = 100 multicast experiment compares consensus-ADMM against SDR randomization, SLA, and MU using SDR-gap and computation-time metrics.The evaluation averages results over 100 Monte-Carlo trials while varying the number of users from 30 to 200.
- Single-group multicast beamforming: For n = 500 and m = 100, ADMM outperforms one SLA step in transmission power and runs faster, while approaching the result of ten SLA steps.ADMM and MU use simple update rules, whereas SLA requires a full convex optimization solver.
- Secondary user multicast beamforming: With added primary-user interference constraints, ADMM and FPP-SCA both found good feasible points across the tested problem instances.The experiment used n = 100, l = 10, τ = 10, and η = 1 over 100 Monte-Carlo runs.
13 repeat
The paper applies consensus-ADMM to phase retrieval formulations under noiseless, quantized, and Gaussian-noise measurements. Experiments compare the resulting algorithms with established methods and report competitive or improved performance.
- Phase retrieval estimates a complex signal from magnitude-only linear measurements, with applications including crystallography, microscopy, and optical imaging.
- Consensus-ADMM reformulates phase retrieval constraints using auxiliary variables so each per-constraint update is a QCQP-1 solvable at optimality.The approach supports memory-efficient updates for noiseless and noisy formulations.
- Real, non-negative, and sparse signal priors can be incorporated through simple x-updates, but global optimality is not guaranteed for these NP-hard problems.Sparsity can use soft-thresholding or a tunable cardinality constraint with hard-thresholding.
- For random Gaussian measurements, consensus-ADMM has higher empirical resolution probability than Wirtinger flow and alternating minimization, with similar per-iteration complexity.The comparison uses n = 128, m ranging from 2n to 5n, common initialization, and up to 10^5 iterations over 100 Monte-Carlo trials.
- Under quantized measurements, Algorithm (16) satisfies all measurement constraints in every tested case, whereas the other two algorithms do not, despite good MSE performance.The experiment uses ε = 0.5 and averages constraint violations and MSE over 100 Monte Carlo trials.
- With additive white Gaussian noise at SNR 20dB, Algorithm (21) performs almost as well as Wirtinger flow and better than alternating minimization.The paper attributes alternating minimization's weaker result to its solving a formulation different from the maximum-likelihood formulation used here.
6 Conclusion
The paper proposes consensus ADMM for general non-convex QCQPs by reducing updates to optimally solvable QCQP-1 subproblems, with implementation choices aimed at scalability. Applications across feasibility pursuit, multicast beamforming, and phase retrieval showed favorable performance relative to prior methods.
- Any QCQP-1 can be solved optimally, irrespective of whether it is convex.
- Consensus ADMM solves general QCQPs through updates requiring multiple QCQP-1 subproblems.
- The encountered QCQP-1 subproblems can be solved very efficiently, supporting improved scalability of the overall algorithm.
- Memory-efficient implementations address certain simple constraints, including rank-one quadratics.
- Parallel and distributed implementations are designed with small communication overhead.
- Across feasibility pursuit, multicast beamforming, and phase retrieval, the proposed algorithms consistently showed favorable performance compared with prior state-of-the-art methods.
A Proof of Theorem 1
The appendix follows the ADMM iterates toward the KKT conditions of the original QCQP. For sufficiently large iterations, the update relation matches the required stationarity condition, while feasibility supplies the remaining KKT conditions.
- The proof tracks the point produced by the update rule at iteration t and analyzes the subsequent iteration.
- The argument uses the well-definedness of each z_i update to establish the next-iteration relations.
- For sufficiently large t, the derived relation provides the stationarity component needed for the KKT conditions.
- The stationarity relation becomes equation (22a) after setting µ⋆ = ρµ^(t+1).
- Feasibility of z^(t+1) guarantees the remaining KKT conditions in the proof.
B Solving (20)
The paper solves the QCQP-1 update by converting its optimality equation into a cubic equation and selecting its real optimal Lagrange-multiplier root. A condition on ρ ensures a unique real root, while smaller practical values may improve convergence.
- Equation (20) is equivalently rewritten as a cubic equation after dropping subscripts.
- The cubic roots are obtained using explicit formulas for a general cubic equation.
- With real coefficients, at least one cubic root is real, while the other roots are either complex conjugates or both real depending on the discriminant.
- The desired root is real because it represents the optimal Lagrange multiplier.
- Choosing ρ > y∥a∥² makes the discriminant condition positive and identifies the only real root as the solution.
- For multiple constraints, the sufficient condition becomes ρ > max_i y_i∥a_i∥², although smaller ρ usually gives faster convergence in practice.