ADMM for multiaffine constrained optimization

ABSTRACT

We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka–?ojasiewicz (K–?) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.     

Nonlinear model predictive control using deterministic global optimization

This paper presents a Nonlinear Model Predictive Control (NMPC) algorithm utilizing a deterministic global optimization method. Utilizing local techniques on nonlinear nonconvex problems leaves one susceptible to suboptimal solutions at each iteration. In complex problems, local solver reliability is difficult to predict and dependent upon the choice of initial guess. This paper demonstrates the application of a deterministic global solution technique to an example NMPC problem. A terminal state constraint is used in the example case study. In some cases the local solution method becomes infeasible, while the global solution correctly finds the feasible global solution. Increased computational burden is the most significant limitation for global optimization based online control techniques. This paper provides methods for improving the global optimization rates of convergence. This paper also shows that globally optimal NMPC methods can provide benefits over local techniques and can successfully be used for online control.     

Adaptive spectral factorization

An on-line spectral factorization algorithm is used to devise a globally convergent self-tuning identifier that does not suffer from restrictions that amount to knowledge of the true system (e.g. the positive real condition). The method developed uses two ideas. One idea, an old one which might be called the method of split recursions, is used to estimate the parameters in blocks. Thus, one block might get the transfer function parameters while the other gets the noise parameters. The other idea is to use spectral factorization to estimate moving average parameters. The algorithm does have its own weaknesses (e.g. transient behavior may not be good, and it relies on a condition that is only generically true), but it does not need a positive real condition to be satisfied for global convergence     

A separable programming approach to the linear complementarity problem

The linear complementarity problem (LCP) is reformulated as a nonconvex, separable program and solved with a general branch and bound algorithm. Unlike the principal alternatives, the approach offered here works for all linear complementarity problems regardless of their underlying matrix structure. In the reformulated version, the optimal value is known at the outset so a convergence check can be made at each iteration of the algorithm. This greatly improves its performance; in fact, a number of cases are given where immediate convergence can be expected.     

A sharp augmented Lagrangian-based method in constrained non-convex optimization

In this paper, a novel sharp Augmented Lagrangian-based global optimization method is developed for solving constrained non-convex optimization problems. The algorithm consists of outer and inner loops. At each inner iteration, the discrete gradient method is applied to minimize the sharp augmented Lagrangian function. Depending on the solution found the algorithm stops or updates the dual variables in the inner loop, or updates the upper or lower bounds by going to the outer loop. The convergence results for the proposed method are presented. The performance of the method is demonstrated using a wide range of nonlinear smooth and non-smooth constrained optimization test problems from the literature.     

Minimizing the multimodal functions with Ant Colony Optimization approach

The ant colony optimization (ACO) algorithms, which are inspired by the behaviour of ants to find solutions to combinatorial optimization problem, are multi-agent systems. This paper presents the ACO-based algorithm that is used to find the global minimum of a nonconvex function. The algorithm is based on that each ant searches only around the best solution of the previous iteration. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and was observed to be better.     

Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting

The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.     

A nonmonotone scaled conjugate gradient algorithm for large-scale unconstrained optimization

This paper proposes a nonmonotone scaled conjugate gradient algorithm for solving large-scale unconstrained optimization problems, which combines the idea of scaled memoryless Broyden–Fletcher–Goldfarb–Shanno preconditioned conjugate gradient method with the nonmonotone technique. An attractive property of the proposed method is that the search direction always provides sufficient descent step at each iteration. This property is independent of the line search used. Under appropriate assumptions, the method is proven to possess global convergence for nonconvex smooth functions, and R-linear convergence for strongly convex functions. Preliminary numerical results and related comparisons show the efficiency of the proposed method in practical computation.     

机器学习随机优化方法的个体收敛性研究综述

随机优化方法是求解大规模机器学习问题的主流方法,其研究的焦点问题是算法是否达到最优收敛速率与能否保证学习问题的结构。目前,正则化损失函数问题已得到了众多形式的随机优化算法,但绝大多数只是对迭代进行 平均的输出方式讨论了收敛速率,甚至无法保证最为典型的稀疏结构。与之不同的是,个体解能很好保持稀疏性,其最优收敛速率已经作为open问题被广泛探索。另外,随机优化普遍采用的梯度无偏假设往往不成立,加速方法收敛界中的偏差在有偏情形下会随迭代累积,从而无法应用。本文对一阶随机梯度方法的研究现状及存在的问题进行综述,其中包括个体收敛速率、梯度有偏情形以及非凸优化问题,并在此基础上指出了一些值得研究的问题。     

Combined new nonnegative matrix factorization algorithms with two-dimensional nonnegative matrix factorization for image processing

In recent years, nonnegative matrix factorization (NMF) has attracted significant amount of attentions in image processing, text mining, speech processing and related fields. Although NMF has been applied in several application successfully, its simple application on image processing has a few caveats. For example, NMF costs considerable computational resources when performing on large databases. In this paper, we propose two enhanced NMF algorithms for image processing to save the computational costs. One is modified rank-one residue iteration (MRRI) algorithm , the other is element-wisely residue iteration (ERI) algorithm. Here we combine CAPG (a NMF algorithm proposed by Lin), MRRI and ERI with two-dimensional nonnegative matrix factorization (2DNMF) for image processing. The main difference between NMF and 2DNMF is that the former first aligns images into one-dimensional (1D) vectors and then represents them with a set of 1D bases, while the latter regards images as 2D matrices and represents them with a set of 2D bases. The three combined algorithms are named CAPG-2DNMF, MRRI-2DNMF and ERI-2DNMF. The computational complexity and convergence analyses of proposed algorithms are also presented in this paper. Three public databases are used to test the three NMF algorithms and the three combinations, the results of which show the enhancement performance of our proposed algorithms (MRRI and ERI algorithms) over the CAPG algorithm. MRRI and ERI have similar performance. The three combined algorithms have better image reconstruction quality and less running time than their corresponding 1DNMF algorithms under the same compression ratio. We also do some experiments on a real-captured image database and get similar conclusions.     

基于随机黑洞和逐步淘汰策略的多目标粒子群优化算法

提出一种基于随机黑洞粒子群算法(RBH-PSO) 和逐步淘汰策略的多目标粒子群优化(MRBHPSO-SE) 算法. 利用RBH-PSO 全局优化能力强和收敛速度快的优点逼近Pareto 最优解; 为了避免拥挤距离排序策略的缺陷, 提出逐步淘汰策略, 并将其应用到下一代粒子的选择策略中. 同时, 动态选择领导粒子, 运用动态惯性权重系数和变异操作 来增强种群全局寻优能力, 以及避免早熟收敛. 利用具有不同特点的测试函数进行验证, 结果表明, 与同类算法相比, 该算法具有较高的精度并兼顾优化解的多样性.

     

基于瓦片算法的并行 QR 分解及其实现

本文介绍了一种基于瓦片算法的稠密矩阵并行 QR 分解及其实现方法。瓦片算法的思想是将完整的矩阵分块,并使每个块内的数据连续存储。各个瓦片块先独立进行分解,其他块接收当前块分解产生的数据,来更新自身块内的矩阵。我们分别实现了串行瓦片算法和并行瓦片算法,采用基于 MPI 和 OpenMP 混合并行编程模型,在“元”超级计算机上验证了该并行算法,并与 PLASMA 软件包进行对比,程序效率和可扩展性优于 PLASMA。 在多个节点上运行时,展现了良好的扩展性。     

基于逻辑自映射的变尺度混沌粒子群优化算法*

针对基本粒子群优化算法的早熟收敛问题,提出了一种基于逻辑自映射的变尺度混沌粒子群优化算法。该算法在粒子群优化算法每次寻优结束时,采用逻辑自映射函数产生混沌序列,在已搜索到的精英粒子附近尝试搜索更优解并动态收缩搜索范围,在防止算法过早陷入局部最优的同时提高了算法搜索的精度。仿真结果表明,新算法在寻优成功率和平均最优值方面有很大提高,在求解包括欺骗性函数和高维函数在内的多种函数优化问题方面具有良好的效果。     

Acceleration of the back propagation through dynamic adaptation of the learning rate

Standard backpropagation, as with many gradient based optimization methods converges slowly as neural networks training problems become larger and more complex. In this paper, we present a new algorithm, dynamic adaptation of the learning rate to accelerate steepest descent. The underlying idea is to partition the iteration number domain into n intervals and a suitable value for the learning rate is assigned for each respective iteration interval. We present a derivation of the new algorithm and test the algorithm on several classification problems. As compared to standard backpropagation, the convergence rate can be improved immensely with only a minimal increase in the complexity of each iteration.     

稀疏约束图正则非负矩阵分解

非负矩阵分解(NMF)是在矩阵非负约束下的一种局部特征提取算法。为了提高识别率,提出了稀疏约束图正则非负矩阵分解方法。该方法不仅考虑数据的几何信息,而且对系数矩阵进行稀疏约束,并将它们整合于单个目标函数中。构造了一个有效的乘积更新算法,并且在理论上证明了该算法的收敛性。在ORL和MIT-CBCL人脸数据库上的实验表明了该算法的有效性。     

基于自适应惯性权重的均值粒子群优化算法

针对粒子收敛速度慢、搜索精度不高和算法性能在很大程度上依赖参数选取等缺点,提出了一种基于自适应惯性权重的均值粒子群优化算法。对算法中的惯性权重参数采用动态自适应变化方式,在迭代过程中根据粒子适应度差值将种群划分为三个等级,对不同等级的粒子采用不同的惯性权重策略,使粒子能根据自己所处的位置选择合适的惯性权重值,更快地收敛到全局最优位置;同时分别用个体极值和全局极值的线性组合取代PSO算法中的全局最优位置与个体最优位置。通过实验仿真与对比,验证了新算法性能优于标准PSO及其它一些改进的PSO算法,能够用较少的迭代次数找到最优解,具有更快的收敛速度和更高的收敛精度。     

改进的菌群算法研究

为了提高菌群寻优算法（ Bacterial Foraging Optimization, BFO）的搜索能力和解决多峰值复杂适应度函数模型避免过早收敛的问题,文中对原始菌群算法进行改进,提出多峰值菌群算法。将寻优过程分成两个时期,前期和原始菌群算法相同,在菌群收敛的后期,加入峰值数目和区间的判断,将区间编号,保证区间内部单峰值;然后在区间内部迭代运行菌群搜索,独立寻优,在多峰值和较复杂模型的情况下进行研究和评估。实验表明,在收敛速度、收敛稳定性和寻找全局最优方面均优于原始菌群算法。     

Globally and superlinearly convergent algorithms for the solution of box-constrained optimization

Based on the identification technique of active constraints, we propose a Newton-like algorithm and a quasi-Newton algorithm for solving the box-constrained optimization problem. The two algorithms require only the solution of a lower-dimensional system of linear equations at each iteration. In the proposed quasi-Newton algorithm, we make use of an approximate direction derivative of the multiplier functions so that only first-order derivatives of the objective function are needed to evaluate. Under mild assumptions, global convergence of the two algorithms is established. In particular, locally quadratic convergence for the Newton-like algorithm and locally superlinear convergence for the quasi-Newton algorithm are obtained without assuming that the strict complementarity condition holds at the solution.     

Hierarchical gradient methods for nonlinear LSQ problems

The idea of hierarchical gradient methods for optimization is considered. It is shown that the proposed approach provides powerful means to cope with some global convergence problems characteristic of the classical gradient methods. Concerning global convergence problems, four topics are addressed: The detour effect, the problem of multiscale models, the problem of highly ill-conditioned objective functions, and the problem of local-minima traps related to ambiguous regions of attractions. The great potential of hierarchical gradient algorithms is revealed through a hierarchical Gauss-Newton algorithm for unconstrained nonlinear least-squares problems. The algorithm, while maintaining a superlinear convergence rate like the common conjugate gradient or quasi-Newton methods, requires the evaluation of partial derivatives with respect to only one variable on each iteration. This property enables economized consumption of CPU time in case the computer codes for the derivatives are intensive CPU consumers, e.g., when the gradient evaluations of ODE or PDE models are produced by numerical differentiation. The hierarchical Gauss-Newton algorithm is extended to handle interval constraints on the variables and its effectiveness demonstrated by computational results.     

一种新算法在基因表达谱聚类中的应用

聚类分析是从基因表达数据中提取生物医学信息的主要方法。针对基本粒子群优化算法易陷入局部极值和对可调参数敏感的问题,提出了一种新型粒子对算法来解决基因聚类问题。算法初始化四个粒子,随机分成两对,将K-均值快速聚类的结果作为每个粒子对中一个粒子的初始位置。在每次迭代中,粒子仅依靠自身速度和粒子对的最佳位置来完成自身更新。每个粒子对产生的精英粒子,组成一个新的粒子对,继续搜索,新粒子对的最优位置即为聚类算法的最优解。实验结果表明算法具有良好的同质性和差异性,且在计算时间和收敛速度方面具有相当的优势。