大规模二次规划和稀疏优化的分片线性同伦路径跟踪方法和分解技术

论文摘要

二次规划和稀疏优化是两类重要而基本的优化模型,在科学、工程与经济的很多领域中具有重要的应用,其数值解法研究是数值代数与优化的重要研究课题.尽管关于这两类问题解法的研究已取得了丰富的研究成果,但由于计算机和信息采集技术的不断升级,计算和信息技术的进步,特别是机器学习和大数据技术的飞速发展和应用普及,实际问题的规模越来越大,因此大规模二次规划和稀疏优化问题的高效率解法研究仍是具有挑战性的热门课题.本文对大规模二次规划和稀疏优化问题的分片线性同伦路径跟踪方法、分解技术、预热技术、邻近点方法进行了深入系统的研究,提出了一些解大规模二次规划和稀疏优化问题的高效率算法.在第一章,我们简要地介绍了二次规划和稀疏优化问题的数值解法的研究背景和现状.在第二章,我们在参数积极集方法的基础上,提出了APG预热技术、ε-精度检验和校正技巧和快速Cholesky更新技巧,给出了解强凸箱型约束二次规划问题的一种新的分片线性同伦路径跟踪方法.数值实验结果显示,该方法比已有的先进算法更加高效,并且对于病态问题表现出了较强的鲁棒性.我们证明了求解非凸箱型约束二次规划的邻近点算法在概率1的意义下Q-线性收敛到一个局部极小点,并给出了收敛因子的估计.基于该收敛性分析,我们提出了一个加速邻近点方法.数值实验结果显示,相比邻近点方法,加速邻近点方法的加速效果非常明显.结合解邻近点子问题的分片线性同伦路径跟踪方法,我们给出了解非凸箱型约束二次规划问题的加速邻近点同伦（APP-Hom）方法.数值实验结果显示,APP-Hom算法相比现有的先进算法具有非常明显的优势.因为直接将分片线性同伦路径跟踪方法推广到一般二次规划时,效果并不理想,在第三章,我们提出了解一般凸二次规划问题的邻近增广拉格朗日同伦（PAL-Hom）方法.该方法采用分片同伦路径跟踪方法求解邻近增广拉格朗日子问题,能够有效地利用分片线性同伦路径跟踪方法和增广拉格朗日方法的优点.数值结果显示,该方法在求解稠密的、等式约束少以及解的自由变量少的问题上表现优异,比内点法更加高效,并比积极集法和参数积极集法更加稳定有效.第四章,为求解SVM中的大规模二次规划问题,我们提出了一个高效的全局收敛的邻近随机块坐标极小化增广拉格朗日同伦（PSBCM-ALH）方法.我们通过高效的启发式块坐标更新策略,将大规模二次规划问题分解成一序列小规模的强凸二次规划子问题,并用增广拉格朗日同伦算法求解每个子问题.利用解的稀疏性和子问题的相似性,设计了一个收缩技巧和一个自适应参数学习技巧,提高了算法的效率和稳定性.证明了算法训练线性SVM的时间复杂度是线性的,非线性SVM的时间复杂度是二次的.数值实验结果显示,相比著名的LIBSVM软件包,我们的方法在训练大规模线性SVM和非线性SVM都具有非常明显的优势;此外,在训练大规模线性SVM时,我们的方法与先进的线性SVM训练器LIBLINEAR相比具有很强的竞争力.在第五章,我们考虑稀疏优化的高效率解法,提出了求解大规模LASSO问题的邻近块坐标极小化ι1-同伦（PBCM-ι1-Hom）方法和求解ι1-2极小化问题的邻近块坐标DCA ι1-同伦（PBCDCA-ι1-Hom）方法.这两个方法充分利用了稀疏优化问题的解的稀疏性以及问题的可分解结构,每次只需要求解小规模的强凸ι1正则极小化子问题.我们证明了,基于精心设计的块坐标更新方式,它们分别收敛到LASSO问题的最优解和ι1-2极小化问题的KKT点.此外,我们引入了参数自适应更新技巧和收缩技巧,提高了算法的效率.数值结果显示,与现有的先进算法相比,我们的算法在时间效率空间效率都具有明显的优势.

论文目录

• 摘要
• ABSTRACT
• 主要符号表
• 1 绪论
•   1.1 二次规划
•   1.2 箱型约束二次规划
•   1.3 支持向量机
•   1.4 稀疏优化
•   1.5 本文结构
• 2 求解箱型约束二次规划的邻近同伦方法
•   2.1 引言
•     2.1.1 最优性条件
•   2.2 邻近点方法
•   2.3 加速邻近点方法
•   2.4 分片线性同伦路径跟踪方法
•   2.5 数值实验
•     2.5.1 非负最小二乘问题
•     2.5.2 非负矩阵分解
•     2.5.3 一般箱型约束二次规划
•   2.6 本章小结
• 3 求解一般二次规划的邻近增广拉格朗日同伦方法
•   3.1 引言
•     3.1.1 单纯形法
•     3.1.2 内点法
•     3.1.3 积极集法
•     3.1.4 增广拉格朗日法
•   3.2 邻近增广拉格朗日同伦方法
•   3.3 数值实验
•     3.3.1 标准测试数据集
•     3.3.2 模式识别
•     3.3.3 弹性接触问题
•   3.4 本章小结
• 4 训练大规模支持向量机的PSBCM-ALH方法
•   4.1 引言
•   4.2 邻近块坐标极小化
•     4.2.1 启发式选取策略和收缩技巧
•     4.2.2 邻近正则化
•   4.3 收敛分析和时间复杂度
•     4.3.1 收敛分析
•     4.3.2 时间复杂度
•   4.4 增广拉格朗日同伦方法
•     4.4.1 自适应参数
•     4.4.2 终止准则
•   4.5 数值实验
•     4.5.1 LIBSVM数据集
•     4.5.2 人脸检测
•   4.6 本章小结
• 1-Hom方法'>5 求解大规模稀疏优化问题的PBCM-l₁-Hom方法
•   5.1 引言
•   5.2 邻近块坐标极小化
•     5.2.1 收敛分析
•   5.3 邻近块坐标DCA极小化
• 1同伦方法'>  5.4 改进的l₁同伦方法
•     5.4.1 预热
•     5.4.2 ε-精度检验和校正
•   5.5 算法实现
•   5.6 数值实验
•     5.6.1 极小化问题
•     5.6.2 极小化问题
•   5.7 结论
• 6 结论与展望
•   6.1 结论
•   6.2 创新点
•   6.3 展望
• 参考文献
• 攻读博士学位期间科研项目及科研成果
• 致谢
• 作者简介

文章来源

类型: 博士论文

作者: 王国强

导师: 于波

关键词: 二次规划,同伦方法,支持向量机,稀疏优化

来源: 大连理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 大连理工大学

分类号: O221

总页数: 140

文件大小: 7525K

下载量: 80