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

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

重庆师范大学 数学学院，重庆 401331

考虑目标函数能够分解成n个独立的凸函数,其约束条件为线性约束的可分凸优化问题.呈现了一种推广的预测矫正邻近乘子法来求解可分凸优化问题.算法在迭代中利用二次项代替了增广拉格朗日函数的增广项，算法既有邻近乘子法的特性，又有可以平行计算，并且在较弱的条件下，能保证全局收敛.     

推广的预矫正邻近点法求解可分凸优化问题

考虑目标函数能够分解成n个独立的凸函数,其约束条件为线性约束的可分凸优化问题.呈现了一种推广的预测矫正邻近乘子法来求解可分凸优化问题.算法在迭代中利用二次项代替了增广拉格朗日函数的增广项,算法既有邻近乘子法的特性,又有可以平行计算,并且在较弱的条件下,能保证全局收敛.     

求解可分离凸优化问题的惯性近似松弛交替方向乘子法

基于交替方向乘子法(ADMM)提出了一种求解可分离凸优化可行问题的惯性近似松弛交替方向乘子法(IPR-ADMM).新构造的算法不仅具有提高算法收敛性的优势的惯性外推项,而且引入随机变量以随机加速新步长,从而提高算法的灵活性.并在适当的假设下,证明了算法的全局迭代收敛性.数值实验结果表明,数据维数取值越大,算法收敛越快,...     

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

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

基于ADMM算法正则化最优步长的研究

交替方向乘子法(Alternating Direction Method of Multipliers,简称ADMM)已经成为求解大规模结构性优化问题的有效方法。尽管已经有较多关于ADMM算法收敛性的研究,但关于该算法参数对收敛性影响的定量表示仍须进一步研究,已有的结果中仅是在实验中凭经验对步长进行选取。文章研究ADMM算法l_1正则化最小的一个重要问题Lasso的收敛因子。研究发现解的形式可用软阈值算子表示,分析发现软阈值的三种情况可以等价转化成算法收敛因子的两种情况,然后通过最小化收敛因子解出最优的步长。实验表明,应用该方法选出的步长,其相应算法的收敛速度明显快于其他选取步长的情况。此外,将该方法应用到压缩感知问题,给出了一个计算最优步长的近似值策略,获得了较好的实验效果。     

通过随机排序的交替方向乘子法的矩阵恢复

为了解决交替方向乘子法（ADMM）在求解广义的鲁棒主成分分析（G-RPCA）模型时结果不收敛的问题,提出用随机排序的交替方向乘子法（RP-ADMM）来求解这一模型,并且通过数值模拟和实例验证证明了该算法的有效性。结果表明,该算法求解G-RPCA模型较目前已有的算法速度更快、鲁棒性更高;在处理同时被稀疏大噪声和稠密小噪声污染的图片时,能较理想地分离出图像的低秩部分、大噪声部分和小噪声部分。     

基于均衡约束的ADMM-LDPC译码算法

基于交替方向乘子法(ADMM)的改进型惩罚函数LDPC译码算法能够提升译码性能,但却存在优化参数数目过多的问题.针对该问题,提出一种基于均衡约束的ADMM-LDPC译码算法.首先将码字的0-1整数约束等价转化为连续的均衡约束,使得原有的整数优化问题转化为含均衡约束的非凸问题;然后采用惩罚函数的方法将该非凸问题转化为可求解的双层凸优化问题;最后采用迭代优化算法对该问题进行求解.仿真结果表明:相较于原有算法,所提算法大幅减少了所需优化的参数数目,且在低信噪比时能实现约0.05 d B的性能提升.     

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

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

基于BB步长的一类原始-对偶算法

增广拉格朗日乘子法(ALM)是求解带等式约束的二次凸优化问题的常用方法，但罚参数选取不当时，收敛速度比较慢.提出ALM-BB算法，利用Barzilai-Borwein(BB)算法的步长去改进原始的ALM,证明ALM-BB算法的收敛性.最后将这类方法运用于求解范数最优控制问题.数值算例表明改进的算法收敛速度更快.     

混合二阶全变分的抗核辐射图像降噪方法

为了更好地保留核环境下图像降噪后的细节信息,提出了基于混合二阶全变分的抗核辐射图像降噪方法。将非凸二阶全变分与重叠组稀疏正则化相结合,使用交替方向乘子法(alternating direction method of multiplier, ADMM)和增广拉格朗日乘子法对全局问题进行优化求解,多次迭代后得到基本降噪图像;将多次降噪后的基本降噪图像进行差值迭代,使核辐射图像中大范围跳变的灰度值更加接近原始图像灰度值;根据核噪声的特点,设计算法模拟出核噪声斑块。通过在真实核环境下采集的数据集和模拟的核噪声数据集上进行实验,峰值信噪比(peak signal-to-noise ratio, PSNR)和结构相似性(structural similarity, SSIM)等指标的变化及处理后的视觉效果表明,提出的算法在保留图像细节信息方面优于对比算法。     

一种自适应量化的分布式次梯度方法

[目的]考虑了网络通讯受宽带限制,提出 了 一种自适应通讯量化的分布式次梯度方法来求解分布式凸优化问题.[方法]首先设计了 自适应量化方法,其次提出了有向网络下的分布式优化次梯度算法.[结果]得到了当 目标函数为凸函数和强凸函数时该算法的收敛率.[结论]数值例子表明所提算法能有效降低通讯成本,并能适用于更一般的非平衡有向通讯网络.     

一个解可分凸优化问题的部分预校正分裂法

考虑线性约束的可分离凸优化问题,其目标函数可分为没有耦合变量的3个独立的凸函数.基于扩展的轮换方向乘子法,提出了一个新的解可分离凸优化问题的部分预校正分裂法,此算法在校正步中考虑对第1个变量不进行校正,对第2个和第3个变量进行校正;并且在较弱的条件下,证明了此算法的收敛性.     

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

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

无约束优化的超记忆梯度法及其全局收敛性

提出一类新的求解无约束优化问题的超记忆梯度法,并在较弱条件下证明了算法的全局收敛性.当目标函数为一致凸函数时,对其线性收敛速度进行了分析.     

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

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

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

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

一种改进的乘子交替方向法在l1-正则化分裂可行问题中的应用

提出了一种改进的乘子交替方向法（ADMM）算法,基于松弛技术和预测-校正框架,将松弛算子引入子问题x和对偶变量λ,使得每次迭代的步长大于1,从而提高了算法的收敛性,并在变分不等式的框架下证明了该算法的收敛性。此外,数值实验中通过图像去模糊问题验证了算法的有效性,并基于多组对照实验,综合考虑收敛效率和图像质量,选取适当的收敛准则。     

一种求解炼油厂连续时间调度模型的Lagrange分解算法

在炼油厂连续时间调度模型中,随着调度问题规模的增大,求解耗时会显著增长。该文提出了一种基于Lagrange分解的求解算法。根据炼油厂生产流程特点,将调度模型分解成9个子问题,并在子问题中加入辅助约束加快Lagrange乘子收敛。针对问题特点设计了乘子初始化方案、乘子迭代方案和对偶解可行化方法。案例仿真选用了3个具有不同调度周期和订单数量的案例进行仿真,结果表明:采用该文提出的算法能够显著提高模型的求解效率,算法求解时间与直接求解和普通Lagrange分解算法相比都要少,且随着问题规模的增大优势会更明显。从求解结果上看,算法能够得到原问题的最优解或者近似最优解。     

基于优化最小化的加强稀疏性的稀疏信号恢复算法

针对稀疏信号恢复算法对稀疏性约束不强的问题,提出了一种基于加强稀疏性非凸函数的稀疏信号恢复算法.通过分析收缩函数和惩罚函数的关系,提出一种新的具有加强稀疏性的非凸的惩罚函数,利用优化最小化(majorization-minimization,MM)方法构造非凸函数的凸上界,并对目标函数的凸部分和凸上界进行迭代求解,实现了对稀疏信号的加强恢复.相较于现存的基于非凸惩罚函数的稀疏信号恢复算法,本算法具有不受参数干扰和梯度方向包含目标函数非凸部分的优势.将提出的算法应用于稀疏无线信道的估计,仿真结果表明,该算法在噪声环境下可以使用更少的导频,取得更准确的信道估计结果.