Consensus-ADMM for General Quadratically Constrained Quadratic Programming

Abstract

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.

References in corpus (4)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Feasible Point Pursuit and Successive Approximation of Non-convex QCQPs
• Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
• Phase Retrieval Using Feasible Point Pursuit: Algorithms and Cramér-Rao Bound

Cited by in corpus (25)

• Signal Processing for High Throughput Satellite Systems: Challenges in New Interference-Limited Scenarios
• NeutRAN: An Open RAN Neutral Host Architecture for Zero-Touch RAN and Spectrum Sharing
• A Fair and Privacy-Aware EV Discharging Strategy using Decentralized Whale Optimization Algorithm for Minimizing Cost of EVs and the EV Aggregator
• A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
• Amplitude Retrieval for Channel Estimation of MIMO Systems with One-Bit ADCs
• Large-Scale Fading Precoding for Spatially Correlated Rician Fading with Phase Shifts
• Super-Resolution mmWave Channel Estimation using Atomic Norm Minimization
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems
• Reconfigurable Intelligent Surface Aided Constant-Envelope Wireless Power Transfer
• Pilot Spoofing Attack by Multiple Eavesdroppers
• Estimating Cellular Goals from High-Dimensional Biological Data
• Second-order Conic Programming Approach for Wasserstein Distributionally Robust Two-stage Linear Programs
• Consensus-based Distributed Discrete Optimal Transport for Decentralized Resource Matching
• Modification of Gesture-Determined-Dynamic Function with Consideration of Margins for Motion Planning of Humanoid Robots
• New notions of simultaneous diagonalizability of quadratic forms with applications to QCQPs
• OPARC: Optimal and Precise Array Response Control Algorithm -- Part II: Multi-points and Applications
• Massive MIMO Multicast Beamforming Via Accelerated Random Coordinate Descent
• Delay and Power Tradeoff with Consideration of Caching Capabilities in Dense Wireless Networks
• On local minimizers of generalized trust-region subproblem
• Robust Beamforming for Enhancing Security in Multibeam Satellite Systems
• ADMM-based Fast Algorithm for Multi-group Multicast Beamforming in Large-Scale Wireless Systems
• A Distributed Algorithm for High-Dimension Convex Quadratically Constrained Quadratic Programs
• Managing Randomization in the Multi-Block Alternating Direction Method of Multipliers for Quadratic Optimization
• Joint Spatial Division and Diversity for Massive MIMO Systems
• A linear-time algorithm for generalized trust region subproblems