大规模无约束{-1,1}二次规划的快速算法及其工程应用

无约束{-1,1}二次规划是组合优化领域中一个关键问题，它广泛地应用到通信工程，电子工程，图像处理等领域。本项目通过对无约束{-1,1}二次规划的数学结构的分析，利用目标函数的海塞矩阵的稀疏性，分块方法，低秩分解，谱分解以及可行域的结构，为大规模无约束{-1,1}二次规划设计快速算法。主要包括锥规划松弛算法和启发式算法。研究低秩稀疏的半定规划松弛算法和高近似界的二次锥规划松弛算法。结合数据预处理、局部搜索方法以及模拟退火方法等，设计有效的基于线性规划的启发式算法。把设计的快速算法应用到极大似然多用户检测、离散系数滤波器设计和图像分割，二值图像恢复等问题中。并且结合工程问题的优化模型结构，改进现有模型，建立新模型，应用快速算法解决大规模工程问题，通过对实际问题的仿真实验验证算法的有效性。项目的成果将推动组合优化算法的发展，拓宽组合优化在工程问题中的应用领域。

无约束{-1,1}二次规划是组合优化领域中一个关键问题，广泛地应用到通信工程，电子技术与图像处理等领域。项目分别从结构分析、算法设计以及应用方面进行了研究，成果基本符合预期。在算法设计方面，设计了大规模无约束{-1,1}二次规划的几种快速的一阶算法，效果较好。在应用研究方面，把设计的快速算法应用到多用户检测、离散系数滤波器设计以及图像处理问题中。具体成果如下：. 1. 基于无约束{-1,1}二次规划的半定规划松弛，对矩阵变量利用秩2矩阵近似，得到新的非线性规划模型，新模型降低了半定规划松弛的规模。利用可行方向法求解该模型，结合随机扰动算法，得到了问题的近似最优解。实验结果显示：秩2半定规划松弛算法与半定规划内点算法得到的近似最优解性能基本一致，但是我们算法远远少于内点算法花费的时间。. 2. 二阶锥规划松弛是无约束{-1,1}二次规划的一种较低规模的松弛方法，基于变分不等式框架，设计了二阶锥规划的几种一阶快速算法。主要成果包括：基于二阶锥规化的增广拉格朗日函数，利用可分离变量结构，提出了交替方向算法，该方法采用并行策略，降低了问题的规模。实验结果显示：我们的算法求解一些公开测试问题花费较少的计算时间；另外，基于二阶锥规划的变分不等式的等价形式，设计了一种投影收缩算法，该算法简单有效。. 3. 将多用户检测问题的{-1,1}二次规划松弛为连续优化模型，利用可行方向算法求解该模型，通过启发式算法得到原问题的近似最优解。该方法将离散问题连续化，连续松弛模型的规模远远小于半定规划松弛模型的规模。实验结果显示，该算法在时间上优于半定规划松弛算法；另外，对多用户检测问题，基于半定规划松弛模型，建立其增广拉格朗日函数，利用交替方向算法求解。该方法降低了问题的规模，在计算时间上相比内点算法有较大的优势。同时，秩2半定规划松弛和连续化松弛算法应用到离散系数滤波器设计问题。. 4. 对图像处理问题，利用基于核函数的二阶电报扩散方程和高阶扩散方程，设计对应的图像去噪算法。实验结果显示：设计的算法在图像去噪和边缘保护方面效果要优于已有的去噪和边缘保护算法。. 研究结果对大规模无约束{-1,1}二次规划算法的研究有重要的促进作用，在我国信息科学领域中具有广泛的应用前景。