复变量二次规划问题的全局优化方法研究

Complex quadratic programming problems have a series of applications in signal processing and power system. Many typical nonconvex problems among them are known to be NP-Hard. Different from conventional real quadratic programming problems, complex problems have many new structures. Most global optimization algorithms in the literature are more suitable for solving real problems, but are not able to be extended to solve complex problems in an effective manner. This proposal will study global optimization methods for complex quadratic programming problems. By exploiting typical structures in complex problems, we propose two types of efficient branch-and-bound algorithms, including polar coordinate based branch-and-bound algorithms, and key-eigen-direction based branch-and-bound algorithms. Meanwhile, we further exploit the sparse structures in certain types of problems to improve the efficiency of the proposed branch-and-bound algorithms. Finally, the proposed branch-and-bound algorithms will be applied to solve some typical nonconvex complex quadratic programming problems arisen in signal processing and power system, including certain types of beamforming problems, phase synchronization problems, radar signal processing problems, and optimal power flow problems, to provide effective global optimization methods for these application problems.

复变量二次规划问题在信号处理和电力系统中具有广泛应用，其中很多典型的非凸问题情形已经被证明是NP-Hard的。不同于传统实变量二次规划问题，复变量问题具有新的结构。然而，文献中现有的全局优化算法普遍适用于求解实变量问题情形，这些算法很难有效扩展到复变量问题情形。本项目拟对复变量二次规划问题的全局优化方法进行系统研究。通过挖掘复变量问题的典型结构特点，提出两类有效的分支定界算法：基于极坐标表示的分支定界算法和基于关键特征方向的分支定界算法。与此同时，通过对问题中常见的稀疏结构及其性质进行深入探索，进一步改进分支定界算法效率。最后，本项目拟将上述分支定界算法应用于求解信号处理和电力系统中的典型非凸复变量二次规划问题，包括几类具体的波束成形问题，相位同步问题，雷达信号处理问题，最优潮流计算问题，从而为相关应用问题提供有效的全局优化求解方案。

复变量二次优化问题在信号处理、电力系统领域具有广泛的应用。在本项目中，我们系统地研究了非凸复变量二次优化问题的全局优化理论与方法，并且完成了原计划的科研目标。我们提出了多种有效的全局优化算法，用于求解不同类型的重要的非凸二次优化问题，包括基于变量极坐标表示的分支定界算法，基于关键敏感特征方向的全局优化算法。此外，针对多输入多输出信道检测问题，我们提出了一类新的改进的半正定松弛方法，并从理论上分析了该松弛方法的紧性。我们还针对电力系统领域中的一类混合整数二次规划问题提出了改进的凸松弛方法。将该方法进一步嵌入到分支定界框架下，所得到的算法效率远远高于求解该类问题的经典算法。上述工作为信号处理及电力系统领域中的二次优化问题提供了新的求解方法。特别地，我们在多输入多输出信道检测问题中得到的一些研究成果在通信系统中具有潜在应用。