{-1，1}二次规划算法及其应用研究

论文摘要

{-1，1)二次规划是一类十分重要的整数规划问题。许多经典的组合优化问题，如最大割问题、图的最大二等分问题以及最大团等问题都是它的特例。它在大规模集成电路设计、统计物理、金融分析、多用户检测以及信号处理等实际问题中有着广泛的应用。因此，研究{-1，1}二次规划的算法及其应用具有重要的理论意义和实用价值。 {-1，1}二次规划问题是NP难问题，它不存在多项式时间的全局优化算法。本文主要研究了{-1，1}二次规划的一些近似求解算法和一些带预处理的优化算法，并把这些算法应用到多用户检测问题和离散系数的FIR数字滤波器设计问题中。主要内容如下： 1．基于{-1，1}二次规划的半定规划松弛模型，利用矩阵分解技巧和低秩分解技巧得到与半定规划松弛模型等价的非线性规划模型，提出求解该模型的序列线性规划算法和序列二次规划算法．在一定的条件下，证明了算法的全局最优性。结合随机扰动算法给出了{-1，1}二次规划的一个较好的近似解。对最大割问题和图的最大二等分问题的数值实验表明：上述算法在时间和内存的利用上要优于半定规划内点算法，尤其对于大规模的半定规划松弛问题。 2．基于{-1，1}二次规划问题的结构特性，利用{-1，1}二次规划的全局最优性必要条件，提出了一种预处理算法，该方法可以确定{-1，1}二次规划的最优解中的大部分元素的取值，把原问题等价转化为一个规模较小的二次整数规划模型。然后基于预处理算法，结合求解{-1，1}二次规划的一些有效算法，如基于半定规划的随机扰动算法，分支定界算法，互补算法，得到了求解{-1，1}二次规划问题的三种有效算法。 3．利用前面提出的基于序列二次规划的随机扰动算法、带预处理的随机扰动算法、带预处理的分支定界算法以及带预处理的互补算法研究了多用户检测问题和离散系数的FIR数字滤波器设计问题。其中带预处理的随机扰动算法和带预处理的互补算法不仅在性能上优于已有的基于半定规划的随机扰动算法，而且大大节省了CPU的计算时间。基于序列二次规划的随机扰动算法在CPU的计算时间方面要优于已存在的基于半定规划的随机扰动算法，但性能却没有多大改善。带预处理的分支定界算法在解的性能上是上述所有算法中最好的，但是CPU的计算时间较长。

论文目录

• 符号说明
• 摘要
• ABSTRACT
• 第一章 绪论与预备知识
• §1.1 组合优化问题简介
• §1.2 {-1,1}二次规划研究的现状及意义
• §1.3本文内容提要及安排
• 第二章 {-1,1}二次规划的半定规划松弛的非线性规划算法
• §2.1 半定规划简介
• §2.2 半定规划松弛模型及其随机扰动算法
• §2.3 非线性规划松弛模型
• §2.4 序列线性规划算法
• §2.5 序列二次规划算法
• §2.6 低秩分解方法
• 第三章 {-1,1}二次规划的带预处理的一些算法
• §3.1 {-1,1}二次规划的预处理算法
• §3.2 带预处理的随机扰动算法
• §3.3 带预处理的分支定界算法
• §3.4 带预处理的互补算法
• 第四章 {-1,1}二次规划在工程问题中的应用
• §4.1 码分多址中的多用户检测问题
• §4.2 离散系数的滤波器设计问题
• 第五章 约束{-1,1}二次规划的凹二次规划算法
• §5.1 引言
• §5.2 凹二次规划简介
• §5.3 约束{-1,1}二次规划的凹二次规划算法
• 结束语
• 致谢
• 参考文献
• 附录
• 在读博士期间撰写（发表）的论文
• 参加的科研项目