Consensus-ADMM for General Quadratically Constrained Quadratic Programming
From MaRDI portal
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.
Cited in
(21)- ADMM for the SDP relaxation of the QAP
- A distributed algorithm for high-dimension convex quadratically constrained quadratic programs
- Lopsided shift-splitting preconditioner for saddle point problems with three-by-three structure
- A hybrid algorithm for the two-trust-region subproblem
- Nonlinear set membership filter with state estimation constraints via consensus-ADMM
- Quantized Consensus by the ADMM: Probabilistic Versus Deterministic Quantizers
- A general system for heuristic minimization of convex functions over non-convex sets
- Modification of gesture-determined-dynamic function with consideration of margins for motion planning of humanoid robots
- A simple effective heuristic for embedded mixed-integer quadratic programming
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation
- A linear-time algorithm for generalized trust region subproblems
- Positive semidefinite interval of matrix pencil and its applications to the generalized trust region subproblems
- Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
- Efficient min–max MPC: Achieving a large domain of attraction with short horizon
- An efficient splitting algorithm for solving the CDT subproblem
- An Adaptive Sampling Strategy for Real-Time Anomaly Detection with Unmanned Sensing Vehicles
- Nonlinear optimization via novel neural network methods
- New notions of simultaneous diagonalizability of quadratic forms with applications to QCQPs
- Stability analysis of a system of systems controlled via MPC and consensus ADMM for a generic consensus horizon
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
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)
