稀疏优化的非凸分段二次近似模型与算法研究

发布时间：2020-09-30 02:26

　　 近年来,在信号与图像处理,压缩感知,统计,机器学习,数据挖掘等领域涌现出了大量的稀疏优化问题,即其中的优化变量具有某种稀疏结构.利用稀疏结构不仅使得从少量数据中重建高维信号成为可能,更重要的是可以极大的加快大规模优化问题的计算速度.稀疏优化问题的一种主要求解思路是对模型进行松弛,而非凸松弛一般比凸松弛可以获得更高质量的稀疏解.非凸优化算法的迅猛发展,使得如何利用非凸松弛快速和准确地求解稀疏优化问题,成为一个热门的研究方向.随着大数据时代的来临,对大规模问题计算的要求不断增加,以加速梯度算法为代表的一阶算法,引起大量学者的广泛关注.自然地,加速梯度法被拓展到求解非凸优化问题,算法的收敛性也被证明.虽然许多实际的数值实验验证了加速梯度法的优越性,但是并没有理论结果表明,在求解非凸优化问题时加速梯度法要优于不加速的梯度法.因此,如何突破加速梯度法在求解非凸优化时的理论瓶颈,是一个富有挑战的问题.本博士学位论文主要探讨可以为稀疏优化模型提供更好的稀疏解的非凸松弛模型,利用模型特性设计求解算法及加速算法,致力于获得加速算法在求解非凸优化问题上的理论突破.本博士论文的主要结果和创新如下.采用极小化绝对残差近似的方法,提出Lo范数的新的非凸近似函数:分段二次近似函数.基于函数建立分段二次近似模型,根据模型特殊结构设计求解模型的迭代算法,以迭代点有界为假设条件证明迭代算法的收敛性和迭代复杂界,并通过选取模型的收缩参数控制算法产生的迭代点有界.信号恢复和图像处理的数值实验结果表明了分段二次近似模型的优越性和迭代梯度算法的有效性.利用相位图分析,更直观清晰的说明分段二次近似模型的优越性.在迭代算法的基础上,引入Nesterov的加速思想,改进Ghadimi和Lan求解非凸非光滑问题(包含分段二次近似模型)的加速梯度法,保证算法的迭代复杂界不变的前提下,每步迭代都减少一个凸优化子问题的求解,从而提高计算速率.利用分段二次近似模型对改进加速梯度法和迭代梯度算法进行测试,数值实验结果显示改进加速梯度法在求解大规模问题时计算效果要优于迭代梯度算法.其次,基于分段二次近似模型构造分段二次近似正则化模型.通过引入替代目标函数,求得分段二次正则化模型解的解析阈值表达式,提出阈值表示定理,建立阈值表达式的固定点与分段二次近似正则化模型极小值点之间的等价关系.利用阈值表示定理设计求解模型的迭代阈值算法,证明该迭代阈值算法具有线性收敛率,且收敛到分段二次近似正则化模型的极小值点.将加速思想引入到迭代阈值算法中,提出加速迭代阈值算法.应用矩阵不等式的知识,证明加速阈值算法收敛到模型的极小值点并具有线性收敛率,且比迭代阈值算法的线性收敛率更优.信号处理,图像恢复和图像去模糊的数值实验也验证了这一理论结果,并在数值实验中将分段二次近似正则化模型和L1,L1/2正则化模型进行比较,结果显示了分段二次近似正则化模型的优越性.
【学位单位】：上海大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：O224
【部分图文】：

Ｎ逡逑｜ＷＩ0邋＝邋ｌｉｍＪ｜＜邋＝邋ｌｉｍ0２Ｗ９．逡逑ｉ＝ｌ逡逑图２．１画出了一维时｜｜ａ：Ｍ的函数值与《的关系．而当０＜ｇ＜邋１时，只有分＝逡逑１／２，邋２／３时正则化问题才有解析的阈值表达式［３１，６７，１１７］．且Ｌ１／２正则化问题可逡逑以作为＼，０邋＜邋ｇ邋＜邋１正则化问题的代表［１１８］．逡逑

数ＰＯｒ）的定义域拓展到全空间Ｒ＇即，逡逑Ｐ｛ｘ）邋＝邋－ｘＴｘ邋＋邋２｜｜ｓ｜｜ｉ，邋ｘ邋ｅ邋Ｒｎ．逡逑然而，在［－ｅ，ｅ］以外的区域，函数ＰＯｅ）并不能很好的近似ＩＷｂ，如图３．１（ｂ）所示．逡逑因此，在利用函数尸（ａ0建立分段二次近模型时，将引入收缩参数ｒ控制变量ａ；的逡逑每个迭代点都在区域［－ｅ，ｅ］内．逡逑下面，先从一维和二维几何图像的角度说明函数：丨Ｍｈ，逦Ｎｌｇ，ＩＭｈ邋－逡逑｜｜；ｒ丨丨和Ｐ（ａ0对ｌｌｃｃｌｌｏ的近似效果．逡逑、，之逦，逦１逡逑０．９－夂逦＊逦－逡逑０．斗逦ｘ邋；：邋ｙ邋－逡逑。．汴逦Ｘ邋＼逦＇，、逦

图３．１（ａ）给出了函数丨丨义丨丨0，丨丨也Ｍｇ，逦ＩＷＩｉ和尸⑷在区间［－Ｕ］上逡逑的图像．从图像的角度可以看出，尸0ｃ）比丨丨地对丨Ｗ｜Ｑ的近似效果要好．此外，逡逑当０．３８邋ＳＵＵ邋１时，与相比尸（ｘ）对丨丨４0的近似效果要更好．当０．６１邋Ｓ邋Ｗｓ逡逑１时，Ｐ0ｃ）比｜｜ｘ｜｜ｊｇ对｜Ｗ｜0的近似效果要好．而丨１急－ＩＷ丨在一维情况下函数值为逡逑零，因此从几何的角度来说它并不能为ＩＷ｜0提供好的近似．逡逑■邋Ｉ２逦１（逦■逡逑Ｉ１６逦?

【相似文献】

相关期刊论文 前10条

1 李博;杜杰;;一类非凸全局最优化问题的新的凸凹化法[J];青岛科技大学学报(自然科学版);2017年01期

2 杨孝平;关于含非凸约束的变分问题[J];应用数学学报;1996年04期

3 王春;丘小玲;王能发;陈拼博;;关于非凸的有限理性的稳定性[J];运筹学学报;2016年03期

4 邹东涛;二元机制的失灵及其“非凸组合”之谜[J];学术研究;1994年02期

5 梁治安;;关于非凸多目标规划问题的一种近似方法的说明（英文）[J];内蒙古大学学报(自然科学版);2016年03期

6 李奇，高廷耀，金毅;非凸大系统优化的辅助变量法[J];同济大学学报(自然科学版);1994年02期

7 王俊彦;高顺川;王春红;;非凸情况下发展包含的反周期问题[J];吉林大学学报(理学版);2013年04期

8 张春阳;张国霜;李卓识;刘庆怀;;正独立映射的判定及其在非凸优化中的应用[J];长春工业大学学报(自然科学版);2010年01期

9 张世清;一类非凸自治二阶Hamilton系统的极小周期解[J];南开大学学报(自然科学版);1994年02期

10 董海涛;用通量分裂法解非凸Hamilton－Jacobi方程的主要算法[J];西北大学学报(自然科学版);1996年01期

相关会议论文 前5条

1 唐智亮;刘书田;张宗华;;新型非凸截面薄壁管轴向冲击吸能性能研究[A];中国力学学会学术大会'2009论文摘要集[C];2009年

2 王燕军;;盒子约束或双值约束非凸三次优化问题的全局最优性条件(英文)[A];中国运筹学会第九届学术交流会论文集[C];2008年

3 丁玉珑;;知觉学习引起非凸显复杂刺激自动无意识捕获注意[A];第二十一届全国心理学学术会议摘要集[C];2018年

4 江涛;章青;;非凸边界上自然单元法形函数计算的边界结点法(B-NEM)[A];庆祝中国力学学会成立50周年暨中国力学学会学术大会’2007论文摘要集（下）[C];2007年

5 张洁;朱经浩;;关于求解非凸全局优化问题的最优控制方法[A];中国运筹学会第十届学术交流会论文集[C];2010年

相关博士学位论文 前10条

1 苗晴;最优化信号处理中若干非光滑、非凸与非线性问题的研究[D];广东工业大学;2018年

2 李倩;稀疏优化的非凸分段二次近似模型与算法研究[D];上海大学;2018年

3 王怡洋;非凸非光滑优化问题在图像处理和机器学习中的算法与应用[D];大连理工大学;2017年

4 陈拉明;基于非凸优化的稀疏重建理论与算法[D];清华大学;2016年

5 李昱帆;稀疏恢复问题的非凸松弛方法[D];天津大学;2015年

6 顾剑;非凸二阶锥规划问题的非线性重新尺度化方法[D];大连理工大学;2009年

7 白晓迪;带离散结构的非凸优化问题的算法研究[D];复旦大学;2014年

8 向文;几类带二次约束的非凸二次优化问题的算法研究[D];北京邮电大学;2010年

9 张勇;基于(?)_q正则化的稀疏优化问题研究[D];上海大学;2016年

10 蔡红艳;带二次约束的非凸二次分式优化问题研究及其在认知无线网络中的应用[D];北京邮电大学;2014年

相关硕士学位论文 前10条

1 郭亚宁;具有可分结构非凸问题的局部最优化方法[D];重庆师范大学;2018年

2 李玉雄;非凸在线支持向量机的研究与应用[D];北京工业大学;2013年

3 王亚丽;非凸极小化的两种分裂方法[D];郑州大学;2016年

4 李鹏程;非凸收缩核和不动点指数的计算[D];东北大学;2012年

5 律金曼;求解一类非凸非光滑优化问题的邻近交替束方法[D];广西大学;2017年

6 杨洋;一类非凸非光滑约束优化的束方法[D];大连理工大学;2012年

7 乔欣;非光滑非凸约束问题的一种迫近束方法[D];辽宁师范大学;2012年

8 刘永乐;基于非凸的压缩感知随机配置方法求解带有随机输入的SPDEs[D];上海师范大学;2017年

9 刘会成;具有箱式约束的非凸非光滑优化问题的规范对偶方法[D];五邑大学;2015年

10 王璞玉;分布式非凸正则化方法研究[D];西北大学;2017年

本文编号：2830608