Consensus-ADMM for General Quadratically Constrained Quadratic Programming
From MaRDI portal
Publication:4620983
DOI10.1109/TSP.2016.2593681zbMATH Open1414.90256arXiv1601.02335MaRDI QIDQ4620983FDOQ4620983
Kejun Huang, Nicholas D. Sidiropoulos
Publication date: 8 February 2019
Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1601.02335
Cited In (18)
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
- A hybrid algorithm for the two-trust-region subproblem
- An efficient splitting algorithm for solving the CDT subproblem
- Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
- Quantized Consensus by the ADMM: Probabilistic Versus Deterministic Quantizers
- A general system for heuristic minimization of convex functions over non-convex sets
- Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem
- Efficient min–max MPC: Achieving a large domain of attraction with short horizon
- A simple effective heuristic for embedded mixed-integer quadratic programming
- A Linear-Time Algorithm for Generalized Trust Region Subproblems
- Nonlinear set membership filter with state estimation constraints via consensus-ADMM
- Lopsided shift-splitting preconditioner for saddle point problems with three-by-three structure
- A distributed algorithm for high-dimension convex quadratically constrained quadratic programs
- Positive semidefinite interval of matrix pencil and its applications to the generalized trust region subproblems
- An Adaptive Sampling Strategy for Real-Time Anomaly Detection with Unmanned Sensing Vehicles
- ADMM for the SDP relaxation of the QAP
- Modification of gesture-determined-dynamic function with consideration of margins for motion planning of humanoid robots
- An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation
This page was built for publication: Consensus-ADMM for General Quadratically Constrained Quadratic Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620983)
