Incremental subgradient method for nonsmooth convex optimization with fixed point constraints

This paper proposes an incremental subgradient method for solving the problem of minimizing the sum of nondifferentiable, convex objective functions over the intersection of fixed point sets of nonexpansive mappings in a real Hilbert space. The proposed algorithm can work in nonsmooth optimization over constraint sets onto which projections cannot be always implemented, whereas the conventional incremental subgradient method can be applied only when a constraint set is simple in the sense that the projection onto it can be easily implemented. We first study its convergence for a constant step size. The analysis indicates that there is a possibility that the algorithm with a small constant step size approximates a solution to the problem. Next, we study its convergence for a diminishing step size and show that there exists a subsequence of the sequence generated by the algorithm which weakly converges to a solution to the problem. Moreover, we show the whole sequence generated by the algorithm with a diminishing step size strongly converges to the solution to the problem under certain assumptions. We also give examples of real applied problems which satisfy the assumptions in the convergence theorems and numerical examples to support the convergence analyses.     

提高链式Lin-kernighan算法性能的策略

Lin-Kernighan算法作为一种高效的组合优化问题优化算法，普遍应用于各种求解组合优化难题的算法中，尤其是旅行商问题的求解。通过对该类问题的可化简性论述，分析并建立了该类问题初始边集的概率化简模型，经实验分析方式确定了模型中的先验性概率值，并建立旅行商化简初始边集的随机算法。将该算法建立的边集作为链式Lin-Kernighan算法的参照优化边集，大幅度提高了链式Lin-Kernighan算法的求解性能，在与多种智能算法结合中取得了较好的收敛效果。     

非平衡有向网络下带约束的连续时间分布式优化算法设计EI北大核心CSCD

本文基于权重不平衡有向网络,对一类分布式约束优化问题进行研究,其中全局目标函数等于具有李普希兹梯度的强凸目标函数之和,并且每个智能体的状态都有一个局部约束集.每个智能体仅知道自身的局部目标函数和非空约束集.本文的目标是用分布式方法求解该问题的最优解.针对优化问题,提出了一种新的分布式投影梯度连续时间协调算法,利用拉普拉斯矩阵的零特征值对应的左特征向量消除了图的不平衡性.在某些假设下,结合凸分析理论和李雅普诺夫稳定性理论,证明了算法能够获得问题的最优解.最后,通过仿真验证了算法的有效性.     

Self-adaptive ergodic algorithm for equilibrium problems over the fixed point set

ABSTRACT

We introduce a new ergodic algorithm for solving equilibrium problems over the fixed point set of a nonexpansive mapping. In contrast to the existing one in Kim [The Bruck's ergodic iteration method for the Ky Fan inequality over the fixed point set. Int. J. Comput. Math. 94 (2017), pp. 2466–2480], our algorithm uses self-adaptive step sizes. Thanks to that, the proposed algorithm converges under milder conditions. Moreover, at each step of our algorithm, instead of solving strongly convex problems, we only have to compute a subgradient of a convex function. Hence, our algorithm has lower computational cost.     

基于混合预测策略与改进社会学习优化算法的动态多目标优化方法

近年来,国内外学者针对基于预测的动态多目标优化算法开展了深入研究,并提出了一系列有效的算法,然而已有的研究工作通常采用单一的预测策略,使得算法不能有效地应对剧烈的环境变化。针对上述问题,提出了一种基于混合预测策略与改进社会学习优化算法的动态多目标优化方法。具体地,当环境发生变化时,该方法首先基于代表性个体预测策略生成一部分群体;其次,基于拐点预测策略生成一部分新群体,特别地,为了提高种群的多样性,根据算法迭代的历史信息和环境变化情况随机地生成一定数量的新个体;为了提高问题的求解效率,对社会学习优化算法进行了改进,为每个进化空间设计了适用于动态多目标优化问题的算子;最后,将混合预测策略与改进的社会学习优化算法结合,构成了一种新的动态多目标优化方法。以FDA、DMOP和F函数集作为实验测试函数集,与四种代表性算法进行了性能对比;并以反向世代距离(inverted generational distance, IGD)对该方法的性能进行了深入的分析。实验结果表明所提方法具有较好的收敛性和鲁棒性。     

随机性优化算法有效性定量对比评价方法

针对随机性优化算法寻优结果不可重复的特点,为该类优化算法提供了一种定量对比评价算法有效性的方法。该方法针对单个或一组测试函数的多次优化结果进行统计分析,得到一个能够在概率意义上定量表征不同随机性算法求解单个或一组测试函数的有效性优劣关系的因子。利用该方法,对采用同步或异步全局最优粒子信息更新模式的两种标准粒子群优化算法（PSO）版本进行有效性对比评价,给出了同步和异步模式PSO算法求解无约束单目标连续变量优化问题的有效性优劣关系。     

基于最优传输理论的高质量点云重采样方法

目前通过3D扫描仪获取的点云仍旧存在一些缺陷:点云含有噪声,点云在不同方向上分布不均匀等.本文针对上述问题开展研究.主要工作为提出一种新的算法用于在点云上进行高质量的重采样,即使用较为稀疏的重采样点集去表达较为密集的原始点云的几何形状,同时重采样点集的分布可以满足用户预先指定的目标分布,并具备一定的蓝噪声性质.在最优传...     

A new approach for online multiobjective optimization of mechatronic systems

We present a new concept for online multiobjective optimization and its application to the optimization of the operating point assignment for a doubly-fed linear motor. This problem leads to a time-dependent multiobjective optimization problem. In contrast to classical optimization where the aim is to find the (global) minimum of a single function, we want to simultaneously minimize k objective functions. The solution to this problem is given by the set of optimal compromises, the so-called Pareto set. In the case of the linear motor, there are two conflicting aims which both have to be maximized: the degree of efficiency and the inverter utilization factor. The objective functions depend on velocity, force and power, which can be modeled as time-dependent parameters. For a fixed point of time, the entire corresponding Pareto set can be computed by means of a recently developed set-oriented numerical method. An online computation of the time-dependent Pareto sets is not possible, because the computation itself is too complex. Therefore, we combine the computation of the Pareto set with numerical path following techniques. Under certain smoothness assumptions the set of Pareto points can be characterized as the set of zeros of a certain function. Here, path following allows to track the evolution of a given solution point through time.     

Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces

Proximal splitting algorithms for monotone inclusions (and convex optimization problems) in Hilbert spaces share the common feature to guarantee for the generated sequences in general weak convergence to a solution. In order to achieve strong convergence, one usually needs to impose more restrictive properties for the involved operators, like strong monotonicity (respectively, strong convexity for optimization problems). In this paper, we propose a modified Krasnosel'ski?–Mann algorithm in connection with the determination of a fixed point of a nonexpansive mapping and show strong convergence of the iteratively generated sequence to the minimal norm solution of the problem. Relying on this, we derive a forward–backward and a Douglas–Rachford algorithm, both endowed with Tikhonov regularization terms, which generate iterates that strongly converge to the minimal norm solution of the set of zeros of the sum of two maximally monotone operators. Furthermore, we formulate strong convergent primal–dual algorithms of forward–backward and Douglas–Rachford-type for highly structured monotone inclusion problems involving parallel-sums and compositions with linear operators. The resulting iterative schemes are particularized to the solving of convex minimization problems. The theoretical results are illustrated by numerical experiments on the split feasibility problem in infinite dimensional spaces.     

面向置换检验的冗余对比模式过滤算法

置换检验方法在进行对比模式挖掘时,返回结果中存在许多冗余对比模式。利用Charm方法挖掘样本集合中的对比模式,提出基于固定属性置换的FSPRP和FEPRP算法,依次为不同长度的对比模式构建零分布,从而过滤冗余对比模式。FSPRP算法通过生成一定数量的置换样本集合构建零分布,FEPRP算法则通过计算每个模式的对比性度量值分布合并建立零分布。实验结果表明,FSPRP和FEPRP算法相较于比较约束法能够过滤较多数量的冗余对比模式,并且FEPRP算法生成的零分布更接近精确零分布。     

求解约束优化问题的改进灰狼优化算法

针对基本灰狼优化(GWO)算法存在求解精度低、收敛速度慢、局部搜索能力差的问题,提出一种改进灰狼优化(IGWO)算法用于求解约束优化问题。该算法采用非固定多段映射罚函数法处理约束条件,将原约束优化问题转化为无约束优化问题,然后利用IGWO算法对转换后的无约束优化问题进行求解。在IGWO算法中,引入佳点集理论生成初始种群,为算法全局搜索奠定基础;为了提高局部搜索能力和加快收敛,对当前最优灰狼个体执行Powell局部搜索。采用几个标准约束优化测试问题进行仿真实验,结果表明该算法不仅克服了基本GWO的缺点,而且性能优于差分进化和粒子群优化算法。     

遗传算法的全局动力学形态分析

目前，对遗传算法的运行机理分析大都集中在算法的极限收敛性等问题，对算法的全局动力学形态研究较少．从一个具有代表性的、简化的2—bit问题入手，可以对遗传算法中常用的各种进化算子及其组合进行形式化描述，从而全面分析GA的全局动力学形态．针对各种参数的选取，分别建立了4个数学模型．通过分析这些模型中各个不动点的吸引性，揭示出不同进化算子对动力学形态的影响．对于这个问题，证明了算法的全局收敛性．并指出，当存在两个被此竞争的局部极值点时，模型中只有两个吸引点和一个鞍点(或排斥点)，不存在其他的不动点或周期点．算法的收敛结果完全由初始条件处于状态空间中的位置所决定，相应的收敛区域的比例完全由模型的参数决定．     

离散萤火虫优化算法求解概率旅行商问题

对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解.其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能.实验中用TSPLIB中的经典实例进行测试来验证其可行性.考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较.实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值.     

Subgradient-based feedback neural networks for non-differentiable convex optimization problems

1 Introduction Optimization problems arise in a broad variety of scientific and engineering applica- tions. For many practice engineering applications problems, the real-time solutions of optimization problems are mostly required. One possible and very pr…     

Non-smooth DC-constrained optimization: constraint qualification and minimizing methodologies

This work concerns the study of a constraint qualification for non-smooth DC-constrained optimization problems, as well as the design and convergence analysis of minimizing algorithms to address the task of computing a stationary/critical point for problems of this class. Specialized algorithms for DC programming approximate the non-convex optimization problem by a sequence of convex subproblems, obtained by linearizing the second components of the involved DC (difference of convex) functions. We propose new approaches that define trial points as inexact solutions of such convex subproblems. This is a property of practical interest that substantially reduces the computational burden to compute a stationary/critical point of non-smooth DC-constrained optimization problems. One variant of the proposed algorithmic patterns is numerically assessed on a DC reformulation of an energy management problem considering a smart-grid controlled by a local actor (follower) and its interaction with a global actor (leader) in the power system.     

D.C. optimization approach to robust control: Feasibility problems

The feasibility problem for constant scaling in output feedback control is considered. This is an inherently difficult problem since the set of feasible solutions is non-convex and may be disconnected. Nevertheless, we show that this problem can be reduced to the global minimization of a concave function over a convex set, or alternatively, to the global minimization of a convex program with an additional reverse convex constraint. Thus this feasibility problem belongs to the realm of d.c. optimization, a new field which has recently emerged as an active promising research direction in nonconvex global optimization. By exploiting the specific d.c. structure of the problem, several algorithms are proposed which at every iteration require solving only either convex or linear subproblems. Analogous algorithms with new characterizations are proposed for the bilinear matrix inequality (BMI) feasibility problem.     

一类非线性极小极大问题的粒子群-邻近点算法

针对每个分量函数都是凸函数的离散型非线性极小极大问题,提出一种全局收敛的粒子群-邻近点混合算法。该算法利用极大熵函数将极小极大问题转化为一个光滑函数的无约束凸优化问题;利用邻近点算法为外层算法,内层算法采用粒子群算法来优化此问题;数值结果表明,该算法数值稳定性好、收敛快,是求解此类非线性极小极大问题的一种有效算法。     

A new real-coded stochastic Bayesian optimization algorithm for continuous global optimization

Estimation of distribution algorithms are considered to be a new class of evolutionary algorithms which are applied as an alternative to genetic algorithms. Such algorithms sample the new generation from a probabilistic model of promising solutions. The search space of the optimization problem is improved by such probabilistic models. In the Bayesian optimization algorithm (BOA), the set of promising solutions forms a Bayesian network and the new solutions are sampled from the built Bayesian network. This paper proposes a novel real-coded stochastic BOA for continuous global optimization by utilizing a stochastic Bayesian network. In the proposed algorithm, the new Bayesian network takes advantage of using a stochastic structure (that there is a probability distribution function for each edge in the network) and the new generation is sampled from the stochastic structure. In order to generate a new solution, some new structure, and therefore a new Bayesian network is sampled from the current stochastic structure and the new solution will be produced from the sampled Bayesian network. Due to the stochastic structure used in the sampling phase, each sample can be generated based on a different structure. Therefore the different dependency structures can be preserved. Before the new generation is generated, the stochastic network’s probability distributions are updated according to the fitness evaluation of the current generation. The proposed method is able to take advantage of using different dependency structures through the sampling phase just by using one stochastic structure. The experimental results reported in this paper show that the proposed algorithm increases the quality of the solutions on the general optimization benchmark problems.     

有向网络分布式优化的Barzilai-Borwein梯度跟踪方法

本文研究有向网络上的分布式优化问题, 其全局目标函数是网络上所有光滑强凸局部目标函数的平均值.受Barzilai-Borwein步长改善梯度方法表现的启发, 本文提出了一种分布式Barzilai-Borwein梯度跟踪方法. 与文献中使用固定步长的分布式梯度算法不同, 所提出的方法中每个智能体利用其局部梯度信息自动地计算其步长. 通过同时使用行随机和列随机权重矩阵, 该方法避免了由特征向量估计引起的计算和通信. 当目标函数是光滑和强凸函数时, 本文证明了该算法产生的迭代序列可以线性地收敛到最优解. 对分布式逻辑回归问题的仿真结果验证了所提出的算法比使用固定步长的分布式梯度算法表现更好     

面向地图点集的多尺度层级ICP算法

地图点集具有点数多、结构复杂等特点,通常对其配准耗时严重,难以满足自主驾驶等情况下的实时性要求.利用多尺度层级化思想,提出一种多尺度层级ICP算法MSICP( Multi-scale Iterative Closest Points),提高了配准速度和精度.所提算法先对待配准图像点集进行稀疏化,随后将稀疏点集配准后的转换矩阵作为原稠密点集配准的转换矩阵初始值,最终实现对原始图像点集的ICP快速精确配准.实验结果表明,所提算法的配准速度及精度优于其他ICP算法,具有一定的实用价值.