求解若干稀疏优化问题的邻近分裂算法设计与研究
发布时间:2020-06-05 01:12
【摘要】:稀疏优化问题具有重要的应用背景,如信号去噪,模型选择,图像处理等等.本文研究LASSO,块LASSO以及稀疏块LASSO,针对更一般的模型,目标函数为光滑函数与非光滑函数的和,提出了求解方法.详细说明如下:首先,提出了修正邻近梯度方法,主要是以固定步长下的邻近梯度作为迭代方向,并选取自适应步长.证得算法具有Q-线性收敛速率,与原始邻近梯度法的收敛速率相比有很大改进.通过数值实验,将本文提出的修正邻近梯度法与原始方法相比较,表明所提算法在计算时间上具有一定的优势.原因在于固定步长下的邻近梯度的求解与原始邻近梯度法在经过若干次线搜索确定步长后再求解邻近梯度相比节约了大量运算时间.其次,为改进上述修正邻近梯度方法的非单调性,提出了一类新的下降步长搜索方法用以计算下降方向.基本思想是利用目标函数光滑部分梯度的Lipschitz连续性,在邻近梯度的计算过程中,只需几步迭代就可以确定使得目标函数值下降的方向.迭代步长选取之前修正邻近梯度法自适应步长变化区间的最大值,即采用固定步长.新的修正邻近梯度法同样具有Q-线性收敛速率.数值实验表明,新的修正邻近梯度法不仅具有目标函数值下降的性质,而且在计算时间上也具有一定优势.在上述两部分工作的基础上,设计了一般性的稀疏度约束问题模型,计算具有一定稀疏度或分块稀疏问题.具体计算过程需要将变量分为各具有稀疏度约束两部分.特别地,稀疏优化问题与分块稀疏优化问题皆可以看作是稀疏度约束问题的特殊情况.针对该类问题,我们提出分层求解方法,整体采用交替最小化方法,而针对每个子问题借助投影梯度法求解.在给定的最优化条件下,证明了投影梯度法求解子问题所得函数值序列是下降的.进一步,给出算法的收敛性分析,并在目标函数为凸的条件下证明了算法的次线性收敛速率.最后,本文设计了求解一类稀疏优化问题的凹凸(DC)算法.主要思想是利用光滑凹部分的线性近似函数,设计出凸规划模型的求解问题.在某些标准假设条件下,得到解的稀疏性质,并给出了算法的收敛性分析.
【图文】:
的迭代图像.其中向量维数我们选取《邋=邋1000,邋m分别选取的是a3n,0.6n.因为我逡逑们主要测试两个算法下降的快慢,所以当结果显示出来差别的时候我们就停止算逡逑法的运行.具体结果如图3邋-邋1和图3邋-邋2.逡逑m=0.3n逡逑;逦I逦I逦I逦I逦I逡逑\逦逦PGM逡逑\逦—邋—邋一邋MPGM逡逑\\逡逑\\逡逑1.9邋W逡逑10逦'邋w逦'逡逑W逡逑W逡逑¥邋\\\\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋、、逡逑\邋、、逡逑101.8-邋、'邋、、、、邋-逡逑、、、邋_逡逑逦,逦,逦逦——….一邋,逦逡逑0逦200逦400逦600逦800逦1000逦1200逡逑iter逡逑图3-1:目标函数值下降速度比较逡逑图3邋-邋1和图3邋-邋2中,obj代表的是目标函数值的对数指标,iter代表迭代次数.逡逑从图3邋-邋1和图3-2中我们可以看出来修正邻近梯度法是具有目标函数下降性质逡逑的,并且下降速度相对较快.进一步,,我们还测试了相同情况下两个相邻迭代点的逡逑距离随着运行时间的变化图像.结果见图3邋_3和图3邋-邋4.逡逑图3邋-邋3和图3-4中,successful邋difference表不两个相邻迭代之间的跑禽.从两逡逑个图中不难看.出,修正邻近梯度法运行更加稳健.逡逑3.4邋本章小结逡逑本章主要分析求解非光滑凸优化问题(1-23)的单调修正邻近梯度的设计与实逡逑现.在设计算法的思路分析中
_去目标函数值下降速度比较
【学位授予单位】:北京工业大学
【学位级别】:博士
【学位授予年份】:2018
【分类号】:O224
【图文】:
的迭代图像.其中向量维数我们选取《邋=邋1000,邋m分别选取的是a3n,0.6n.因为我逡逑们主要测试两个算法下降的快慢,所以当结果显示出来差别的时候我们就停止算逡逑法的运行.具体结果如图3邋-邋1和图3邋-邋2.逡逑m=0.3n逡逑;逦I逦I逦I逦I逦I逡逑\逦逦PGM逡逑\逦—邋—邋一邋MPGM逡逑\\逡逑\\逡逑1.9邋W逡逑10逦'邋w逦'逡逑W逡逑W逡逑¥邋\\\\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋\逡逑\邋、、逡逑\邋、、逡逑101.8-邋、'邋、、、、邋-逡逑、、、邋_逡逑逦,逦,逦逦——….一邋,逦逡逑0逦200逦400逦600逦800逦1000逦1200逡逑iter逡逑图3-1:目标函数值下降速度比较逡逑图3邋-邋1和图3邋-邋2中,obj代表的是目标函数值的对数指标,iter代表迭代次数.逡逑从图3邋-邋1和图3-2中我们可以看出来修正邻近梯度法是具有目标函数下降性质逡逑的,并且下降速度相对较快.进一步,,我们还测试了相同情况下两个相邻迭代点的逡逑距离随着运行时间的变化图像.结果见图3邋_3和图3邋-邋4.逡逑图3邋-邋3和图3-4中,successful邋difference表不两个相邻迭代之间的跑禽.从两逡逑个图中不难看.出,修正邻近梯度法运行更加稳健.逡逑3.4邋本章小结逡逑本章主要分析求解非光滑凸优化问题(1-23)的单调修正邻近梯度的设计与实逡逑现.在设计算法的思路分析中
_去目标函数值下降速度比较
【学位授予单位】:北京工业大学
【学位级别】:博士
【学位授予年份】:2018
【分类号】:O224
【相似文献】
相关期刊论文 前10条
1 陈元媛;高岩;刘志敏;杜守强;;一类特殊优化问题的光滑梯度法[J];运筹学学报;2017年02期
2 李蕊;;半定规划的改进的外梯度法[J];重庆文理学院学报(自然科学版);2010年05期
3 孙佑民;曾继富;苏殿贞;凌萍华;;梯度法及其应用实例[J];优选与管理科学;1986年02期
4 徐尔;一个超线性收敛的广义既约梯度法[J];高校应用数学学报A辑(中文版);1988年03期
5 O.FUJIARA;关洪林;袁达q
本文编号:2697263
本文链接:https://www.wllwen.com/kejilunwen/yysx/2697263.html