大规模非线性优化问题的并行算法及应用研究

目前，大部分优化算法，包括人们熟知的序列二次规划算法和序列线性方程组算法等，在解决如支持向量机等大规模或超大规模优化问题时，都因计算时间过长、计算误差积累，难以达到实际应用的目的，解决该困难的一个方向，是研究适合高速并行计算机或机群系统的优化算法。本课题主要研究大规模优化问题的并行算法及其在支持向量机等模型求解中的应用。首先研究无约束问题的高效并行变量分布和并行变量转换等新算法，分析其全局收敛性质及并行效率；其次研究特殊约束问题的并行序列二次规划和序列线性方程组算法，试图获得全局并行、子问题高效求解的算法；第三个内容是利用约束剖分技术，研究带一般约束的非线性优化问题的并行算法；第四个内容是将相应的并行优化新算法进行特殊化，应用于支持向量机等超大规模问题的求解；最后，将建立大规模优化问题和并行优化问题的数值测试平台，进行大量数值实验，验证并改进所提出的各种新算法的有效性。

本项目的主要研究内容是求解大规模优化问题的并行算法及其在支持向量机等模型求解中的应用。首先研究了无约束问题的高效并行变量分布和并行约束转换等新算法，使每步下降量加大，并证明了算法具有全局收敛性且收敛比与处理器个数无关；其次，对于特殊约束问题，提出了高效并行的序列二次规划（SQP）和序列线性方程组（SSLE）算法，在子问题的构造方面，充分考虑同步或异步、局部下降和全局收敛的关系，使算法子问题求解的工作量减少，整体快速收敛。最后，对一般约束的非线性优化问题，将约束剖分概念引入并行优化算法的设计，提出了一般约束情况下新的并行算法，并用SSLE等方法解决子问题求解，在适当条件下证明了算法的收敛性。同时，以一般约束优化问题并行算法的研究工作为基础，本课题组成员对超大规模支持向量机问题的求解进行了深入研究，利用支持向量机模型的特殊结构，通过对支持向量机进行算法层次的并行化处理，获得了较为有效的并行算法，使得支持向量机的求解既能快速进行，又有理论保障。对支持向量机模型的分解算法及分布式算法进行了研究，并对基于支持向量机模型的界约束优化问题的求解算法进行研究，得到若干成果。此外，本课题组还对隐私保护支持向量机问题及支持向量机的应用作了较多研究工作；开展了网络机群环境下并行算法的实现研究，初步构建了并行优化方法的数值测试平台。对二阶锥优化及互补问题的求解方法进行研究，获得了一系列具有全局收敛性和局部超线性收敛速度的有效算法，并通过数值试验验证了算法的有效性。