图像修复TV模型的快速算法研究

关于图像修复的全变分（ TV）模型的求解有很多方法。在图像修复的全变分（ TV）模型中,文中针对含有非光滑项的凸优化问题提出了一种基于交替方向乘子法（ ADMM）的快速求解算法。 ADMM方法对迭代公式中具体的子问题求解过程一般采用Gauss-Seidel方法,文中通过分析TV修复模型的性质,对ADMM算法进行了相应的改进,使得具体的数值求解可以用快速傅里叶变换方法,并证明了该算法的收敛性。实验结果表明,文中所提出的新算法与采用Gauss-Seidel迭代的方法相比较,不但修复效果更好,而且修复速度更快。     

基于交替方向乘子法的电力系统完全分布式动态经济调度方法

本文基于交替方向乘子法(alternating direction multiplier method,ADMM)提出了一种完全分布式的跨区域电力系统动态经济调度方法.其中的经济调度模型以整个系统的运行成本最小为目标,并满足各种系统运行约束.为了实现模型的分布式求解,本文利用交替方向乘子法将各区域之间的联系解耦,将整个系统的大型优化问题分解为各个区域内部的子优化问题,通过迭代求解每个区域的子问题即可得到整个系统的最优解.进一步地,本文算法取消了负责乘子更新的数据中心,实现了完全分布式的调度策略.同时,为了兼顾电力系统中时间断面之间的紧密联系,本文的经济调度模型采用了多时段优化方法.最后,本文对基于IEEE标准测试系统的3区域互联系统算例进行了分析,验证了本文的调度策略的有效性.     

求解正则化最小二乘问题的一个非精确交替方向乘子法

正则化最小二乘问题广泛出现在图像处理、统计学等领域中,交替方向乘子法(ADMM)是求解这个问题的一种有效方法.ADMM在每一步迭代过程中,都需要求解两个子问题,子问题能否有效地求解对整个算法的有效性有重要影响.在有些情形,精确求解子问题是不可能的,或者是需要花费很大代价的.由于这个原因,非精确地求解子问题的一类算法得到了发展.而已有的非精确类ADMM算法,在迭代过程中需要不断提高子问题解的精度,从而子问题迭代步数也越来越多,这就影响了整个算法的效率.这篇文章提出了一个不精确ADMM算法,该算法的特点是在迭代过程中,子问题的迭代步数是确定的,这克服了之前算法的不足.文章中的数值例子也说明了提出的算法是有效的.     

改进的迭代收缩阈值算法及其在量子状态估计中的应用

本文将含有稀疏干扰的量子状态估计问题, 转化为考虑量子状态的约束条件下, 分别求解密度矩阵的核范 数, 以及稀疏干扰l1范数的两个子问题的优化问题. 针对迭代收缩阈值算法(ISTA)所存在的收敛速度慢的问题, 通 过在两个子问题的迭代估计中, 引入一个加速算子, 对当前值与前一次值之差进行进一步的补偿, 来提高算法的迭 代速度(FISTA). 并将FISTA算法应用于求解含有稀疏干扰的量子状态估计中. 针对5个量子位的状态估计的仿真实 验, 将FISTA分别与ISTA、交替方向乘子法(ADMM)、不动点方程的ADMM算法(FP–ADMM), 以及非精确的ADMM 算法(I–ADMM)4种优化算法进行性能对比. 实验结果表明, FISTA算法具有更加优越的收敛速度, 并且能够得到更 小的量子状态估计误差.     

面向通用一致性优化的通信高效的异步ADMM算法

分布式交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)是求解大规模机器学习问题使用最广泛的方法之一。现有大多数分布式ADMM算法都基于完整的模型更新。随着系统规模及数据量的不断增长,节点间的通信开销逐渐成为限制分布式ADMM算法发展的瓶颈。为了减少节点间通信开销,提出了一种通信高效的通用一致性异步分布式ADMM算法(General Form Consensus Asynchronous Distributed ADMM,GFC-ADADMM),该算法通过分析高维稀疏数据集的特性,节点间利用关联模型参数代替完整模型参数进行通信,并对模型参数进行过滤以进一步减少节点间传输负载。同时结合过时同步并行(Stale Synchronous Parallel, SSP)计算模型、allreude通信模型及混合编程模型的优势,利用异步allreduce框架并基于MPI/OpenMP混合编程模型实现GFC-ADADMM算法,提高算法计算与通信效率。文中利用GFC-ADADMM算法求解稀疏logistic回归问题,实验测试表明,与现有分...     

面向无人机集群路径规划的智能优化算法综述

在电–气–热互联系统(EGHS)的联合优化愈受关注的背景下, 提出一种电–气–热互联系统分布式优化调度 框架. 首先, 以系统供能成本最小建立同时考虑气网及热网动态特性的日前调度模型. 其次, 针对电–气–热互联系 统含电、气、热3个子系统在分布式运算属三区(3-Block)优化问题因而难以利用常规分布式算法得到收敛解的问题, 提出基于交替方向乘子法(ADMM)的改进算法, 即强制平等的ADMM算法. 所提算法框架为内外层协调凸分布框 架, 外层为罚凸凹算法(PCCP), 内层为ADMM–FE算法. 此算法框架中, 外层优化利用罚凸凹过程将非凸气流方程 凸化为逐次迭代的二阶锥约束, 内层ADMM–FE算法求解外层凸化后的模型以得到收敛解. 最后, 通过算例仿真分 析对比了所提算法与传统ADMM算法及集中式优化算法的计算结果, 所得结果验证了所提模型以及优化算法框架 的有效性.     

一种基于ADMM的非光滑损失在线优化算法

交替方向乘子法（ADMM）在机器学习问题研究中已有一些高效的实际应用,但为了适应大规模数据的处理和求解非光滑损失凸优化问题,文中提出对原ADMM进行改进,得到了损失函数线性化的ADMM的在线优化算法。该在线算法相较原算法具有操作简单、计算高效等特点。通过详尽的理论分析,文中证明了新在线算法的收敛性,并得到其在一般凸条件下具有目前最优的Regret界以及随机收敛速度。最后在与当今流行在线算法的对比实验中验证了新在线算法的高效可行性。     

图像上梯度相关的优化问题快速算法

针对图像处理中目标函数为对图像梯度的约束,形式为正则项与保真项之和的优化问题,提出了一种对该优化问题的变形形式,并给出了基于交替方向乘子法(alternatingdirectionmethodofmultipliers,ADMM)的优化算法进行求解.在约束条件下采用每个图像中的最小单元上的分段式,使得在每步迭代中的每个子问题可以分化为在每个最小单元上的二元优化问题,从而可直接获得优化问题的最优解.所提出的优化形式与优化算法可以控制每步迭代的时间复杂度在O(N),其中N为优化问题在该图像区域中最小单元的个数,还可进一步根据图像的分割进行并行化.文中给出了2个图像上比较经典的优化问题:L0模优化问题和Poisson图像编辑的优化算法.与现有的基于迭代算法相比,文中算法在达到相似结果的同时,可具有更快计算速度与更小的内存消耗.     

基于无网格压缩感知的DOA估计算法

应用传统的压缩感知理论对天线阵列信号的波达方向(Direction-of-arrival,DOA) 进行估计,存在基的失配问题。基于交替方向乘子法 (Alternative Direction Method of Multiplier,ADMM) 的无网格压缩感知(Grid-less Compressive Sensing) 技术能够解决该问题,但仍存在收敛速度慢的缺陷。针对该缺陷, 提出带自适应惩罚项的ADMM (ADMM with adaptive penalty,AP-ADMM)算法,即根据输入信号的噪声功率,自适应地选择惩罚项的初始值;同时在算法迭代求解的过程中,自适应地对目标函数的惩罚项进行调整。与传统算法相比,在保证收敛精度和DOA的恢复成功概率的条件下,带自适应惩罚项的ADMM算法收敛速率明显加快。仿真结果验证了新算法的有效性。     

基于交替方向乘子法的非光滑损失坐标优化算法

交替方向乘子法(ADMM)在机器学习问题中已有一些实际应用。针对大规模数据的处理和非光滑损失凸优化问题,将镜面下降方法引入原ADMM批处理算法,得到了一种新的改进算法,并在此基础上提出了一种求解非光滑损失凸优化问题的坐标优化算法。该算法具有操作简单、计算高效的特点。通过详尽的理论分析,证明了新算法的收敛性,在一般凸条件下其具有目前最优的收敛速度。最后与相关算法进行了对比,实验结果表明该算法在保证解稀疏性的同时拥有更快的收敛速度。     

高效求解三维装箱问题的剩余空间最优化算法

为实现三维装箱问题的高效求解，提出了一个三维的剩余空间最优化算法（Three-Dimensional Residual-Space-Optimized Algorithm，3D-RSO）。在满足3个著名约束的条件下，该算法将三维问题转化为带有高度约束的二维问题，通过对箱子放置后的剩余空间状态分析，提出了基于概率较优的空间分割方法和箱子布置规则。相比于传统算法，3D-RSO在求解过程中不需要任何的预处理和搜索操作，是一种最坏计算复杂度为[O(2n2)]的直接求解算法。针对强异构体的实验表明，该算法能够在极短的时间内对算例进行高效求解，适合应用在大规模或者需要被快速求解的三维装箱问题中。     

Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time

Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A ^* algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson’s preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A ^* to reach optimal schedules, while these instances are not solved by A ^* otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.     

Parametric optimization and optimal control using algebraic geometry methods

We present two algebraic methods to solve the parametric optimization problem that arises in non-linear model predictive control. We consider constrained discrete-time polynomial systems and the corresponding constrained finite-time optimal control problem. The first method is based on cylindrical algebraic decomposition. The second uses Gröbner bases and the eigenvalue method for solving systems of polynomial equations. Both methods aim at moving most of the computational burden associated with the optimization problem off-line, by pre-computing certain algebraic objects. Then, an on-line algorithm uses this pre-computed information to obtain the solution of the original optimization problem in real time fast and efficiently. Introductory material is provided as appropriate and the algorithms are accompanied by illustrative examples.     

基于二点组合算法的旅行商问题应用性能分析

旅行商问题模型应用广泛,其求解策略的研究具有重要的理论和实践意义。为高效快速解决旅行商问题,给出一种基于环路改造的二点组合算法,即选取一条汉密尔顿环路作为目标解,任取两个顶点删除与之相关的边形成2至4个环路片断,对这些环路片断进行排列组合,尝试寻找更优的解替换目标解的方法。仿真实验结果表明,该算法的计算效率和计算误差性能皆优于蚁群算法,实际应用结果也表明本算法在解决中小规模旅行商问题时的实用性。因此,本算法具有较强的理论价值和较强的实用价值,可以较好地完成中等规模的TSP问题,且适用于一系列的优化组合问题。     

Modified augmented Lagrangian coordination and alternating direction method of multipliers with parallelization in non-hierarchical analytical target cascading

Analytical Target Cascading (ATC) is a decomposition-based optimization methodology that partitions a system into subsystems and then coordinates targets and responses among subsystems. Augmented Lagrangian with Alternating Direction method of multipliers (AL-AD), one of efficient ATC coordination methods, has been widely used in both hierarchical and non-hierarchical ATC and theoretically guarantees convergence under the assumption that all subsystem problems are convex and continuous. One of the main advantages of distributed coordination which consists of several non-hierarchical subproblems is that it can solve subsystem problems in parallel and thus reduce computational time. Therefore, previous studies have proposed an augmented Lagrangian coordination strategy for parallelization by eliminating interactions among subproblems. The parallelization is achieved by introducing a master problem and support variables or by approximating a quadratic penalty function to make subproblems separable. However, conventional AL-AD does not guarantee convergence in the case of parallel solving. Our study shows that, in parallel solving using targets and responses of the current iteration, conventional AL-AD causes mismatch of information in updating the Lagrange multiplier. Therefore, the Lagrange multiplier may not reach the optimal point, and as a result, increasing penalty weight causes numerical difficulty in the augmented Lagrangian coordination approach. To solve this problem, we propose a modified AL-AD with parallelization in non-hierarchical ATC. The proposed algorithm uses the subgradient method with adaptive step size in updating the Lagrange multiplier and also maintains penalty weight at an appropriate level not to cause oscillation. Without approximation or introduction of an artificial master problem, the modified AL-AD with parallelization can achieve similar accuracy and convergence with much less computational cost compared with conventional AL-AD with sequential solving.     

一种LS-SVM在线式短时交通流预测方法

针对最小二乘支持向量机用于短时交通流在线预测时存在的计算复杂性问题,结合短交通流观测数据的特点,提出了一种最小二乘支持向量机在线式短时交通流预测算法。通过改进最小二乘支持向量机模型结构风险形式,消除了模型中的偏置项,从而简化了在线学习过程中Lagrange乘子的求解过程,利用训练数据集滑动时间窗口的移动来控制新样本的加入和旧样本的移除,通过线性运算即可求得由训练样本集的更新而引起Lagrange乘子的变化量,进而完成预测模型的在线更新。仿真结果表明,相对于已有算法,所提算法在保证预测精度的条件下,具有更低的计算复杂度,能够将在线模型更新时间平均降低了约62.64%。     

柔性Flow-Shop调度的遗传算法优化

柔性Flow-shop调度问题（Flexible Flow-shop Scheduling Problem,FFSP）是一般Flow-shop调度问题的推广,由于在某些工序上存在并行机器,所以比一般的Flow-shop调度问题更复杂。为了有效地解决柔性Flow-shop调度问题,用遗传算法求解,给出了一种改进的编码方法,能够保证个体的合法性;并根据编码方法提出了矩阵解码方法。最后以某汽车发动机厂金加工车间的生产调度实例进行仿真,通过比较表明了算法的有效性。     

一种基于优化状态转换信任度的增强型学习算法

针对增强型算法中求解目标状态问题，提出了反映当前状态与目标状态的距离和转换代价的优化模型，设计了基于优化状态转换信任度的增强型学习算法COSTRIL。算法定义了优化状态信任度函数，设计了优化状态信任度函数的更新学习规则。COSTRLA用于求解迷宫问题，表明了算法在处理目标状态问题时比传统的增强型学习算法更加有效。     

Bi-level programming model and hybrid genetic algorithm for flow interception problem with customer choice

This paper investigates how to optimize the facility location strategy such as to maximize the intercepted customer flow, while accounting for “flow-by” customers’ path choice behaviors and their travel cost limitation. A bi-level programming static model is constructed for this problem. An heuristic based on a greedy search is designed to solve it. Consequently, we proposed a chance constrained bi-level model with stochastic flow and fuzzy trip cost threshold level. For solving this uncertain model more efficiently, we integrate the simplex method, genetic algorithm, stochastic simulation and fuzzy simulation to design a hybrid intelligent algorithm. Some examples are generated randomly to illustrate the performance and the effectiveness of the proposed algorithms.