一类绝对值方程的若干解法

论文摘要

绝对值方程是一类NP难、不可微的问题,因它与许多数学问题等价（如广义线性互补问题、标准线性互补问题、双线性规划问题、凹极小化问题等）,又具有结构简单、求解便于转化等优点,而备受学者们的关注.本文主要针对形如Ax-|x|=b的一类绝对值方程,在解存在时,从多种不同途经设计出快速高效求解的算法,并证明其收敛性.全文主要研究成果概括如下:1.在广义牛顿算法的基础上进行了有效改进,在搜索方向上增加了一个动态的步长,改进后的算法具有全局线性收敛性,数值实验表明,改进后的算法较广义牛顿算法在求解速度与精度上都得到了大幅度的提升,所需迭代次数较少.2.受求解一维非线性方程的迭代算法的启发,先将绝对值方程转化为非线性方程,将一维上的算法通过改进推广到n维,设计了两步式和三步式两种迭代算法,算法都具有全局线性收敛性,数值实验表明,改进后的算法收敛速度较快、求解精度较高、迭代次数较少.3.为了克服粒子群算法在后期种群多样性变差、收敛速度变慢、计算停滞不前、容易陷入局部最优无法跳出的缺点,做出了如下改进:一是将惯性权重由以前的保持不变设计为随着迭代次数的增加而呈指数趋势减小,二是将局部挖掘能力较强的模式搜索算法嵌入到粒子群算法中,在迭代前期主要利用粒子群算法进行全局搜索,后期发挥模式搜索算法的强局部收敛性能,两种算法交替使用,各取所长,三是将自我学习因子设置为线性递减的变化趋势,社会学习因子设置为线性递增的变化趋势.通过标准测试函数和绝对值方程验证上述三种改进策略,显示三种改进算法的计算水平得到了极大提高,尤其是在后期加大了粒子的局部寻优能力,激发了粒子跳出局部最好这一陷阱的能力,很好地平衡了算法的局部挖掘能力和全局搜索能力.4.为了克服人群搜索算法在搜索后期易早熟、易陷入局部最优无法弹出的缺点,分别引入了单纯形搜索和模式搜索,当运行人群搜索算法进行全局搜索一定代数后,开始分别执行这两种算法来增加算法后期的局部挖掘能力,跳出局部最优这一陷阱的概率,实验表明,改进后的两种算法增加了人群搜索算法的局部搜索水平,进而提高了整个算法的收敛速度、求解精度.

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 研究现状
•   1.3 预备知识
•   1.4 本文的主要内容和结构安排
• 第二章 基于改进的广义牛顿算法求解绝对值方程
•   2.1 引言
•   2.2 广义牛顿算法
•   2.3 改进的广义牛顿算法
•   2.4 收敛性分析
•   2.5 数值实验
•   2.6 本章小结
• 第三章 基于新的迭代算法求解绝对值方程
•   3.1 引言
•   3.2 两步式迭代算法
•     3.2.1 收敛性分析
•     3.2.2 数值实验
•     3.2.3 评注
•   3.3 三步式迭代算法
•     3.3.1 收敛性分析
•     3.3.2 数值实验
•     3.3.3 评注
•   3.4 本章小结
• 第四章 基于改进的粒子群算法求解绝对值方程
•   4.1 引言
•   4.2 绝对值方程问题等价转化
•   4.3 基本粒子群算法
•   4.4 基于惯性权重指数递减的粒子群算法求解绝对值方程
•     4.4.1 惯性权重指数递减的粒子群优化算法
•     4.4.2 数值实验
•     4.4.3 评注
•   4.5 基于融入模式搜索的粒子群算法求解绝对值方程
•     4.5.1 模式搜索算法
•     4.5.2 融入模式搜索的粒子群算法
•     4.5.3 数值实验
•     4.5.4 评注
•   4.6 基于学习因子动态变化的粒子群算法求解绝对值方程
•     4.6.1 动态惯性权重和学习因子
•     4.6.2 改进后的粒子群算法
•     4.6.3 数值实验
•     4.6.4 评注
•   4.7 三种算法对比
•     4.7.1 算法回顾
•     4.7.2 数值实验
•   4.8 本章小结
• 第五章 基于改进的人群搜索算法求解绝对值方程
•   5.1 引言
•   5.2 基本人群搜索算法
•   5.3 基于单纯形算法局部优化的人群搜索算法求解绝对值方程
•     5.3.1 单纯形算法
•     5.3.2 基于单纯形算法进行局部优化的人群搜索算法
•     5.3.3 数值实验
•     5.3.4 评注
•   5.4 基于融入模式搜索的人群搜索算法求解绝对值方程
•     5.4.1 模式搜索算法
•     5.4.2 融入模式搜索的人群搜索算法
•     5.4.3 数值实验
•     5.4.4 评注
•   5.5 两种算法对比
•     5.5.1 算法回顾
•     5.5.2 数值实验
•   5.6 本章小结
• 第六章 总结与展望
•   6.1 总结
•   6.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 博士论文

作者: 封京梅

导师: 刘三阳

关键词: 绝对值方程,广义牛顿算法,迭代算法,粒子群优化算法,人群搜索算法,模式搜索算法,单纯形算法

来源: 西安电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 西安电子科技大学

分类号: TP18;O241

DOI: 10.27389/d.cnki.gxadu.2019.003141

总页数: 118

文件大小: 3268K

下载量: 26