上海论文网提供毕业论文和发表论文,专业服务20年。

一类单线性约束二次规划问题计算机快速算法的研究

  • 论文价格:免费
  • 用途: ---
  • 作者:上海论文网
  • 点击次数:79
  • 论文字数:0
  • 论文编号:el2018073119394517495
  • 日期:2018-07-28
  • 来源:上海论文网
TAGS:
本文是一篇计算机论文,计算机论文是计算机专业毕业生培养方案中的必修环节。学生通过计算机论文的写作,培养综合运用计算机专业知识去分析并解决实际问题的能力,学有所用,不仅实践操作、动笔能力得到很好的锻炼,还极大地增强了今后走向社会拼搏、奋斗的勇气和自信。(以上内容来自百度百科)今天为大家推荐一篇计算机论文,供大家参考。
 
第 1 章 绪 论
 
1.1 本文主要研究内容
随着计算机科学的高速发展,计算机技术对人们生活影响越来越大,特别是人工智能的火热,deep learning[1-5]、neural networks[6-8]、support vector machine(SVM)[9-10]等等人工智能算法留下深刻印象,而这些算法都离不开数学理论基础的支撑。我们在综合研究了支持向量机、连续二次背包[11-17]、图上快速马尔科夫[18-20]、度量投影[21-22]等等问题的算法后,发现其在模型建立后都需要求解凸二次规划问题。
.........
 
1.2 课题研究的意义
本文主体构架由五个章节组成,每个章节具体内容如下:第一章绪论:此章节交代课题选定的初衷,在研究支持向量机、连续二次背包、度量投影等问题,归纳出一类单线性约束二次规划问题标准形式,旨在给出一个标准模型和快速的通用算法,为机器学习研究者在二次规划模型求解上给出一个可靠的解决方案。针对标准模型,本文给出具体的几个应用场景组,并分析了相关场景组的已有算法和研究现状。第二章最优化理论基础知识:本文应用的最优化基础理论主要包括有:凸集、凸函数的定义及判别分析,最优性条件 KKT 判别,Lagrange 对偶问题与原问题的转化,半光滑牛顿迭代优化形式。基于上述主要基础优化思想,结合提出的实际标准模型问题,即可推出模型的最优解。本章详细给出上述基础优化理论的概念,且作有针对本文模型的展开和推广。第三章封闭形式解的构造:针对文章中所建立的标准模型,对于约束条件首先只考虑其中的类盒子约束,于是得到只有一种约束条件的二次规划问题。那么,对于简化后的模型,运用互补松弛的 KKT 最优性条件求得子问题的最优解。并对求得的最优解以分类讨论的方式证明最优解是存在且唯一的。子问题的封闭形式解得到后,通过引进参数的方法来得到原问题的参数形式解。第四章 Lagrange 对偶问题及 Pssn 算法:针对原问题的参数形式最优解,本文采用Lagrange 对偶方法得到标准二次规划问题(1.1)的对偶问题,通过求解对偶问题的最优解性质来确定原问题参数最优解中的参数取值。针对原问题与对偶问题的等价性条件优化,在分析了等价性函数的性质后,本章节中运用线搜索保障的半光滑牛顿迭代法来求得等价性函数的最优解。第五章高效鸟群优化算法:在这一章节我们介绍另外一种优化算法--鸟群优化算法,用来优化原问题与对偶问题的等价性方程。第六章算法理论分析及数值实验:对于本文设计的半光滑牛顿迭代算法,分析算法的收敛性和收敛速度,对于收敛速度主要用时间复杂度和收敛阶来衡量,在理论上给出算法的性能指标体现其优越性。本文最后实现三个典型形式的随机数值实验,并与已有的最优算法和最高水平优化软件作对比试验,证实本文算法的高效性与准确性。
.........
 
第 2 章 最优化相关理论及背景知识
 
随着人工智能时代的来临,机器学习[28-32]、深度学习[33-38]、强化学习[39-42]等各类人工智能领域逐渐被大家所熟知,更是学术研究者孜孜不倦的研究方向。人工智能算法被应用到各个领域,最优化理论在其中发挥着举足轻重的作用,其优化模型目标函数对算法来说至关重要。本章来介绍有关最优化的几个基本知识和二次规划算法的基本概念。
 
2.1 凸集和凸函数
凸集是一个拥有良好优化特性的集合,凸函数是目前优化算法最擅长处理的函数类型,凸集和凸函数在算法优化里担当关键的角色。有关凸集和凸函数的很多重要定理在最优化算法特别是二次规划问题算法的理论证明和算法性质分析中具有重要的作用。
...........
 
2.2 本章小结
本章主要介绍了最优化相关基础理论以及一些二次规划算法背景知识。首先介绍了优化中最重要的凸集和凸函数,这是整个最优化最基础的也是最重要的只是部分,是整个优化理论基石;然后介绍了最优化问题的最优性条件,这是判别一个最优解的基本必要条件,互补松弛 KKT 条件对最优解求解起着关键性作用;最后引入二次规划问题的概念,并介绍相关经典算法。
........
 
第 3 章 封闭形式解的构造..........16
3.1 子问题封闭性解的构造 ............16
3.2 参数方法 ......20
第 4 章 LAGRANGE 对偶问题及 PSSN 算法........22
4.1 拉格朗日对偶方法 ..........22
4.2 PSSN 算法 .....24
第 5 章 基于双高斯函数的高效鸟群算法 .....32
5.1 鸟群算法介绍 ........32
5.2 基本鸟群算法流程 ..........33
5.3 高效鸟群算法 ........34
5.4 高效鸟群优化算法步骤及时间复杂度分析 ..........37
5.5 测试结果及分析 ....38
5.6 高效鸟群算法总结 ..........39
 
第 6 章 算法理论分析及数值实验
 
本章节主要讨论算法的一些关键处理技术和给出收敛速度分析,并在理论的指导下设计三个典型的随机数值实验来验证算法的高效性和实用性。
 
6.1 等价性函数解析解存在的条件
针对前章节提出来的算法,主要探索对偶方程的数值解,这里也探讨算法的解析解存在的条件,由于一般解析解的条件比较严格,于是本章只作简单介绍。值得注意的是,在半光滑算法中当初始点远离极小点时,半光滑牛顿法可能不收敛,或者收敛速度非常慢。对此,在半光滑牛顿算法开始之前采用对初始点不依赖的Barzilou-Borwein stepsize 方法来选取初始点。当优化目标函数维度很大或很复杂的时候,精确线搜索的计算量很大,并且迭代点离最优解很远的时候,作精确线搜索的作用就会大大降低。非精确线搜索沿搜索方向产生迭代点,总体希望算法的迭代收敛性快,每一步并不要达到精确的最小值,非精确线搜索虽然在每一次外循环迭代增加选择步长的迭代次数,但是会使整个算法的迭代次数大大降低,从而达到加速收敛的速度。
.........
 
结 论
 
本文在总结大量机器学习算法原型的基础上,根据其数学原理将问题模型归纳成一类单线性类盒子约束凸二次规划标准形式。关于标准形式模型的最优化解,通过最优性条件和参数方法来构造,并证明了其存在唯一性。在确定最优解参数方面,引入拉格朗日对偶原理和费马定理得到最优性函数,而且文中通过分析其函数性质确定使用半光滑牛顿迭代方法得到最优参数解。全文的主要工作内容总结如下:
1. 在学习研究支持向量机、马尔科夫模型、条件随机模型、EM 模型等算法原型的基础上总结一类单线性类盒子约束标准凸二次规划模型。在简单的变量代换和变形后,上述算法模型蕴含的最优化问题都可以转化为本文提出的标准形式。
2. 本文不但提出了标准凸二次规划模型,而且运用互补松弛 KKT 条件和参数方法给出了标准二次规划形式的带参数解,并证明解的存在唯一性。在构造解的过程中以分类讨论的形式考虑标准二次规划问题的约束条件,精确地考虑到每一种情况的发生。
3. 本文在确定标准形式参数解中参数时,运用半光滑牛顿迭代方法。根据对偶问题的拉格朗日函数,运用费马定理得到最优参数方程。在分析最优参数方程的单调性和可导性质后,采用半光滑牛顿迭代的形式优化得到最优的参数。
..........
参考文献(略)
1,点击按钮复制下方QQ号!!
2,打开QQ >> 添加好友/群
3,粘贴QQ,完成添加!!