Abstract
Complex Quadratic Programming (CQP) problems are fundamental to modern engineering applications such as 5G signal processing and power grid management. However, these problems are typically NP-hard due to non-convex magnitude and phase constraints. This paper proposes a novel, tighter semidefinite relaxation (SDR) by mapping these constraints into a higher-dimensional "lifted" space using polar coordinates. The resulting "Enhanced" SDR (ECSDP) significantly reduces the optimality gap in both continuous and discrete scenarios, outperforming standard relaxation methods.
Introduction
Many critical engineering challenges—including radar waveform design, wireless beamforming, and optimal power flow—are modeled as Complex Quadratic Programming (CQP). These problems involve variables with specific magnitude and phase constraints, making them notoriously difficult to solve optimally. Standard approaches rely on Semidefinite Relaxation (SDR) to create a convex approximation. However, traditional SDR often ignores crucial phase information, leading to "loose" bounds that may be far from the global optimum.
Proposed Methodology: The Power of Polar Coordinates
The authors introduce a sophisticated lifting technique that goes beyond the standard matrix representation. By introducing a secondary lifted matrix specifically for variable magnitudes and deriving valid inequalities from polar coordinate representations, they characterize the convex hull of the constraint set more precisely.
The key innovations include:
- Convex Hull Characterization: Mathematically defining the smallest convex shape containing valid points for both magnitude and phase.
- Discrete Phase Handling: Explicitly modeling "quantized" phases, which is essential for digital signal processing where phases are restricted to specific intervals.
- Enhanced ECSDP: Integrating these new constraints with a positive semidefinite constraint on the magnitude matrix to create a strictly tighter relaxation.
Experimental Evaluation
The proposed algorithm was evaluated using simulated test instances for three primary applications:
- Phase Quantized Waveform Design: Simulating radar systems with discrete phase choices.
- Discrete Transmit Beamforming: Modeling multi-antenna systems with discrete power levels.
- Continuous Phase Angle Constraints: General non-convex problems with phase intervals.
Key Results
Using the "Gap Closed" metric, the authors demonstrated significant improvements:
- Radar Waveform Design: For 3-bit quantization, the method closed the optimality gap by 50% to 90% compared to standard SDR.
- Beamforming: The relaxation gap was reduced by 9.7% to 31.5% across various antenna configurations.
- Global Optimality: For continuous problems, the new bounds were often twice as close to the true maximum as standard methods.
Key Insights
- Geometry Matters: Defining tight boundaries is more effective in polar coordinates ($magnitude \times angle$) than in standard real/imaginary components.
- Bridging the Gap: Linking the complex matrix and the magnitude matrix through linear and second-order cone constraints prevents the relaxation from including "impossible" solutions.
- Generality: Unlike previous methods limited to small phase windows, this approach supports the full 360-degree circle and discrete points.
Conclusion and Future Work
While the Enhanced SDR provides significantly tighter bounds, it comes with increased computational complexity due to additional variables and constraints. Future research may focus on improving the scalability for large-scale systems or proving theoretical approximation ratios. Given its tightness, this relaxation is a prime candidate for integration into Branch-and-Bound algorithms to find exact global optima for complex problems like Optimal Power Flow.
Summary updated