论文部分内容阅读
优化是应用数学,计算科学和运筹学交叉产生的一门年轻学科。它在最新几十年正以惊人的速度渗透到工程、医学、经济、管理以及军事等许多学科。算法设计和实现技巧的研究既是优化这个学科本身不可或缺的一部分,又在将优化技术应用于其它学科的过程中扮演了重要的角色。本篇博士论文,主要研究非线性优化算法的设计和应用。
第一部分是关于一般约束的非线性优化问题。在第二章中提出了一个新的信赖域算法。算法迭代的每一步通过求解增广Lagrangian函数在信赖域内的极小来得到试探步。然后首先使用增广Lagrangian函数判断是否接受试探点。新算法与原有的信赖域算法的一个主要区别是,当试探点不能被评价函数所接受时,filter被做第二个评价标准用于进行再次判断。使用积极集法将算法扩展到可以处理带有不等式约束的情形。通过CUTEr题库中一组测试题目的数值实验,将新算法与著名的软件LANCELOT进行了比较,计算结果验证了新算法的正确性和有效性。
第二部分是将非线性优化算法技巧用于混合整数非线性规划。针对一个来源于矿山开采计划的实际问题,研究了如何将非线性优化算法的技巧应用到求解混合整数非线性规划中。该问题中含有的唯一非线性约束条件是关于连续变量的双线性约束。这种约束反映了元素在混合前后物质中比例相同的特性。文献[12]提出了一个求解这个混合整数非线性规划问题的分枝定界方法。然而这个方法主要是针对整数变量设计的,对于处理连续变量的非线性约束并不有效。因此,对于预处理后的非线性子问题提出了一个启发式的算法。并同时给出了分段线性化的技巧来估计解的质量。实验是通过NESO调用目前最好的非线性优化求解器filterQP和IPOPT实现的。为了能够使用非商业的软件在本地求解整个问题,为目前世界上最快的非商业混合整数线性规划求解软件SCIP添加了首个非线性句柄一多项式句柄。著名的开源软件IPOPT被选做句柄中的非线性求解器。
第三部分,考虑为机器学习和数据挖掘中产生的非线性优化问题设计特殊的算法。目标是利用问题的特殊结构,设计出快速高效的算法。因此,对于不同的向量机模型考虑了不同的方法。
第四部分,在综述了求解C—支持向量机的分解算法之后,介绍了自己开发的面向对象的支持向量机求解器—OOSVM。与以往的求解器不同,OOSVM从优化算法的角度进行了模块化的设计。一方面,力求在当前的版本中包含尽量多的算法模块。另一方面,也提供了可扩展的接口,方便用户实现自己的新算法。虽然OOSVM是针对C—支持向量机设计的,但是它其中包含的设计思想和实现技巧,对于设计其它向量机的训练方法也具有启发的作用。
第五部分,讨论了训练边界支持向量机的分解算法。与上一章不同,这一章侧重于工作集选取方案的设计和相应分解算法的全局收敛性分析。提出了首个在非SMO算法中,使用部分二阶信息选取工作集的方案。同时,为了提高训练效率,建议联合使用投影梯度算法和内点法求解二次规划子问题,这种混合算法比以往的方法更加注重子问题的特点。新算法在对公共数据集上测试问题的数值实验获得了良好的数值表现结果
第六部分,提出了一个针对Crammer和Singer多类核学习机模型的并行分解算法。给出了新的工作集选取方案,并证明了基于该方案的分解算法的全局收敛性。投影梯度算法用来求解每步迭代所产生的二次规划子问题,为了使得投影梯度算法高效,针对子问题约束条件的结构特点,专门设计了特殊的投影点计算方案。并行技巧被用于开发多处理器系统上的存储和计算资源。数值实验结果显示了新算法能够在达到高分类准确度的同时,大幅度的节省训练时间。
最后讨论了临近支持向量机的训练算法。通过巧妙的重排计算公式,可以将使用一对其它技巧处理多类分类问题的计算代价降到与训练一个同等规模的两类临近支持向量机的代价基本相同。低秩分解的技术被用于处理训练集中含有大量样本点的问题。同时给出定理估计低秩分解近似解的误差,并据此设计了实际迭代过程中,低秩分解的终止条件。为了克服不平均数据造成的困难并提高临近支持向量机的分类表现,还提出了一种后处理的技巧。将新算法进行了并行实现以提高计算效率和处理大规模的问题,程序采用标准的MH接口实现进程间通信。数值实验结果表明,算法对于处理适合于线性核的分类问题十分有效。