基于原始对偶方法的图像去色精确解算法

针对张俊康等提出的图像去色算法(2021)在求解Jin去色模型(2014)的子问题时因内迭代产生的结果误差较大和耗时增加问题,文中基于原始对偶方法和拉格朗日乘子法,提出一种改进的图像去色精确解算法求解Jin模型。该算法完整利用了图像中的局部方差和局部均值信息,给出了各子问题的精确解。数值实验结果表明,相较于对比算法,所提算法在实现彩色图像灰度化的同时,能更好地保持图像对比度和细节特征,图像去色结果更精确,算法运行时间较短。

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.

基于原始对偶分裂方法求解一类约束可分离凸优化问题及其应用

本文研究一类具有代表性的约束可分离凸优化模型,其目标函数中的数据误差项满足可微性条件,许多图像恢复和图像重建等问题都可以归结为该模型的求解.为克服现有求解该模型方法的不足,文中首先借助指示函数,将原模型转化为无约束的凸优化模型;然后基于原始对偶分裂方法思想,提出一种新的迭代算法,该算法具有结构简单和参数选取容易的特点,同时证明所提算法的收敛性.最后,为验证算法的有效性,我们将其应用于CT图像重建问题,数值实验结果表明所提出的算法在重建时间和重建图像质量上优于现有的其他算法.

原始对偶有效集方法在统计学习教学中的应用

以统计学习(statistical learning)课程中基于高维线性模型的LASSO正则化为例,项目组给出了其基于原始对偶有效集(primal dual active set)方法的求解过程,并进行了相应的实证分析,期望培养学生对统计学习课程的学习兴趣和应用新近文献方法进行高维数据分析的实践经验。

一种超松弛原始对偶不动点算法及其应用

近年来,关于两个凸函数和的优化问题受到极大关注,其中一凸函数可微且其梯度满足Lipschitz连续性,另一凸函数包含有界线性算子。提出一种超松弛原始对偶不动点算法求解这一类问题,相比于原始对偶不动点算法,所提算法扩展了松弛参数的选择范围。通过定义合适的范数,运用非扩张算子不动点理论,证明所提迭代算法的收敛性,并证明算法的遍历收敛率。在对目标函数一些强的条件下,证明算法具有全局线性收敛率。最后,为验证算法的有效性和优越性,将所提算法运用于求解全变分图像复原模型,数值结果表明,选择松弛参数大于1(即超松弛)的原始对偶不动点算法比松弛参数小于1时算法收敛更快。

最小化三个凸函数之和的一个简单原始-对偶算法

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题,其中目标函数包含有梯度李普希兹连续的光滑函数,非光滑函数和含有复合算子的非光滑函数.在新方法中,对偶变量迭代使用预估-矫正的方案.分析了算法的收敛性和收敛速率.最后,数值实验说明了算法的有效性.

虚拟网映射竞争算法设计与分析

对网络虚拟化技术中的虚拟网映射问题及其研究现状进行了介绍,针对虚拟节点映射已知且物理网不支持路径分割的虚拟网映射问题,提出以物理网提供商收益最大化为目标的虚拟网映射竞争算法,并给出了算法的竞争比分析。实验表明,所提出的算法能提高物理网资源的负载均衡度和利用率,从而提高了虚拟网构建请求的接受率和物理网提供商的收益。

使用网络节点信息传递策略的分布式优化新算法

本文基于统计学习中众所周知的信度传播理论来研究非线性凸优化问题的分布式算法.通过对优化问题中的网络图中节点上和节点之间的计算以及信息传递过程的深入研究,结合信度传播理论得出适合分布式优化算法的信息传递策略.在集中式经典牛顿法和原始对偶方法框架下,所提分布式算法通过网络中的信息传递策略来完成设计.所提的分布式牛顿-拉夫森算法在无圈连通图情形下是集中式牛顿法的分布式实现.所提分布式原始对偶算法在无圈图情形下有集中式原始对偶算法的收敛效果,且对于有圈连通图也有较好的适应性和鲁棒性.仿真实验说明了我们所提信息传递策略和算法的收敛效果和适合的应用场景.

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

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

紧框架小波和总广义全变分联合约束的医学图像复原算法

为了克服传统全变分正则化方法容易造成复原图像中出现阶梯状伪边缘、纹理细节丢失的不足,本文提出了一种紧框架小波和总广义全变分联合约束的图像复原算法.首先,结合紧框架小波能够捕获含噪声或退化图像中的奇异点的优势,同时采用能够逼近任意阶多项式函数进而可以保留图像尖锐边缘的总广义全变分,构造出一种由紧框架小波的L_1范数和二阶总广义全变分的L_2范数组成的联合正则项约束的图像复原模型;其次,采用交替方向迭代方法将所提模型的最小化问题分解为两个子问题,并分别采用均值增广拉格朗日算法和Chambolle-Pock一阶原始—对偶迭代方法获得最优解.实验结果表明,所提算法在抑制噪声的同时能够有效复原图像的边缘、细节信息,两种量化指标峰值信噪比和结构相似度的值也能直观体现复原图像质量的提高水平.

求解分段常数图象分割模型的一个快速算法

针对Xue-ChengTai等提出的分段常数图象分割模型,我们提出了一个新的快速求解算法。通过引进一个函数来选择模型中的正则化参数β的值,并判断在迭代过程中何时求解不含惩罚项的泛函F。此函数的引入有效地加速了算法的收敛速度。结合原始-对偶Newton方法来求解总变差最小化问题。数值试验表明新算法具有很快的收敛速度与良好的分割效果,且算法对初始值的要求不高。

平面上带次模惩罚费用的最小能量部分覆盖问题

给定平面上的n个用户、m个传感器和一个正整数k(≤n),任意传感器s均可以通过提供能量p(s)产生一个圆形的覆盖区域,覆盖区域的半径r(s)与p(s)满足p(s)=r(s)^(α),其中,α≥1为衰减系数.平面上带次模惩罚费用的最小能量部分覆盖问题尝试寻找传感器的一个能量供应方案,使得至少有k个用户被覆盖且总能量与未覆盖用户的惩罚费用之和达到最小,其中惩罚费用由一个次模函数确定.该问题推广了最小能量覆盖问题、最小能量部分覆盖问题和带惩罚费用的最小能量部分覆盖问题.通过深入挖掘平面上半不相交圆盘集合的几何性质,本文设计了一个基于原始对偶框架的两阶段多项式时间(5·2^(α)+1)-近似算法.当惩罚费用函数是线性函数时,此算法的近似比为5·2^(α).