正交投影非负矩阵的交替方向乘子分解方法

目的 目前非负矩阵分解一般使用乘性规则进行更新,乘性更新规则虽实现简单,但更新时收敛较慢,而且容易陷入局部最优解。当数据规模较大时,乘性规则的时效性很低,难以应用于一些实时性较强的问题中。针对乘性更新规则的这些缺点,提出一种使用交替方向乘子求解正交投影非负矩阵分解的方法。方法 首先,基于正交投影非负矩阵的正交性和稀疏性特征,将原始的目标函数优化问题分解为各子问题的交替优化求解过程。通过引入辅助变量建立原目标函数的增广拉格朗日方程,完成对原问题的子问题等价表示;然后,对转换后方程的主变量和对偶变量进行交替优化求解,从而找到原问题最优解。结果 不同规模矩阵分解仿真实验结果表明,与乘性更新规则相比,本文所提方法在收敛速度和精度上具有明显优势,特别是在矩阵规模很大时,收敛速度明显优于乘性规则。同时,将本文方法应用于目标跟踪问题中,提出一种基于交替方向乘子方法的模版更新策略,并与乘性规则以及其他3种经典目标跟踪算法进行比较。本文方法在目标跟踪效果上与基于乘性更新规则方法相当,且优于其他3种方法,重叠率约0.73,且帧处理速度约是乘性规则的3.8倍。结论 本文方法在数据规模较大时,处理速度明显优于乘性规则。在目标跟踪应用中,因其分解过程中的稀疏性和正交性,与常用跟踪算法相比能较好地应对视频场景中的遮挡、尺度变化及光照变化等干扰,其跟踪性能更加稳定。     

An Alternating Augmented Lagrangian method for constrained nonconvex optimization

ABSTRACT

We consider the problem of minimizing a smooth nonconvex function over a structured convex feasible set, that is, defined by two sets of constraints that are easy to treat when considered separately. In order to exploit the structure of the problem, we define an equivalent formulation by duplicating the variables and we consider the augmented Lagrangian of this latter formulation. Following the idea of the Alternating Direction Method of Multipliers (ADMM), we propose an algorithm where a two-blocks decomposition method is embedded within an augmented Lagrangian framework. The peculiarities of the proposed algorithm are the following: (1) the computation of the exact solution of a possibly nonconvex subproblem is not required; (2) the penalty parameter is iteratively updated once an approximated stationary point of the augmented Lagrangian is determined. Global convergence results are stated under mild assumptions and without requiring convexity of the objective function. Although the primary aim of the paper is theoretical, we perform numerical experiments on a nonconvex problem arising in machine learning, and the obtained results show the practical advantages of the proposed approach with respect to classical ADMM.     

An alternating direction method for second-order conic programming

An alternating direction dual augmented Lagrangian method for second-order cone programming (SOCP) problems is proposed. In the algorithm, at each iteration it first minimizes the dual augmented Lagrangian function with respect to the dual variables, and then with respect to the dual slack variables while keeping the other two variables fixed, and then finally it updates the Lagrange multipliers. Convergence result is given. Numerical results demonstrate that our method is fast and efficient, especially for the large-scale second-order cone programming.     

Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables

We propose a new splitting augmented Lagrangian method (SALM) for solving a class of optimization problems with both cardinality constraint and semicontinuous variables constraint. The proposed approach, inspired by the penalty decomposition method in [Z.S. Lu and Y. Zhang, Sparse approximation via penalty decomposition methods, SIAM J. Optim. 23(4) (2013), pp. 2448–2478], splits the problem into two subproblems using auxiliary variables. SALM solves two subproblems alternatively. Furthermore, we prove the convergence of SALM, under certain assumptions. Finally, SALM is implemented on the portfolio selection problem and the compressed sensing problem, respectively. Numerical results show that SALM outperforms the well-known tailored approach in CPLEX 12.6 and the penalty decomposition method, respectively.     

多特征融合与交替方向乘子法的行人再识别

目的 由于行人图像分辨率差异、光照差异、行人姿态差异以及摄像机视角和成像质量差异等原因,导致同一行人在不同监控视频中的外观区别很大,给行人再识别带来了巨大挑战。为提高行人再识别的准确率,针对以上问题,提出一种基于多特征融合与交替方向乘子法的行人再识别算法。方法 首先利用图像增强算法对所有行人图像进行处理,减少因光照变化产生的影响,然后把处理后的图像进行非均匀分割,同时使用特定区域均值法提取行人图像的HSV和LAB颜色特征以及SILTP（scale invariant local ternary pattern）纹理特征和HOG（histogram of oriented gradient）特征,融合多种特征得到行人图像对的整体与局部相似度度量函数并结合产生相似度函数,最后使用交替方向乘子优化算法更新出最优的测度矩阵实现行人再识别。结果 在VIPeR、CUHK01、CUHK03和GRID这4个数据集上进行实验,其中VIPeR、CUHK01和GRID 3个数据集Rank1（排名第1的搜索结果即为待查询人的比率）分别达到51.5%、48.7%和21.4%,CUHK03 手动裁剪和检测器检测数据集Rank1分别达到62.40%和55.05%,识别率有了显著提高,具有实际应用价值。结论 提出的多特征融合与交替方向乘子优化算法,能够很好地描述行人特征,迭代更新出来的测度矩阵能够很好地表达行人之间的距离信息,较大幅度地提高了识别率。该方法适用于大多数应用场景下的行人再识别。尤其是针对复杂场景下静态图像行人再识别问题,在存在局部遮挡、光照差异和姿态差异的情况下也能保持较高的识别正确率。     

基于非凸低秩约束的图像修复方法

受传输干扰或存储不当等因素的影响,现实应用中获取的某些图像通常会存在像素缺失现象,这给图像的后续分析与处理带来了一定影响.解决该问题的常用方法是对图像进行低秩修复.利用低秩特性进行修复的方法大多以秩函数建模,由于矩阵秩函数是非凸离散的,该模型的求解是一个NP难问题,所以通常利用核范数对矩阵的秩进行凸松弛.但是,基于核范...     

ADMM稀疏非负矩阵分解语音增强算法

提出一种基于交替方向乘子法的（Alternating Direction Method of Multipliers,ADMM）稀疏非负矩阵分解语音增强算法,该算法既能克服经典非负矩阵分解（Nonnegative Matrix Factorization,NMF）语音增强算法存在收敛速度慢、易陷入局部最优等问题,也能发挥ADMM分解矩阵具有的强稀疏性。算法分为训练和增强两个阶段：训练时,采用基于ADMM非负矩阵分解算法对噪声频谱进行训练,提取噪声字典,保存其作为增强阶段的先验信息;增强时,通过稀疏非负矩阵分解算法,从带噪语音频谱中对语音字典和语音编码进行估计,重构原始干净的语音,实现语音增强。实验表明,该算法速度更快,增强后语音的失真更小,尤其在瞬时噪声环境下效果显著。     

基于矩阵模型的方向关系表示与推理

传统方向关系模型难以支持空间的点、线、面物体的表示,其推理采用效率较低的查表运算,不支持复杂方向关系推理。为解决此问题,提出基于矩阵模型的方向关系表示与推理的方法。该方法为空间方向关系的定性表示、描述、推理运算构建基础理论,为空间查询和一致性校验研究提供了新思路。     

An efficient augmented Lagrangian method for support vector machine

ABSTRACT

Support vector machine (SVM) has proved to be a successful approach for machine learning. Two typical SVM models are the L1-loss model for support vector classification (SVC) and ε-L1-loss model for support vector regression (SVR). Due to the non-smoothness of the L1-loss function in the two models, most of the traditional approaches focus on solving the dual problem. In this paper, we propose an augmented Lagrangian method for the L1-loss model, which is designed to solve the primal problem. By tackling the non-smooth term in the model with Moreau–Yosida regularization and the proximal operator, the subproblem in augmented Lagrangian method reduces to a non-smooth linear system, which can be solved via the quadratically convergent semismooth Newton's method. Moreover, the high computational cost in semismooth Newton's method can be significantly reduced by exploring the sparse structure in the generalized Jacobian. Numerical results on various datasets in LIBLINEAR show that the proposed method is competitive with the most popular solvers in both speed and accuracy.     

An augmented Lagrangian relaxation for analytical target cascading using the alternating direction method of multipliers

Analytical target cascading is a method for design optimization of hierarchical, multilevel systems. A quadratic penalty relaxation of the system consistency constraints is used to ensure subproblem feasibility. A typical nested solution strategy consists of inner and outer loops. In the inner loop, the coupled subproblems are solved iteratively with fixed penalty weights. After convergence of the inner loop, the outer loop updates the penalty weights. The article presents an augmented Lagrangian relaxation that reduces the computational cost associated with ill-conditioning of subproblems in the inner loop. The alternating direction method of multipliers is used to update penalty parameters after a single inner loop iteration, so that subproblems need to be solved only once. Experiments with four examples show that computational costs are decreased by orders of magnitude ranging between 10 and 1000.     

低秩矩阵恢复算法综述

将鲁棒主成分分析、矩阵补全和低秩表示统称为低秩矩阵恢复,并对近年来出现的低秩矩阵恢复算法进行了简要的综述。讨论了鲁棒主成分分析的各种优化模型及相应的迭代算法,分析了矩阵补全问题及求解它的不精确增广拉格朗日乘子算法,介绍了低秩表示的优化模型及求解算法。最后指出了有待进一步研究的问题。     

低秩分块矩阵的核近似

为了探讨结构受限下的矩阵分解问题,通过最小化块外对角线来增强类与类之间数据表示的不相关性,从而实现分块约束,即数据来源于不同的聚类结构,是一种局部结构的约束;同时通过增强样本的自表达属性并缩小样本之间的差距来增强类内数据表示的相关性,从而实现低秩约束,即数据行出现冗余,是一种全局结构的约束。随后设计了一个低秩分块矩阵的核近似算法,通过交替方向乘子法迭代求解。最后将该方法分别在人脸识别和字符识别上进行测试。实验结果表明,所提出的低秩分块矩阵分解算法在收敛速度和近似精度上都具有一定的优势。     

非负矩阵分解降维的入侵检测方法

直接对高维网络连接数据进行处理会出现维数灾难问题,因此,需要对其进行维数约简。非负矩阵分解不仅能对高维数据进行降维,而且使矩阵在分解后的所有分量均为非负值,符合网络连接数据的语义特征。将其应用到入侵检测中,把高维数据投影到低维可视空间上,用散点来表示网络连接记录,通过观察散点所处位置来判断其所属类别,实现入侵检测的可视化。实验验证了这种入侵检测方法的有效性。     

改进交替方向乘子法求解冷水机组负荷分配群智能优化问题

群智能控制系统中的多台冷水机组负荷优化分配问题是一个多块优化问题,传统分布式方法难以获得其收敛解.文中将交替方向乘子法(ADMM)引入冷水机组负荷分配群智能优化问题中,并通过一种有效的高斯罚函数(GPF)更新策略改进了交替方向乘子法收敛特性.同时,建立了一种基于ADMM–GPF–GBS双层分布式计算框架的冷水机组负荷优...     

基于对称非负矩阵分解的重叠社区发现方法

针对重叠社区中的重要节点(重叠节点、中心节点、离群节点)及其固有的重叠社区结构的发现问题,提出了一种新的对称非负矩阵分解算法。首先将误差逼近项和非对称惩罚项的和作为目标函数,然后基于梯度更新的原则及非负约束条件推导出该算法。对5个实际网络进行了仿真实验,结果显示所提算法能将实际网络的重要节点及其固有的社区结构发现出来。从社区发现结果的平均导电率和算法的执行时间看,所提方法优于非负矩阵分解社区发现(CDNMF)方法;从准确率和召回率的调和平均值的加权平均值看,所提方法比较适合较大数据集的重叠社区发现。     

基于牛顿法的并行优化算法

针对非线性数值优化问题,提出一种在分布式环境下的基于牛顿法的并行算法。引入松弛变量,将不等式约束转换为等式约束,利用广义拉格朗日乘子将约束优化问题转换为无约束子优化问题。为了并行地求解这些子优化问题,将Newton迭代法中的Hessian矩阵进行适当的分裂,采用简单迭代法求解Newton法中的线性方程组。在理论上对该算法进行了收敛性分析。在HP rx2600集群上进行的数值实验结果表明并行效率达90%以上。     

基于矩阵分解的DeepWalk链路预测算法

现有的链路预测方法的数据来源主要是基于邻居、路径和随机游走的方法,使用的是节点相似性假设或者最大似然估计,尚缺少基于神经网络的链路预测研究。基于神经网络的一些研究表明,基于神经网络的DeepWalk网络表示学习算法可以更加有效地挖掘到网络中的结构特征,已有研究证明DeepWalk等同于分解目标矩阵。因此,提出了一种基于矩阵分解的DeepWalk链路预测算法（LPMF）。该算法首先基于矩阵分解的DeepWalk算法分解得到网络的表示向量;然后通过余弦相似度计算每对节点之间的相似度,构建目标网络的相似度矩阵;最后利用相似度矩阵,在三个真实的引文网络中进行链路预测实验。实验结果表明,提出的链路预测算法性能优于现存的20余种链路预测算法。这充分表明了LPMF能够有效地挖掘网络中节点之间的结构关联性,而且在实际网络的链路预测中能够发挥出较为优异的性能。     

A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization

We present a new hybrid method for solving constrained numerical and engineering optimization problems in this paper. The proposed hybrid method takes advantage of the differential evolution (DE) ability to find global optimum in problems with complex design spaces while directly enforcing feasibility of constraints using a modified augmented Lagrangian multiplier method. The basic steps of the proposed method are comprised of an outer iteration, in which the Lagrangian multipliers and various penalty parameters are updated using a first-order update scheme, and an inner iteration, in which a nonlinear optimization of the modified augmented Lagrangian function with simple bound constraints is implemented by a modified differential evolution algorithm. Experimental results based on several well-known constrained numerical and engineering optimization problems demonstrate that the proposed method shows better performance in comparison to the state-of-the-art algorithms.     

丰富图像标签的正则化非负矩阵分解方法

目的 随着Web2.0技术的进步,以用户生成内容为中心的社交网站蓬勃发展,也使得基于图像标签的图像检索技术越来越重要。但是,由于用户标注时的随意性和个性化,导致用户提交的图像标签不够完备,降低了图像检索的准确性。方法 针对这一问题,提出一种正则化的非负矩阵分解方法来丰富图像欠完备的标签,提高图像标签的完备性。利用非负矩阵分解的方法将原始的标签-图像矩阵投影到潜在的低秩空间里消除噪声,同时利用图像的类内视觉离散度作为正则化项提高消除噪声、丰富标签的效果。结果 利用从社交网站Flickr上下载的大量社交图像进行对比实验,验证了本文方法对丰富图像标签的有效性。通过对比目前流行的优化算法,本文算法获得较高的性能提升,算法平均准确度提高了12.3%。结论 将图像类内视觉离散度作为正则化项的非负矩阵分解算法,能较好地丰富社交图像的标签,解决网络图像标签的欠完备问题。     

A new alternating direction method for solving variational inequalities

We introduce a modified alternating direction method for structured monotone variational inequalities by performing an additional projection step at each iteration and another optimal step length is employed to reach substantial progress in each iteration. This method only needs functional values for given variables in the solution process and avoids the task of estimating the co-coercive modulus. All the computing process are easily implemented and the global convergence is also presented under mild assumptions. Some preliminary computational results are given.