非凸非光滑优化问题的惯性Bregman ADMM的收敛性分析

【目的】针对具有可分结构的非凸非光滑优化问题，提出一种内置惯性Bregman交替方向乘子法。【方法】为了加快算法的收敛速度，在Bregman交替方向乘子法的框架下，对子问题中的Bregman度量内置惯性项。【结果】在生成的点列有界的条件下，利用Kurdyka-Lojasiewicz性质，证明了算法的渐进收敛性。【结论】数值实验结果表明了该算法的有效性。     

一种加速的广义交替方向乘子法

针对一类特殊的凸优化问题,原始交替方向乘子法收敛较慢,为改善算法的收敛速度,一种加速交替方向乘子法被提出,但是该算法可能会使对偶变量更新步长变得很小,影响算法效果.基于此,本文提出一种加速的广义交替方向乘子法,通过应用Chambolle和Pock提出的惩罚参数更新规则,证明了所提算法在一定假设条件下的全局收敛性以及建立起了在遍历情况下的最坏Ο(1/n~2)收敛率.     

部分并行磁共振成像的交替方向乘子法研究

交替方向乘子法是求解基于全变分模型的部分并行磁共振成像(partially parallel imaging,PPI)的有效方法,但研究表明其测量矩阵的求解繁琐且复杂。文中针对交替方向乘子法采用固定步长求解速度慢的缺点,提出了一种自适应交替方向乘子法,将传统的交替方向乘子法和BarzilaiBorwein方法相结合,有效处理了全变分正则项的非凸难以求解的问题。实验结果表明,该改进算法不仅能得到较好的图像恢复效果,而且具有良好的收敛性和稳定性。     

基于ADMM迭代法的PageRank问题的求解

针对PageRank问题导出的线性方程组,首先对方程组的系数矩阵进行了LU分解,提出了一种基于交替方向乘子法(ADMM)形式的迭代算法,用于求解该线性方程组的最小二乘解;然后,证明了所提出的算法的收敛性;最后,数值结果表明了该算法的可行性.     

求解Poisson问题的区域分解和交替方向乘子法

【目的】有效求解有界闭区域的Poisson问题，得到解决这类问题的区域分解法和交替方向乘子法。【方法】用区域分解法将问题转化为用两个子区域和增广拉格朗日函数表示的极小值问题，再采用交替方向乘子法求解该问题。【结果】对算法进行了收敛性分析，并给出了此类问题的具体应用。【结论】数值结果验证了该方法求解Poisson问题的可行性。     

求解一类等式约束二次规划问题的交替变量极小化方法

本文针对一类特殊的等式约束二次规划问题,提出带有乘数的交替变量极小化方法.比较了一般的交替方向乘子算法与交替变量极小化算法在解决这类特殊的等式约束二次规划问题时的异同.并研究了这种特殊交替变量极小化算法的收敛性,给出了该方法的渐进收敛率.     

求解凸优化问题的改进对称交替方向乘子法

对称交替方向乘子法(简称S-ADMM算法)是求解可分离凸优化问题的一种有效方法。该算法利用目标函数的可分离性,将原问题分解成多个极小化子问题,然后交替求解。能否有效地求解子问题对算法的有效性有重要影响。在很多实际应用中,不能精确地求解子问题,或者精确求解子问题花费代价较大。为解决这一问题,提出了一种改进的对称交替方向乘子法(简称MSADMM算法)。与一般的S-ADMM算法相比,该算法在x子问题中引入一个半近邻项,近似地求解x子问题,克服了之前算法的不足。在适当的假设下,证明了其收敛性。最后,通过数值计算说明了该算法的有效性。     

基于ADM分解的预测-校正分解算法

考虑的是一种具有线性约束条件且目标函数是块可分的凸优化极小问题,文章的目标函数主要是由三个凸函数之和组成.解决这种模型,理论上有效的处理办法是直接拓展的交替方向乘子法,简称EADM法,该方法是在交替方向乘子法(ADMM法)的基础上演变而来.但是这种方法的收敛性目前在理论上还没有得到证明.因此,基于ADM法的直接拓展以及在韩德仁文章的指引下,本文刻画了一种新的分离方法,称为基于ADM分解的预测-校正分解算法,该方法也能解决这种模型.新方法在每次迭代的时候,通过一个轻微的校正计算产生一个新的迭代,从而校正了直接拓展的ADM法的输出结果.本文证明了新方法在适当假设条件下的全局收敛性,并通过有关例子说明了该方法具有可行性.     

非凸两分块问题乘子交替方向法的收敛性分析

乘子交替方向法(ADMM)求解大规模问题十分有效.ADMM在凸情形下的收敛性已被清晰认识,但非凸问题ADMM的收敛性结果还很少.本文针对非凸两分块优化问题,在增广拉格朗日函数满足Kurdyka-Lojasiewicz不等式性质且罚参数大于某个常数的条件下,证明了ADMM的收敛性.     

互补问题的一个新的光滑乘子价值函数

研究互补问题的新解法,给出了互补问题的一个新的光滑乘子价值函数,分析了乘子价值函数的性质,并构造了相应的算法.选取了新的下降方向和乘子修正方法,使价值函数获得两次下降,从而加快了下降速度.研究结果表明:在函数为一致P的条件下,算法具有全局收敛性、局部超线性收敛性和二次收敛性;对线性互补问题有限步收敛.     

非凸不可分离问题的广义交替方向乘子法的收敛性

交替方向乘子法（ADMM）是求解大规模优化问题和非凸非光滑问题的一种有效的方法,但当目标函数为非凸非光滑的情况时,原始ADMM算法的收敛性无法保证,且若目标函数中存在耦合函数,则算法的收敛性证明将更为复杂。在现实生活中存在的很多问题,其本质都是非凸的。因此,本文提出了一种改进的ADMM算法。与原始ADMM算法相比,该算法引入了一个松弛因子$\alpha $,构造了一种广义交替方向乘子法（GADMM）来求解具有线性约束的非凸不可分离优化问题。在一定的假设条件下,通过假设增广拉格朗日函数满足K-L不等式,证明了当惩罚参数足够大时,算法生成的序列收敛到增广拉格朗日函数的稳定点。     

一种新的广义鲁棒主成分分析(GRPCA)算法研究及应用

为恢复被混合噪声污染的低秩矩阵,提出了一种新的广义鲁棒主成分分析（GRPCA）算法。它通过最小化核范数、1范数和2,1范数的组合问题,从观测矩阵中分离出低秩部分和混合噪声部分,并用随机排序的交替方向乘子法求解。利用本文方法进行垃圾邮件分类的实验结果表明,与经典的主成分分析（PCA）和鲁棒主成分分析（RPCA）算法相比,本文方法可以有效提高垃圾邮件分类的精确度和稳定性。     

基于近似投影的水平分层调度译码算法

基于交替方向乘子法（ADMM）的线性规划（LP）译码模型因其不会出现错误平台和具有最大似然认证的优点,广受译码研究者的关注。目前大多数ADMM算法采用的是泛洪调度策略（FL）,该算法存在译码收敛速度过慢的问题。基于水平分层调度的交替方向乘子法的低密度奇偶校验（LDPC）码译码算法能够加速译码收敛速度,然而目前水平分层调度算法中的投影算法采用的为精确投影算法,复杂度较高。针对该问题,文中将近似投影算法和水平分层调度算法结合,提出基于近似投影的ADMM水平分层调度译码算法以提高译码的性能。仿真实验表明,相比其他算法,本文提出的算法的译码性能可提升0.1~0.3dB,迭代次数可降低约19%~40%,平均译码时间可减少大约21%~65%。     

一种求解单调变分不等式的下降型邻近点交替方向乘子法

针对具有可分结构的单调变分不等式问题,基于邻近点算法和文献[12]提出的下降型算法构造了一个新的下降方向,并利用下降量的下界来选择最优步长,提出一种下降型邻近点交替方向乘子法;证明了算法的收敛性;并将该方法与文献[11]中算法的下降量下界进行比较,从理论上说明了算法的优越性。     

基于L_1范数最小化的逆协方差矩阵估计

由于在高维空间中,基于固定维数的经典方法和结果不再适用,样本协方差矩阵不可逆,估计逆协方差矩阵时存在不稳定、计算成本高和非精确等问题,提出了一种L1范数最小化方法来有效估计高维逆协方差矩阵即精确矩阵.当总体分布满足指数类型条件或者多项式类型条件时,所提估计方法在各种范数下的收敛速率优于其他现存的方法.经分析验证,所提方法为凸优化问题,可采用交替方向乘子算法来解决.之后通过R语言在模拟数据和实际数据下进行仿真分析,并与Glasso方法对比逆协方差的估计性能和图恢复性能,结果表明所提估计方法准确率高、计算成本低.最后,将所提估计方法用来分析白血病数据集,并运用聚类分析对白血病人进行分类.     

稀疏多元逻辑回归问题优化算法研究

稀疏多元逻辑回归(sparse multinomial logistic regression, SMLR)因为具有在分类的同时嵌入特征选择的作用而被广泛应用于生物信息学、高光谱图像分类、图像中的多类物体识别等领域。SMLR问题最早采用迭代重加权最小二乘法(iterative reweighted least squares, IRLS)的方式进行求解。但IRLS算法在处理高维数据集或者类别数较多的数据集时具有较高的计算复杂度。为了提高SMLR的可用性,提出采用一些高级优化算法如快速迭代收缩阈值法(fast iterative shrinkage threshold method, FISTA)、快速自适应收缩阈值法(fast adaptive shrinkage threshold method, FASTA)、交替方向乘子法(alternating direction multiplier method, ADMM)等来对SMLR问题进行求解。此外,为提高SMLR的适用性,还考虑了SMLR问题的分布式优化求解。对提出的几种SMLR优化求解算法的性能在不同数据集下进行了综合比较。实验结果表明,提出的算法在求解速度和准确率指标上都优于目前最先进的基于IRLS的SMLR优化算法。     

一种新的Lagrange乘子法

基于Lagrange乘子法中将与不等式约束相关的乘子定义为原乘子的正定函数,用同样的方法处理不等式约束和等式约束的构想,构造了一种新的Lagrange乘子法. 分析了该算法的收敛性,并利用LaSalle不变集原理揭示了算法稳定机制及如何减弱收敛条件和扩大收敛域. 分析表明,算法在稳定因素和不稳定因素的综合作用下获得最优解.     

各向异性全变分图像去噪算法

图像去噪是图像复原问题中的重要研究内容之一,在此过程中图像的高频部分易受到破坏。针对这一情况,通过引入不同的权重参数惩罚x与y方向上的梯度算子,提出修正的各向异性全变分去噪模型。引入的权重参数具有局部自适应性,可以使模型对应欧拉方程在图像切线与法向方向的扩散具有更鲁棒的各向异性扩散能力,可以达到保护图像细节的目的。另外,提出的模型是具有可分裂结构的非光滑凸优化问题,采用算子分裂技术将其转化为多个易求解的子问题,并在交替方向乘子法的框架下求解,从而保证了算法在理论上的收敛性。与现阶段其他变分型的复原模型相比,所提出的模型在有效抑制噪声的同时能有效地保持图像的局部结构特征。对于分块效果明显,噪声水平较低的图像去噪结果十分显著;对于分块效果不明显,图像细节较多的图像,该模型依然有效。     

一类非对称变分不等式的非精确交替方向法

对一类非对称变分不等式问题提出了一种非精确交替方向法,对其中一个子问题(非线性方程组)的计算仅需要达到一个相对的精度,研究了迭代序列的若干性质,并证明了算法的全局收敛性.