基于Polyak步长的随机递归梯度算法

针对机器学习中一类有限光滑凸函数和的最小化问题,将随机递归梯度算法和Polyak步长结合,提出基于Polyak步长的随机递归梯度算法(SARAH-Polyak).分别在强凸和一般凸条件下证明了算法的线性收敛性.实验结果表明SARAH-Polyak算法的有效性.     

基于预测向心加速的生成对抗网络训练

为缓解生成对抗网络(generative adversarial networks, GAN)训练过程中的极限循环行为,本文受向心加速算法及Liang和Stokes (2019)的修正的预测方法 (modified predictive method, MPM)的启发,基于对匀速圆周运动的几何观察提出了预测向心加速算法(predictive centripetal acceleration algorithm, PCA).首先,在二元线性博弈(特殊的GAN)上证明了PCA的最后一次迭代收敛性.然后,将PCA分别与随机梯度下降(stochastic gradient descent, SGD)算法和自适应性矩估计(adaptive moment estimation, Adam)算法结合,提出了随机PCA (stochastic PCA, SPCA)和PCA-Adam用于实际训练GAN.最后,在二元线性博弈、多元Gauss分布以及CIFAR10和Celeb A数据集上的实验分别验证了所提出算法的有效性.     

求解无约束非线性规划问题的一个新的重开始共轭梯度算法的收敛性

Conjugate gradient optimization algorithms depend on the search directions.with different choices for the parameters in the search directions.In this note,by combining the nice numerical performance of PR and HS methods with the global convergence property of the class of conjugate gradient methods presented by HU and STOREY(1991),a class of new restarting conjugate gradient methods is presented.Global convergences of the new method with two kinds of common line searches,are proved .Firstly,it is shown that,using reverse modulus of continuity funciton and forcing function,the new method for solving unconstrained optimization can work for a continously differentiable function with Curry-Altman‘s step size rule and a bounded level set .Secondly,by using comparing technique,some general convergence propecties of the new method with other kind of step size rule are established,Numerical experiments show that the new method is efficient by comparing with FR conjugate gradient method.     

结合广义Armijo步长搜索的一类新的三项共轭梯度算法及其收敛特征

In this paper, we consider the convergence properties of a new class of three terms conjugate gradient methods with generalized Armijo step size rule for minimizing a continuously differentiable function f on R^π without assuming that the sequence {xk} of iterates is bounded. We prove that the limit infimum of ‖↓△f(xk)‖ is Zero. Moreover, we prove that, when f(x) is pseudo-convex (quasi-convex) function, this new method has strong convergence results: either xk→x* and x* is a minimizer (stationary point); or ‖xk‖→∞, arg min{f(x) :x∈R^n} =φ, and.f(xk) ↓ inf(f(x) : x∈R^n}. Combining FR, PR, HS methods with our new method, FR, PR, HS methods are modified to have global convergence property.Numerical result show that the new algorithms are efficient by comparing with FR,PR, HS conjugate gradient methods with Armijo step size rule.     

改进的OWL-QN方法解稀疏logistic回归问题

稀疏logistic回归,是机器学习中一类重要的问题,它在控制论、管理科学和互联网等领域有着广泛的应用.本文提出了一种改进的基于分象限学习的拟Newton算法来求解稀疏logistic回归问题.新算法采用著名的Barzilai-Borwein步长策略自适应地近似代替目标函数的Hesse阵,并利用目标函数的整体梯度信息来构造拟Newton向量.在适当的条件下,证明了新算法的全局收敛性.数值实验表明新算法是可行的,并且是有效的.     

基于梯度的自适应快速布谷鸟搜索算法

针对标准布谷鸟搜索(CS)算法存在全局搜索和局部搜索能力不平衡的缺点, 提出一种基于梯度的自适应快速布谷鸟搜索(GBAQCS)算法. 在改进的算法中, 针对偏好随机游动的步长, 在利用目标函数的梯度决定步长方向的基础上, 首先提出自适应搜索机制平衡了算法的全局搜索和局部搜索能力; 其次提出快速 搜索策略, 充分利用当前鸟巢信息进行精细化搜索, 从而提高算法的搜索精度和收敛速度. 实验结果表明, 相比其他算法, 所提出的改进策略使算法的全局搜索和局部搜索能力保持了相对的平衡, 并提高了算法的收敛性能.     

Stability Analysis for the Numerical Simulation of Hybrid Stochastic Differential Equations

This paper is mainly concerned with the exponential stability of a class of hybrid stochastic differential equations–stochastic differential equations with Markovian switching (SDEwMSs). It first devotes to reveal that under the global Lipschitz condition, a SDEwMS is pth (p ∈ (0,1)) moment exponentially stable if and only if its corresponding improved Euler-Maruyama(IEM) method is pth moment exponentially stable for a suitable step size. It then shows that the SDEwMS is pth(p ∈ (0,1)) moment exponentially stable or its corresponding IEM method with small enough step sizes implies the equation is almost surely exponentially stable or the corresponding IEM method, respectively. In that sense, one can infer that the SDEwMS is almost surely exponentially stable and the IEM method, no matter whether the SDEwMS is pth moment exponentially stable or the IEM method. An example is demonstrated to illustrate the obtained results.     

A Modified Polynomial Preserving Recovery and Its Applications to A Posteriori Error Estimates

<正>A modified polynomial preserving gradient recovery technique is proposed. Unlike the polynomial preserving gradient recovery technique,the gradient recovered with the modified polynomial preserving recovery(MPPR) is constructed element-wise, and it is discontinuous across the interior edges.One advantage of the MPPR technique is that the implementation is easier when adaptive meshes are involved.Superconvergence results of the gradient recovered with MPPR are proved for finite element methods for elliptic boundary problems and eigenvalue problems under adaptive meshes. The MPPR is applied to adaptive finite element methods to construct asymptotic exact a posteriori error estimates.Numerical tests are provided to examine the theoretical results and the effectiveness of the adaptive finite element algorithms.     

Implicit Simulation Methods for Stochastic Chemical Kinetics

In biochemical systems some of the chemical species are present with only small numbers of molecules. In this situation discrete and stochasticsimulation approaches are more relevant than continuous and deterministic ones. The fundamental Gillespie’s stochastic simulation algorithm (SSA) accounts for every reaction event, which occurs with a probability determined by the configuration of the system. This approach requires a considerable computational effort for models with many reaction channels and chemical species.In order to improve efficiency, tau-leaping methods represent multiple firings of each reaction during a simulation step by Poisson random variables. For stiff systems the mean of this variable is treated implicitly in order to ensure numerical stability. This paper develops fully implicit tau-leaping-like algorithms that treat implicitly both the mean and the variance of the Poisson variables. The construction is based on adapting weakly convergent discretizations of stochastic differential equations to stochastic chemical kinetic systems. Theoretical analyses of accuracy and stability of the new methods are performed on a standard test problem. Numerical results demonstrate the performance of the proposed tau-leaping methods.     

测地线活动轮廓模型的图像分割快速算法

从最优化理论的角度来看,目前求解图像分割的测地线活动轮廓(geodesic active contour,GAC)模型大多采用固定步长的最速下降算法.而众所周知,该算法收敛速度较慢,这在能量泛函的梯度较小时尤为明显.对求解GAC模型的快速算法进行了研究.首先,回顾了GAC模型的演化方程;随后,将共轭梯度(conjugate gradient,CG)算法引入到GAC模型的求解中,形成一种新的求解图像分割问题的数值方法,即GAC模型的CG算法;最后,通过试验对比传统的数值方法,表明CG算法具有良好的收敛性.     

AN ADAPTIVE MULTI-SCALE CONJUGATE GRADIENT METHOD FOR DISTRIBUTED PARAMETER ESTIMATION OF 2-D WAVE EQUATION

An adaptive multi-scale conjugate gradient method for distributed parameter estimations (or inverse problems) of wave equation is presented. The identification of the coefficients of wave equations in two dimensions is considered. First, the conjugate gradient method for optimization is adopted to solve the inverse problems. Second, the idea of multi-scale inversion and the necessary conditions that the optimal solution should be the fixed point of multi-scale inversion method is considered. An adaptive multi-scale inversion method for the inoerse problem is developed in conjunction with the conjugate gradient method. Finally, some numerical results are shown to indicate the robustness and effectiveness of our method.     

无线多媒体接入网高能效的自适应载频开启控制

针对无线接入网负载高波动的特点,提出一种基于随机超时阈值的多路载频自适应开启的动态功耗控制策略,在满足多类业务QoS的同时,降低系统基站的能耗.构建事件驱动的连续时间Markov控制过程系统分析模型,将自适应载频开启节能控制转化为一个带约束的优化问题.结合性能梯度估计与随机逼近,提出一种基于策略梯度的在线自适应优化算法.仿真实验结果验证了方法的有效性.     

Rate of Convergence of an Improved Reduced Gradient Method

An improved reduced gradient method was proposed in [4] to solve the nonlinear programming (p) with linear constraints: (p) f(x) R={x∈E~n|AX=b,x≥0} b∈E~m. In this paper we introduce parameters ρ_k which is the skill used in [5] to the algorithm of [4] to obtain a reduced gradient method which is linearly convergent under the conditions of R being non-degenerate, f being second-order continuously differentiable and strong convex.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

无约束最优化问题随机搜索算法的收敛性

引言 设F(X)是定义在n维欧氏空间R~n上的实值连续函数,欲求它的极小点和极小值。解这样的无约束极值问题,已提出了好几种随机搜索算法。这类算法简单直观,适用范围广泛,是人们时常采用的方法之一。但是对这类算法的收敛理论,迄今研究甚少。 G.Schrack和N.Borowski对三种比较流行的随机搜索算法作了系统的计算实验,[2]说明M.A.Schumer和K.Steiglitz在[3]中提出的“调整步长随机搜索”算法(Ada-ptive step size random search)其计算效果比较好。本文在目标函数F(X)的一定假设条件下证明了这种算法的收敛性。     

一种新型的局部连接BP网络模型及应用

局部连接神经网络简化了网络结构,提升了网络收敛速度和减少了网络训练复杂度,可用于函数逼近和系统建模.为了采用直观的建模方式对实际系统网络拓扑逼近,对此文章提出一种新型的局部连接BP网络模型(local BP neural network,LBPNN).该模型的网络结构可以模拟任意前馈型网络拓扑结构,其网络模型中的连接权和神经元与被模拟的网络拓扑中的边和节点一一对应.传统带约束的非线性规划和智能优化算法,其参数辨识受限条件多和算法代价较大,同时提出了与LBPNN模型相应的一种新型的带约束的随机梯度下降法(constrained stochastic gradient descent,CSGD)对其权值参数进行训练.通过算例仿真验证了CSGD训练算法的有效性,稳定性和鲁棒性.     

一类新的伪单调变分不等式的自适应次梯度外梯度投影算法

Gibali[J.Nonlinear Anal.Optim.,2015,6(1):41-51]提出了一种解伪单调非Lipschitz连续变分不等式的自适应次梯度外梯度投影算法.其下一迭代点是通过向一个特定的半空间投影来实施.本文通过构造新的下降方向得到了一类新的自适应次梯度外梯度投影算法,并借助于何炳生和廖立志[J.Optim.Theory Appl.,2002,112(1):111-128]中的技巧优化了这些算法的步长.证明了这些算法所生成序列的全局收敛性.数值实验结果表明这类次梯度外梯度投影算法比已有算法受初始点的选取、变分不等式的维数及停止标准的精度的影响更小.而且,从迭代次数及运算所花的时间来看,新的算法均优于Gibali提出的算法.     

QUASI-SURE CONVERGENCE RATE OF EULER SCHEME FOR STOCHASTIC DIFFERENTIAL EQUATIONS

Let Xt(x) be the solution of stochastic dierential equations with smooth and bounded derivatives coeffcients. Let Xnt(x) be the Euler discretization scheme of SDEs with step 2-n. In this note, we prove that for any R 0 and γ∈(0, 1/2), supt∈[0,1],|x|≤R |Xnt(x, ω)- Xt(x, ω)|≤ξR,γ(ω)2-nγ, n≥1, q.e., where ξR,γ(ω) is quasi-everywhere finite.     

求解伪单调变分不等式的自适应加速外梯度算法

本文改进Tseng的外梯度算法,引入了一种新的求解伪单调变分不等式的投影算法.该算法的步长是自适应的,在Lipschitz常数未知的情况下通过一个简单的计算逐步更新.结合惯性加速技巧,在算子A是伪单调且Lipschitz连续的假设下,证明了该算法所产生的序列强收敛到变分不等式的解.进行的一些数值试验表明了所提出的算法比现有的一些算法具有竞争优势.     

非精确信赖域类型算法及收敛性分析

在求解大规模数据的优化问题时,由于数据规模和维数较大,传统的算法效率较低.本文通过采用非精确梯度和非精确Hessian矩阵来降低计算成本,提出了非精确信赖域算法和非精确自适应三次正则化算法.在一定条件下,证明了算法有限步停止,并估计了算法迭代的复杂度.特别地,我们分析了采用随机抽样时算法在给定概率下的复杂度.最后,通过二分类问题的数值求解,比较了本文提出的随机信赖域算法,随机自适应三次正则化算法和已有算法收敛效率.数值结果表明在相同精度下,本文提出的算法效率更高,并且随机自适应三次正则化算法的效率优于随机信赖域算法.