几类优化问题的算法及应用研究

论文摘要

最优化广泛应用于工程设计、生产管理、交通运输和政府决策等重要领域,因此优化问题的求解算法成为备受关注的研究课题.二阶锥规划是一类十分重要的非光滑凸规划问题,它宽广的应用范围、特殊的锥结构和方便的计算性,使其具有独立的研究价值,而且许多优化问题都可以转化为二阶锥规划来求解.二阶锥互补问题是二阶锥规划的推广,包括线性和非线性二阶锥互补问题.同样,变分不等式与互补问题也是当今优化问题的重要研究领域.本文主要围绕上述几类优化热点问题的求解算法以及互补问题在支持向量机中的应用进行研究,得到的主要成果如下：（1）对二阶锥规划问题的求解算法进行了研究.首先,针对线性二阶锥规划问题提出了两个求解算法：其一,给出了一个求解线性二阶锥规划问题的预估校正光滑牛顿算法,算法产生的迭代序列不需要额外的计算,而能保持在一个给定的邻域内.算法具有全局收敛性和局部二次收敛性质.其二,提出一个求解线性二阶锥规划问题的半光滑非精确牛顿算法,在算法执行过程中,非精确搜索方向允许有适度误差,从而节省了计算时间和内存.该算法是全局收敛和局部超线性收敛的.然后,给出了一个求解非线性二阶锥规划问题的SQP信赖域筛选算法,该算法避免了一般SQP类算法中使用传统的具有惩罚项的价值函数.在适当假设条件下,算法被证明具有全局收敛性质.（2）研究了求解二阶锥互补问题的光滑化方法.首先,分别基于带光滑参数的Fischer-Burmeister函数和对称扰动的最小值函数,把二阶锥互补问题转化为一个非线性方程组,提出了两个求解单调二阶锥互补问题的光滑牛顿算法.这两个算法都具有全局收敛质.然后,利用一个新的正则化方法,给出了一个求解笛卡尔P0性质的二阶锥互补问题光滑牛顿算法,并证明了算法的全局收敛性和局部超线性收敛性质.（3）对变分不等式问题的求解算法进行了研究.将变分不等式问题转化为一个带光滑变量的光滑方程组,给出了一个求解该问题的完全光滑化算法.该算法不仅对初始点没有限制,而且在适当的假设条件下具有全局收敛性和局部二次收敛性.初步的数值试验表明该方法是有效的.（4）研究了互补问题在支持向量机中的应用.首先,简化支持向量机优化问题得到与之对偶规划等价的互补问题,提出一个求解该问题的一步光滑化分类算法.该算法可以任意选取初始点,在每一步迭代中,仅求解一个线性方程组和执行一次线性搜索,且具有二次收敛性.其次,为克服LSVM算法需要求逆矩阵而不适合求解大规模非线性分类问题的缺陷,给出了一个求解互补支持向量机的下降算法.新算法不需要计算任何Hesse矩阵或矩阵求逆运算,实现简单,计算量小.算法具有全局收敛性.仿真实验表明算法是可行有效的.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• §1.1 研究背景
• 1.1.1 二阶锥规划
• 1.1.2 变分不等式和互补问题
• §1.2 预备知识
• 1.2.1 与二阶锥相伴的欧几里得若当代数
• 1.2.2 基本概念
• §1.3 内容安排
• 第二章 二阶锥规划问题的求解算法
• §2.1 预估校正光滑算法
• 2.1.1 引言
• 2.1.2 光滑函数
• 2.1.3 算法描述
• 2.1.4 收敛性分析
• 2.1.5 数值试验
• §2.2 半光滑非精确牛顿算法
• 2.2.1 引言
• 2.2.2 问题转化
• 2.2.3 算法描述
• 2.2.4 收敛性分析
• §2.3 非线性二阶锥规划的SQP信赖域筛选法
• 2.3.1 引言
• 2.3.2 筛选法
• 2.3.3 信赖域方法
• 2.3.4 算法描述
• 2.3.5 收敛性分析
• 2.3.6 数值试验
• §2.4 本章小结
• 第三章 二阶锥互补问题的光滑化方法
• §3.1 基于Fischer-Burmeister函数的光滑牛顿法
• 3.1.1 Fischer-Burmeister光滑函数
• 3.1.2 算法描述
• 3.1.3 收敛性分析
• 3.1.4 数值试验
• §3.2 基于对称扰动最小值函数的光滑牛顿算法
• 3.2.1 对称扰动的光滑函数
• 3.2.2 算法描述
• 3.2.3 收敛性分析
• 3.2.4 数值试验
• §3.3 正则化光滑方法
• 3.3.1 正则化方法
• 3.3.2 正则化光滑函数
• 3.3.3 算法描述
• 3.3.4 收敛性分析
• 3.3.5 数值试验
• §3.4 本章小结
• 第四章 变分不等式的算法研究
• §4.1 引言
• §4.2 预备知识
• §4.3 算法描述
• §4.4 收敛性分析
• §4.5 数值试验
• 4.5.1 关于仿射变分不等式的数值试验
• 4.5.2 关于非线性互补问题的数值试验
• §4.6 本章小结
• 第五章 互补问题在支持向量机中的应用
• §5.1 引言
• §5.2 求解支持向量机的光滑化牛顿算法
• 5.2.1 标准支持向量机
• 5.2.2 光滑化算法
• 5.2.3 算法收敛性分析
• 5.2.4 数值实验
• §5.3 求解支持向量机的新的下降算法
• 5.3.1 LSVM模型
• 5.3.2 新的下降算法
• 5.3.3 数值试验
• §5.4 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果