求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

低秩张量填充的加速随机临近梯度算法

本文提出了一种求解低秩张量填充问题的加速随机临近梯度算法.张量填充模型可以松弛为平均组合形式的无约束优化问题,在迭代过程中,随机选取该组合中的某一函数进行变量更新,有效减少了张量展开、矩阵折叠及奇异值分解带来的较大的计算花费.本文证明了算法的收敛率为$O (1/k^{2})$.最后,随机生成的和真实的张量填充实验结果表明新算法在CPU时间上优于现有的三种算法.     

竞争市场均衡问题的内点算法

本文应用最优化方法求解经济学中的经典问题-竞争市场均衡问题.本文对Ye的算法(Ye首先提出了解Fisher问题的原始-对偶路径跟踪算法)做了改进,分别给出了步长调整和迭代方向分解后的原始-对偶路径跟踪算法,并对算法做了理论证明和复杂性分析.最后分析了初始点的求法,做了初步的数值计算.计算结果表明算法能在有效时间内求得问题的解.     

基于改进的不动点迭代算法的低秩Gram矩阵的恢复

仿射限制条件下的低秩矩阵的恢复问题广泛地出现在控制、信号处理及系统识别等许多领域中.此问题可以凸松弛为带仿射限制条件的矩阵核范数的极小化问题.尽管后者能够转化为标准的半定规划问题求解,但是对于规模较大的矩阵其产生的计算量也很大.为此提出一种新的求解Gram矩阵核范数极小化问题的一阶算法-改进的不动点迭代算法(FPC-BB),并给出了算法的收敛性分析.算法以不动点迭代算法(FPC)中的算子分裂技术为基础,通过改进阈值算子Tv来求解低秩Gram矩阵的恢复问题.同时,还引入Barzilai-Borwein技术进行参数的选取,提高了算法的收敛速度.数值实验显示算法不仅能够很快地将低秩Gram矩阵精确地恢复出来,对于一些非低秩矩阵的恢复问题也能得出较好的结果.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

单纯形算法的两种部分定价策略

根据Hu和Johnson的原始一对偶单纯形算法原理,提出了两种部分定价策略.给定一组原始一对偶可行解,首先,选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量,再用Dantzig准则的单纯形算法求解该原始子问题.其次,针对原始退化问题,选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价,然后应用Bland准则的单纯形算法求解原始子问题,以克服退化可能引起的循环现象.最后,对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验,结果表明,与经典单纯形算法相比,提出的算法具有更好的计算表现.     

处理噪声问题的泰勒展开交替最小化算法

为了处理图像、计算机视觉和生物信息等领域中广泛存在的稀疏大噪声和高斯噪声问题,提出了一种利用交替方向最小化思想求解主成分追求松弛模型的泰勒展开交替最小化算法(TEAM).采用推广泰勒展开和收缩算子等技术推导出低秩矩阵和稀疏大噪声矩阵的迭代方向矩阵,加入连续技术提高算法的收敛速率,设计出TEAM算法的求解步骤.实验中,将TEAM算法与该领域的顶级算法作分析对比.结果表明,TEAM算法时间优势明显,误差优势略好.     

求解鲁棒主成分分析的新交替下降方向法

鲁棒主成分分析作为统计与数据科学领域的基本工具已被广泛研究,其核心原理是把观测数据分解成低秩部分和稀疏部分.本文基于鲁棒主成分分析的非凸模型,提出了一种新的基于梯度方法和非单调搜索技术的高斯型交替下降方向法.在新算法中,交替更新低秩部分和稀疏部分相关的变量,其中低秩部分的变量是利用一步带有精确步长的梯度下降法进行更新,...     

一个基于定步长技术的超记忆梯度法

基于定步长技术,本文给出一种求解无约束优化问题的超记忆梯度算法,从而避免每步都执行线搜索.在一定条件下证明该算法具有全局收敛性和局部线性收敛率.由于该方法不用计算和存储矩阵,故适合于求解大规模优化问题.数值试验表明该算法是有效的.     

一个投影收缩算法的新步长

本文研究了求解单调变分不等式问题的一个投影收缩算法.利用何炳生教授的分析手法,给出了新步长,并且证明了在该步长下算法的全局收敛性.初步的数值试验表明了新步长的实用性.     

低秩矩阵优化若干新进展

低秩矩阵优化是一类含有秩极小或秩约束的矩阵优化问题,在统计与机器学习、信号与图像处理、通信与量子计算、系统识别与控制、经济与金融等众多学科领域有着广泛应用,是当前最优化及其相关领域的一个重点研究方向.然而,低秩矩阵优化是一个NP-难的非凸非光滑优化问题,其研究成果并非十分丰富,亟待进一步深入研究.主要从理论和算法两个方面总结和评述若干新结果,同时列出相关的重要文献,奉献给读者.     

求解低秩矩阵填充的改进的交替最速下降法

矩阵填充是指利用矩阵的低秩特性而由部分观测元素恢复出原矩阵,在推荐系统、信号处理、医学成像、机器学习等领域有着广泛的应用。采用精确线搜索的交替最速下降法由于每次迭代计算量小因而对大规模问题的求解非常有效。本文在其基础上采用分离地精确线搜索,可使得每次迭代下降更多但计算量相同,从而可望进一步提高计算效率。本文分析了新算法的收敛性。数值结果也表明所提出的算法更加有效。     

一般单调变分不等式的一个改进的预估-校正算法

最近何炳生等提出了解大规模单调变分不等式的一种预估-校正算法,然而,这个方法在计算每一个试验点时需要一次投影运算,因而计算量较大．为了克服这个缺点,我们提出了一个解一般大规模g-单调变分不等式的新的预估-校正算法,该方法使用了一个非常有效的预估步长准则,每个步长的选取只需要计算一次投影,这将大大减少计算量．数值试验说明我们的算法比最新文献中出现的投影类方法有效．     

低秩表示实现鲁棒的CT和MR图像分割

由于图像中的噪声和复杂性,传统的图像分割方法并不总是能够捕捉到所有细节,即可能会忽略相邻像素的属性或者将图像的不同部分合并在一起.为了充分利用可用信息,利用低秩表示(LRR)和鲁棒主成分分析(RPCA)模型的优点,提出了一种新的图像分割方法,通过模糊c均值(FCM)方法对低秩亲和矩阵进行聚类来获得分割结果.在整个方法中,低秩分量是图像的主要信息,是通过求解RPCA模型获得的,而亲和矩阵表示全局结构,则是通过求解LRR模型获得的.在实验部分,使用计算机断层扫描(CT)图像分割来评估本文方法,结果显示在准确性和鲁棒性方面都有了显著改进.与现有一些算法相比,本文算法对异常值更加鲁棒,并尽可能地保留了图像的细节信息.     

图的最大二等分问题的低秩可行方向算法

基于图的最大二等分问题的半定规划松弛模型,利用矩阵的低秩分解技巧,给出了该问题的半定规划松弛的一种低秩可行方向算法.在一定的条件下,证明了算法的收敛性.结合0.699随机扰动方法得到原问题的近似最优解.数值实验表明该方法能有效地求解图的最大二等分问题.     

用随机奇异值分解算法求解矩阵恢复问题

本文研究了大型低秩矩阵恢复问题.利用随机奇异值分解（RSVD）算法,对稀疏矩阵做奇异值分解.该算法与Lanczos方法相比,在误差精度一致的同时运算时间大大降低,且该算法对相对低秩矩阵也有效.     

两阶段特殊结构混合0-1规划的分解算法

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现.该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性.实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高.算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解.     

低秩矩阵恢复的混合型增广拉格朗日乘子算法CSCD

1引言低秩矩阵恢复问题,又称为鲁棒主成分分析问题或稀疏低秩矩阵分解问题,是指在较少的观测值的基础上恢复出原始矩阵.该问题来源于许多领域,如协同过滤[1,2,3],机器学习[4],图片对齐[5],信号处理[6]和量子态层析成像[7]等等.在文献[8,9,10]中,低秩矩阵恢复问题可以看作是将向量的稀疏表示推广到低秩矩阵的情形,也就是说当矩阵中某些元素严重缺失时,自动识别出损坏的元素并恢复原始矩阵[11].     

基于修正拟牛顿方程的两阶段非单调稀疏对角变尺度梯度投影算法

基于修正拟牛顿方程,利用Goldstein-Levitin-Polyak(GLP)投影技术,建立了求解带凸集约束的优化问题的两阶段步长非单调变尺度梯度投影算法,证明了算法的全局收敛性和一定条件下的Q超线性收敛速率.数值结果表明新算法是有效的,适合求解大规模问题.