Abstract
This paper develops new semidefinite programming (SDP) relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs (MBQCQP) and analyzes their approximation performance. The first class involves finding two minimum norm vectors in $N$-dimensional space such that $M$ out of $2M$ concave quadratic functions are satisfied. Using a specialized randomized rounding procedure, the authors prove that the approximation ratio is upper bounded by $\frac{54M^2}{\pi}$ in the real case and $\frac{24M}{\sqrt{\pi}}$ in the complex case. The second class, involving multi-slot scheduling with cardinality constraints, also yields approximation ratios independent of problem dimension. These results provide a solid mathematical foundation for efficient beamforming and user scheduling in wireless networks.
What Problem Does This Paper Address?
In optimization, Quadratically Constrained Quadratic Programs (QCQPs) are notoriously difficult due to their nonconvexity. The complexity increases significantly with "mixed binary" variables—where some decisions are continuous (e.g., signal power levels) and others are discrete (e.g., user assignment to time slots). These are known as MBQCQPs.
The authors focus on two specific models motivated by telecommunications:
- Joint User Grouping and Beamforming: Deciding which users to group together in two different time slots while minimizing total transmit power.
- Generalized Multi-slot Scheduling: A complex version involving multiple time slots and specific service priorities, ensuring each user is served a minimum number of times.
These problems are NP-hard. While engineers often use "relaxations" to find approximate solutions, the gap between these approximations and the true optimal solution is rarely known. This paper aims to close that gap by providing provable performance guarantees.
Methods
The authors employ a two-step strategy to tackle these problems:
- Semidefinite Relaxation (SDP): The original hard problem is transformed into a convex SDP. This involves treating binary variables as continuous values between 0 and 1 and using a "lifting" technique to replace vector products with a high-dimensional matrix, dropping the non-convex rank-1 constraint.
- Novel Randomized Rounding: Once the SDP is solved, the resulting "soft" solution is converted back into a "hard" feasible solution (actual beamforming vectors and binary assignments).
The authors propose a specific randomized procedure (illustrated above) to sample from the SDP solution and scale the results using factors $t^{(1)}$ and $t^{(2)}$ to ensure all original Quality of Service (QoS) constraints are satisfied. The mathematical core of the paper uses probabilistic analysis to determine the "approximation ratio"—the maximum possible gap between the cost of this approximate solution and the true optimal cost.
Key Insights and Ideas
- Dimension Independence: A significant finding is that the approximation bounds do not depend on $N$ (the dimension of the vectors). This is vital for "Massive MIMO" systems in 5G/6G, where the number of antennas is very large.
- The "Complex" Advantage: Theoretical bounds for complex-valued problems (representing actual radio signals) are often tighter than for real-valued problems. For Model 1, the bound scales linearly with $M$ in the complex case but quadratically ($M^2$) in the real case.
- Feasibility via Scaling: The randomized rounding isn't just about picking the closest binary value; it involves a clever scaling factor ($t$) that guarantees the final vectors meet requirements, even if the initial random sample falls short.
Key Results
The authors prove that the ratio between the approximate solution and the optimal solution is upper-bounded by:
- Model 1 (Real): $\frac{54M^2}{\pi}$
- Model 1 (Complex): $\frac{24M}{\sqrt{\pi}}$
- Model 2: Also shown to be bounded and independent of the vector dimension $N$.
Numerical experiments using synthetic data (Gaussian channel vectors) show that in practice, the approximation ratio is often very close to 1. For real-valued cases, the average ratio was typically below 3, and for complex-valued cases, it was often below 2. In many trials, the algorithm successfully found the exact optimal solution.
Limitations and Future Work
While the theoretical worst-case bounds scale with $M$ or $M^2$, empirical results are much lower. Future work could focus on tightening these mathematical bounds to better reflect real-world performance. Additionally, while SDPs are solvable in polynomial time, they can be computationally heavy for extremely large networks; exploring faster, first-order methods that maintain these guarantees is a logical next step.
Summary updated