An outer approximation algorithm for equilibrium problems in Hilbert spaces

We introduce an algorithm for solving non-smooth equilibrium problems in real Hilbert spaces. At each iteration, a regularized proximal-like equilibrium problem on a suitable outer approximation of the original constraint set is considered. We prove, under standard assumptions, that the sequence generated by the algorithm converges weakly to a solution of the problem. Some numerical experience with the algorithm is reported.     

Two stochastic optimization algorithms for convex optimization with fixed point constraints

Two optimization algorithms are proposed for solving a stochastic programming problem for which the objective function is given in the form of the expectation of convex functions and the constraint set is defined by the intersection of fixed point sets of nonexpansive mappings in a real Hilbert space. This setting of fixed point constraints enables consideration of the case in which the projection onto each of the constraint sets cannot be computed efficiently. Both algorithms use a convex function and a nonexpansive mapping determined by a certain probabilistic process at each iteration. One algorithm blends a stochastic gradient method with the Halpern fixed point algorithm. The other is based on a stochastic proximal point algorithm and the Halpern fixed point algorithm; it can be applied to nonsmooth convex optimization. Convergence analysis showed that, under certain assumptions, any weak sequential cluster point of the sequence generated by either algorithm almost surely belongs to the solution set of the problem. Convergence rate analysis illustrated their efficiency, and the numerical results of convex optimization over fixed point sets demonstrated their effectiveness.     

Efficient Euclidean projections via Piecewise Root Finding and its application in gradient projection

Recently, the gradient (subgradient) projection method, especially by incorporating the idea of Nesterov's method, has aroused more and more attention and achieved great successes on constrained optimization problems arising in the field of machine learning, data mining and signal processing. In the gradient projection method, a critical step is how to efficiently project a vector onto a constraint set. In this paper, we propose a unified method called Piecewise Root Finding (PRF) to efficiently calculate Euclidean projections onto three typical constraint sets: ?₁-ball, Elastic Net (EN) and the Intersection of a Hyperplane and a Halfspace (IHH). In our PRF method, we first formulate a Euclidean projection problem as a root finding problem. Then, a Piecewise Root Finding algorithm is applied to find the root and global convergence is guaranteed. Finally, the Euclidean projection result is obtained as a function of the found root in a closed form. Moreover, the sparsity of the projected vector is considered, leading to reduced computational cost for projection onto the ?₁-ball and EN. Empirical studies demonstrate that our PRF algorithm is efficient by comparing it with several state of the art algorithms for Euclidean projections onto the three typical constraint sets mentioned above. Besides, we apply our efficient Euclidean projection algorithm (PRF) to the Gradient Projection with Nesterov's Method (GPNM), which efficiently solves the popular logistic regression problem with the ?₁-ball/EN/IHH constraint. Experimental results on real-world data sets indicate that GPNM has a fast convergence speed.     

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…     

多智能体系统的多步近似次梯度随机投影优化算法

基于切换网络下带有随机时延和随机通讯噪声的多智能体系统模型,提出分布式多步近似次梯度随机投影算法,并对算法的收敛性进行分析.首先,利用网络扩维的方法将含随机时延的通讯网络转化为无时延网络;其次,提出近似次梯度概念,并设计多步近似次梯度随机批量投影算法,批量随机投影可以避免在实际问题中整体约束集合不易获得而导致投影算子不...     

Consensus-based distributed optimisation of multi-agent networks via a two level subgradient-proximal algorithm

This paper presents a consensus-based stochastic subgradient algorithm for multi-agent networks to minimise multiple convex but not necessarily differential objective functions, subject to an intersection set of multiple closed convex constraint sets. Compared with the existing results an alternative subgradient algorithm is first introduced based on two level subgradient iterations, where the first level is to minimise the component functions, and the second to enforce the iterates not oscillate from the constraint set wildly. In addition, a distributed consensus-based type of the proposed subgradient algorithm is constructed within the framework of multi-agent networks for the case when the iteration index of local objective functions and local constraint sets is not homologous. Detailed convergence analysis of the proposed algorithms is established using matrix theories and super-martingale convergence theorem. In addition, a pre-step convergence factor is obtained in this study to characterise the distance between the iterations and the optimal set, while some existing literatures only present a convergence work. Simulation results are given to demonstrate the effectiveness of the developed theoretical results.     

大规模图上具有约束的多起点路径规划算法

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足。因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性。实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解。     

多个体切换网络分布式量化次梯度优化算法

由于已有的分布式次梯度算法大多基于理想的假设：网络拓扑是有向平衡的,构成网络的个体间通信的是各个个体某个状态变量的完全精确的信息。针对更一般的非平衡切换网络以及实际生活中网络通道的带宽限制,提出一种基于有限量化信息通信的切换网络分布式量化次梯度优化算法。在非平衡切换网络中,通过设计具有有限量化水平的一致量化器使所有信息在发送之前都经过量化,利用非二次李雅普诺夫函数方法,证明了所提出的多个体分布式量化次梯度优化算法的收敛性。最后仿真实例验证了所提算法的有效性,而且通过调节量化水平参数,在相同的带宽条件下,可提高信息传输速率,使网络中的个体更快地达到一致。该方法弱化了对刻画网络拓扑的邻接矩阵的假设及对网络带宽的要求,更具实用性。     

支持向量机初始化的常数模盲均衡算法仿真

为了提高常数模盲均衡算法的收敛速度并避免算法收敛至局部极小,提出了一种支持向量机初始化的常数模盲均衡算法.新算法采用一小段初始数据,利用支持向量机,将盲均衡问题转化为全局最优的支持向量回归问题,对盲均衡器的初始权向量进行设定,而后切换至计算量较小的常数模算法.采用浅海水声信道对新算法进行了计算机仿真,结果表明:支持向量机初始化阶段收敛速度快;切换至常数模算法后性能稳定.该算法适合应用于快衰落水声信道中通信数据的实时恢复.     

Distributed continuous‐time algorithm for a general nonsmooth monotropic optimization problem

This paper investigates a general monotropic optimization problem for continuous‐time networks, where the global objective function is a sum of local objective functions that are only known to individual agent, and general constraints are taken into account, including local inequality constraints, global equality constraint, and local feasible constraints. In addition, all functions involved in the objective functions and inequality constraints are not necessarily differentiable. To solve the problem, a distributed continuous‐time algorithm is designed using subgradient projections, and it is shown that the proposed algorithm is well defined in the sense that the existence of its solutions can be guaranteed. Furthermore, it is proved that the algorithm converges to an optimal solution for the general monotropic optimization problem. Finally, a simulation example is provided for validating the theoretical result.     

带有随机改进Barzilai-Borwein步长的小批量稀疏随机方差缩减梯度法

为了更好地应对当今时代的大规模高维稀疏数据集,融合BB方法、小批量算法与随机方差缩减梯度法(SVRG)优势,提出一种带有随机改进Barzilai-Borwein步长的小批量稀疏随机方差缩减梯度法(MSSVRG-R2BB)。首先,在SVRG外循环中全梯度计算的基础上加入L₁范数次梯度设计出一种稀疏近似梯度用于内循环,得到一种稀疏的SVRG算法(SSVRG)。在此基础上,在小批量的稀疏随机方差缩减梯度法中使用随机选取的改进BB方法自动计算、更新步长,解决了小批量算法的步长选取问题,拓展得到MSSVRG-R2BB算法。数值实验表明,在求解大规模高维稀疏数据的线性支持向量机(SVM)问题时,MSSVRG-R2BB算法不仅可以减小运算成本、更快达到收敛上界,同时能达到与其他先进的小批量算法相同的优化水平,并且对于不同的初始参数选取表现稳定且良好。     

Training neural networks by stochastic optimisation

We present a stochastic learning algorithm for neural networks. The algorithm does not make any assumptions about transfer functions of individual neurons and does not depend on a functional form of a performance measure. The algorithm uses a random step of varying size to adapt weights. The average size of the step decreases during learning. The large steps enable the algorithm to jump over local maxima/minima, while the small ones ensure convergence in a local area. We investigate convergence properties of the proposed algorithm as well as test the algorithm on four supervised and unsupervised learning problems. We have found a superiority of this algorithm compared to several known algorithms when testing them on generated as well as real data.     

An Extragradient Algorithm for Monotone Variational Inequalities

A new iterative algorithm is proposed for solving the variational inequality problem with a monotone and Lipschitz continuous mapping in a Hilbert space. The algorithm is based on the following two well-known methods: the Popov algorithm and so-called subgradient extragradient algorithm. An advantage of the algorithm is the computation of only one value of the inequality mapping and one projection onto the admissible set per one iteration. The weak convergence of sequences generated by the proposed algorithm is proved.     

A subgradient selection method for minimizing convex functions subject to linear constraints

A readily implementable subgradient algorithm is given for minimizing a convex, but not necessarily differentiable, functionf subject to a finite number of linear constraints. It is shown that the algorithm converges to a solution, if any. The convergence is finite iff is piecewise linear.     

An improved stepsize of the subgradient algorithm for solving the lagrangian relaxation problem

The Lagrangian relaxation approach has been successfully applied to many large-scale mathematical programming problems. The Lagrangian relaxation problem itself is a non-differentiable optimization problem. One of the methods for solving such problem is the subgradient algorithm. In this paper, we propose an improved stepsize of the subgradient algorithm for solving the Lagrangian relaxation problem. Our version of the algorithm may significantly improve the rate of convergence of subgradient algorithm when applied to the solution of Lagrangian relaxation problem. An illustrative numerical example is also given.     

Dynamic location problem under uncertainty with a regret‐based measure of robustness

In this paper, we present a dynamic uncapacitated facility location problem that considers uncertainty in fixed and assignment costs as well as in the sets of potential facility locations and possible customers. Uncertainty is represented via a set of scenarios. Our aim is to minimize the expected total cost, explicitly considering regret. Regret is understood as a measure, for each scenario, of the loss incurred for not choosing that scenario's optimal solution if that scenario indeed occurred. We guarantee that the regret for each scenario is always upper bounded. We present a mixed integer programming model for the problem and we propose a solution approach based on Lagrangean relaxation integrating a local neighborhood search and a subgradient algorithm to update Lagrangean multipliers. The problem and the solutions obtained are first analyzed through the use of illustrative examples. Computational results over sets of randomly generated test problems are also provided.     

A new method for camera stratified self-calibration under circular motion

We consider the stratified self-calibration (affine and metric reconstruction) problem from images acquired with a camera with unchanging internal parameters undergoing circular motion. The general stratified method (modulus constraints) is known to fail with this motion. In this paper we give a novel constraint on the plane at infinity in projective reconstruction for circular motion, the constant inter-frame motion constraint on the plane at infinity between every two adjacent views and a fixed view of the motion sequences, by making use of the facts that in many commercial systems rotation angles are constant. An initial solution can be obtained by using the first three views of the sequence, and Stratified Iterative Particle Swarm Optimization (SIPSO) is proposed to get an accurate and robust solution when more views are at hand. Instead of using the traditional optimization algorithm as the last step to obtain an accurate solution, in this paper, the whole motion sequence information is exploited before computing the camera calibration matrix, this results in a more accurate and robust solution. Once the plane at infinity is identified, the calibration matrices of the camera and a metric reconstruction can be readily obtained. Experiments on both synthetic and real image sequence are given, showing the accuracy and robustness of the new algorithm.     

Two hybrid algorithms for solving split equilibrium problems

The paper considers split equilibrium problems (EPs) in Hilbert spaces and proposes two hybrid algorithms for finding their solution approximations. Three methods including the diagonal subgradient method, the projection method and the proximal method have been used to design the algorithms. Using the diagonal subgradient method for EPs has allowed us to reduce complex computations on bifunctions and feasible sets. The first algorithm is designed with two projections on feasible set and with the prior knowledge of operator norm while the second algorithm is simpler in computations where only one projection on feasible set needs to be implemented and the information of operator norm is not necessary to construct solution approximations. The strongly convergent theorems are established under suitable assumptions imposed on equilibrium bifunctions. The computational performance of the proposed algorithms over existing methods is also illustrated by several preliminary numerical experiments.     

改进的多载波码分多址系统多址干扰抑制算法

为了抑制多载波码分多址（MC-CDMA）系统中的多址干扰,提出了一种基于自适应并行次梯度投影的多址干扰抑制算法。它首先根据接收端信号模型建立包含最优干扰抑制滤波器系数并具有随机属性的凸集,然后运用并行次梯度投影的思想将对该凸集的投影转化为对多个闭合半平面的投影,最后将更新后的干扰抑制滤波器系数矢量投影到限定集合上。理论分析和仿真结果表明,该算法具有快速收敛性和稳定的干扰抑制性能,在不同的噪声强度下都具有较低的误码率和较高的鲁棒性。     

定步长压缩感知锥束CT重建算法

针对锥束CT成像系统中投影数据不完全的图像重建问题,提出了一种定步长压缩感知锥束CT重建算法。首先将锥束CT重建问题归结为投影数据均方误差作为数据保真项、全变分作为正则项的无约束优化问题,分析目标函数的Lipschitz连续性;然后近似计算Lipschitz常数,求出梯度下降步长,利用梯度下降法进行重建;最后对CT投影数据采用联合代数重建算法更新重建图像。在每次迭代过程中调整梯度下降步长,提高重建算法的收敛速度。Shepp-Logan模型的无噪声实验结果表明,该算法的重建图像信噪比分别比联合代数重建算法、自适应最速下降-凸集投影算法、BB梯度投影算法的重建图像信噪比高出13.7728dB、12.8205dB、7.3580dB。仿真试验表明该重建算法提高了收敛速度,同时减少了重建图像的相对误差,极大提高了用少量投影数据重建的图像质量。