一类自适应广义交替方向乘子法

广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.     

基于交替方向乘子法的大规模线性多商品流问题求解算法

企业的商品流通配送问题是典型的线性多商品流问题.由于经营规模的扩大和全球化运营模式的推行,企业所面临的问题规模正变得空前巨大,数据存储也越来越分散,传统方法已无法适应求解需求.本文基于交替方向乘子法(ADMM)的可分解性,提出一类随机ADMM算法,将大规模的问题分解成多个、规模比较小的问题,并采取随机顺序去求解这些小问题以及对偶问题,最终得到原问题的最优解.算法克服了ADMM的直接拓展求解多块问题时可能发散的缺点,并采用MnetGen生成器随机生成的多个规模不同的线性多商品流问题对算法进行了测试,验证了算法的有效性和高效的求解效率.     

求解多周期投资组合优化问题的对称交替方向乘子法CSCD

1引言分散化投资和资产组合的选择问题是金融领域极为重要的研究课题.对于个人投资者而言,投资组合优化问题是指在最大化收益和最小化风险之间做出完美的选择.但高收益往往意味着高风险,研究如何在众多的金融产品中分配资金,确定投入的比例以规避风险和实现财产的保值、升值,具有重要意义.     

融合欧拉弹性能及边缘检测项的图像分割模型

欧拉弹性能量作为正则项已经被成功应用于图像处理模型中.Egil Bae等人在L²欧拉弹性模型的基础上提出的ECV-L1模型具有偏向于分割凸轮廓的性质,但分割结果易受参数及弹性项的影响,使得分割结果不易紧贴目标物体边缘.在ECV-L1模型基础上引入边缘检测项提出新模型,并应用增广拉格朗日算法和交替方向乘子法对新模型进行数值求解.数值实验表明,新模型具有使分割结果保持为凸的性质,同时新模型的分割结果更易靠近目标物体边缘.     

一种改进的连续最大流图像分割模型

在图像分割中,基于连续最大流模型的快速算法有明显的优势,但分割结果易受参数和步长的影响,过分割会产生大量阶梯效应的伪影,而且纹理特征不明显.文章提出一种先对图像进行预处理的新型最大流分割模型,并给出一种新的参数选取方式.实验结果表明,文章提出的新算法在速度和分割效果上更有优势.     

张量鲁棒主成分分析的增广拉格朗日交替方向方法

张量的鲁棒主成分分析是将未知的一个低秩张量与一个稀疏张量从已知的它们的和中分离出来.因为在计算机视觉与模式识别中有着广阔的应用前景,该问题在近期成为学者们的研究热点.本文提出了一种针对张量鲁棒主成分分析的新的模型,并给出交替方向极小化的求解算法,在求解过程中给出了两种秩的调整策略.针对低秩分量本文对其全部各阶展开矩阵进行低秩矩阵分解,针对稀疏分量采用软阈值收缩的策略.无论目标低秩张量为精确低秩或近似低秩,本文所提方法均可适用.本文对算法给出了一定程度上的收敛性分析,即算法迭代过程中产生的任意收敛点均满足KKT条件.如果目标低秩张量为精确低秩,当迭代终止时可对输出结果进行基于高阶奇异值分解的修正.针对人工数据和真实视频数据的数值实验表明,与同类型算法相比,本文所提方法可以得到更好的结果.     

我和乘子交替方向法20年

1997 年, 交通网络分析方面的问题把我引进乘子交替方向法(ADMM)的研究领域. 近10 年来, 原本用来求解变分不等式的ADMM在优化计算中被广泛采用, 影响越来越大. 这里总结了20 年来我们在ADMM 方面的工作, 特别是近10 年 ADMM 在凸优化分裂收缩算法方面的进展. 梳理主要结果, 说清来龙去脉. 文章利用变分不等式的形式研究凸优化的ADMM 类算法, 论及的所有方法都能纳入一个简单的预测-校正统一框架. 在统一框架下证明算法的收缩性质特别简单. 通读, 有利于了解ADMM类算法的概貌. 仔细阅读, 也许就掌握了根据实际问题需要构造分裂算法的基本技巧. 也要清醒地看到, ADMM类算法源自增广拉格朗日乘子法 (ALM) 和邻近点 (PPA)算法, 它只是便于利用问题的可分离结构, 并没有消除 ALM和PPA等一阶算法固有的缺点.     

关于一类潜在空间问题的数值计算

潜在空间模型是网络数据统计建模和可视化的有效工具.随着网络规模的不断扩大,潜在空间模型的计算也面临着巨大挑战.在本文我们应用对偶半邻近交替方向乘子法(dual semiproximal Alternating Direction Method of Multipliers,简称dsADMM)求解大型网络的通用潜在空间模型拟合问题.并在一些温和的条件下分析了该算法的全局收敛性.数值试验验证了该算法的有效性.     

多块交替方向乘子法不收敛反例的几点注记

近年来,多块交替方向乘子法被广泛地应用在信号处理、图像处理、机器学习、工程计算等各个领域中,然而它的收敛性一直是一个悬而未决的公开问题;直至2016年,陈彩华等人给出了一个三维线性方程组构成的反例说明多块交替方向乘子法是可能发散的.结合陈等人的结果,现讨论了与此相关的三个问题:1)反例之所以发散是否由于初始点选择不够好?2)反例的发散是否因为它的可行域是单点集?3)是否能够在对偶变量更新中引入某一与问题无关的步长γ∈(0,1]使得小步长的交替方向乘子法变形收敛?从理论上对前两个问题给出了否定的回答,证明当初始点随机选取时,存在可行域不是单点集的例子,使得多块交替方向乘子法求解该问题时以概率1发散;从数值上否定了第三个问题,说明即使步长γ=10~(-8),多块交替方向乘子法也可能发散.     

曲率障碍下四阶变分不等式的交替方向乘子法北大核心CSCD

对于重调和算子和曲率障碍表示的变分不等式,提出了自适应交替方向乘子数值解法(SADMM).对问题引入一个辅助变量表示曲率函数的增广Lagrange函数,导出一个约束极小值问题,并且该问题等价于一个鞍点问题.然后采用交替方向乘子法(ADMM)求解这个鞍点问题.通过采用平衡原理和迭代函数,得到了自动调整罚参数的自适应法则,从而提高了计算效率.证明了该方法的收敛性,并给出了利用迭代函数近似罚参数的具体方法.最后,用数值计算结果验证了该方法的有效性.     

A Fast Symmetric Alternating Direction Method of Multipliers

In recent years, alternating direction method of multipliers (ADMM) and its variants are popular for the extensive use in image processing and statistical learning. A variant of ADMM: symmetric ADMM, which updates the Lagrange multiplier twice in one iteration, is always faster whenever it converges. In this paper, combined with Nesterov's accelerating strategy, an accelerated symmetric ADMM is proposed. We prove its $\mathcal{O}(\frac{1}{k^2})$ convergence rate under strongly convex condition. For the general situation, an accelerated method with a restart rule is proposed. Some preliminary numerical experiments show the efficiency of our algorithms.     

A Note on the Alternating Direction Method of Multipliers

We consider the linearly constrained separable convex programming, whose objective function is separable into m individual convex functions without coupled variables. The alternating direction method of multipliers has been well studied in the literature for the special case m=2, while it remains open whether its convergence can be extended to the general case m≥3. This note shows the global convergence of this extension when the involved functions are further assumed to be strongly convex.     

Stochastic Accelerated Alternating Direction Method of Multipliers with Importance Sampling

In this paper, we incorporate importance sampling strategy into accelerated framework of stochastic alternating direction method of multipliers for solving a class of stochastic composite problems with linear equality constraint. The rates of convergence for primal residual and feasibility violation are established. Moreover, the estimation of variance of stochastic gradient is improved due to the use of important sampling. The proposed algorithm is capable of dealing with the situation, where the feasible set is unbounded. The experimental results indicate the effectiveness of the proposed method.     

An Alternating Direction Method of Multipliers for MCP-penalized Regression with High-dimensional Data

The minimax concave penalty (MCP) has been demonstrated theoretically and practically to be effective in nonconvex penalization for variable selection and parameter estimation. In this paper, we develop an efficient alternating direction method of multipliers (ADMM) with continuation algorithm for solving the MCP-penalized least squares problem in high dimensions. Under some mild conditions, we study the convergence properties and the Karush–Kuhn–Tucker (KKT) optimality conditions of the proposed method. A high-dimensional BIC is developed to select the optimal tuning parameters. Simulations and a real data example are presented to illustrate the efficiency and accuracy of the proposed method.     

A Bregman-style Partially Symmetric Alternating Direction Method of Multipliers for Nonconvex Multi-block Optimization

The alternating direction method of multipliers(ADMM) is one of the most successful and powerful methods for separable minimization optimization. Based on the idea of symmetric ADMM in two-block optimization, we add an updating formula for the Lagrange multiplier without restricting its position for multiblock one. Then, combining with the Bregman distance, in this work, a Bregman-style partially symmetric ADMM is presented for nonconvex multi-block optimization with linear constraints, and the ...     

Two-Stage Image Segmentation Scheme Based on Inexact Alternating Direction Method

Image segmentation is a fundamental problem in both image processing and computer vision with numerous applications. In this paper, we propose a two-stage image segmentation scheme based on inexact alternating direction method. Specifically, we first solve the convex variant of the Mumford-Shah model to get the smooth solution, and the segmentation is then obtained by applying the K-means clustering method to the solution. Some numerical comparisons are arranged to show the effectiveness of our proposed schemes by segmenting many kinds of images such as artificial images, natural images, and brain MRI images.     

Nested Alternating Direction Method of Multipliers to Low-Rank and Sparse-Column Matrices Recovery

The task of dividing corrupted-data into their respective subspaces can be well illustrated,both theoretically and numerically,by recovering low-rank and sparse...     

Linear Convergence Rates for Variants of the Alternating Direction Method of Multipliers in Smooth Cases

In the present paper, we propose a novel convergence analysis of the alternating direction method of multipliers, based on its equivalence with the overrelaxed primal–dual hybrid gradient algorithm. We consider the smooth case, where the objective function can be decomposed into one differentiable with Lipschitz continuous gradient part and one strongly convex part. Under these hypotheses, a convergence proof with an optimal parameter choice is given for the primal–dual method, which leads to convergence results for the alternating direction method of multipliers. An accelerated variant of the latter, based on a parameter relaxation, is also proposed, which is shown to converge linearly with same asymptotic rate as the primal–dual algorithm.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

广义乘子交替方向法求解线性约束不可分非凸优化问题的收敛性

In this paper, we consider the convergence of the generalized alternating direction method of multipliers(GADMM) for solving linearly constrained nonconvex minimization model whose objective contains coupled functions. Under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality, we prove that the sequence generated by the GADMM converges to a critical point of the augmented Lagrangian function when the penalty parameter in the augmented Lagrangian function is sufficiently large. Moreover, we also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.