Kth最短路径的Bellman改进算法

基于对Bellm an算法的改进,得到了求解k th最短路的新算法.改进算法的优势在于从Bellm an算法只能解决最短路问题拓展到求解k th最短路问题,而且可以考虑权重为负数的情况.与传统算法相比,新算法更易于理解.     

带约束动力学辛算法的符号计算

首先对带约束动力学中的辛算法作了改进,利用吴消元法求解多项式类型Euler-Lagrange方程.在辛算法的基础上,根据线性方程组理论和相容条件提出了一个求解约束的新算法.新算法的推导过程比辛算法严格,而且计算也比辛算法简单,并且多项式类型的Euler-Lagrange仍可以用吴消元法求解.另外,对于某些非多项式类型的Euler-Lagrange方程,可以先化为多项式类型,再用吴消元法求解.利用符号计算软件,上述算法都可以在计算机上实现.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

一类具有非单调线搜索的混合共轭梯度算法

提出一类求解无约束最优化问题的混合共轭梯度算法,新算法有机地结合了DY算法和HS算法的优点,并采用非单调线搜索技术在较弱条件下证明了算法的全局收敛性.数值实验表明新算法具有良好的计算效能.     

非线性互补问题的水平值估计算法

本文研究非线性互补问题（NCP）的求解算法，先将NCP转化为约束全局优化问题（CGOP），然后直接移植求解问题（CGOP）的水平值估计算法^[4,5]来求解问题（NCP）．文章证明了算法对于NCP是收敛的，数值实验说明了算法的有效性．     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

一种新的并行代数多重网格粗化算法

近年来,受实际应用领域中大规模科学计算问题的驱动,在大规模并行机上实现代数多重网格（AMG）算法成为数值计算领域的研究热点。本文针对经典AMG方法,提出一种新的并行网格粗化算法一多阶段并行RS算法（MPRS）。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示,新算法适合更广泛的问题,相对其他并行粗化算法,明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程,在64个处理机上并行AMG求解,含8百万个未知量,新算法比RS3算法减少了近60的三维Poisson方程,近32万个未知量,在16个处理机上并行AMG—GMRES求解,新算法所需的迭代步数大约为其他粗化算法的一半,显示了很好的算法可扩展性。     

一种单位化的增量梯度算法

研究目标函数是若干光滑函数和的可分离优化问题,提出了一种单位化增量梯度算法。该算法每次子迭代只需要计算一个（或几个）分量函数的单位负梯度方向作为迭代方向。在一定条件下,证明了采用发散步长的单位化增量梯度算法的收敛性。作为应用,新算法和Bertsekas D P,Tsitsikils J N提出的（没有单位化）增量梯度算法分别用来求解稳健估计问题和源定位问题。数值例子表明,新算法优于（没有单位化）增量梯度算法。     

Equi-statistical convergence of positive linear operators

Balcerzak, Dems and Komisarski [M. Balcerzak, K. Dems, A. Komisarski, Statistical convergence and ideal convergence for sequences of functions, J. Math. Anal. Appl. 328 (2007) 715-729] have recently introduced the notion of equi-statistical convergence which is stronger than the statistical uniform convergence. In this paper we study its use in the Korovkin-type approximation theory. Then, we construct an example such that our new approximation result works but its classical and statistical cases do not work. We also compute the rates of equi-statistical convergence of sequences of positive linear operators. Furthermore, we obtain a Voronovskaya-type theorem in the equi-statistical sense for a sequence of positive linear operators constructed by means of the Bernstein polynomials.     

Global convergence and rate of convergence of a method of centers

We consider a method of centers for solving constrained optimization problems. We establish its global convergence and that it converges with a linear rate when the starting point of the algorithm is feasible as well as when the starting point is infeasible. We demonstrate the effect of the scaling on the rate of convergence. We extend afterwards, the stability result of [5] to the infeasible case anf finally, we give an application to semi-infinite optimization problems.     

具简单界约束变分不等式的拟牛顿算法的收敛性分析

１．引言 牛顿型方法是解变分不等式的一类重要数值迭代算法．其局部收敛性质的研究也取得了很好的成果（见［５］等）．近几年来,此类算法的全局收敛性研究也得到了许多进展．如阻尼牛顿法的局部超线性乃至二阶收敛性质的研究（见［４,６,９; １１, １２, １４; １６］等）．然而,对于计算上更为实用的拟牛顿法的研究还不多见．文［１８］基于祁力群等在［１４］中给出的逐次逼近牛顿型法,建立了一种解非线性互补问题的拟牛顿法,并得到了类Ｂｒｏｙｄｅｎ算法的全局收敛性．但是,该方法有以下两个缺陷：１．线搜索可能不能实现…     

Linear convergence of gradient projection algorithm for split equality problems

ABSTRACT

In this paper, we consider the varying stepsize gradient projection algorithm (GPA) for solving the split equality problem (SEP) in Hilbert spaces, and study its linear convergence. In particular, we introduce a notion of bounded linear regularity property for the SEP, and use it to establish the linear convergence property for the varying stepsize GPA. We provide some mild sufficient conditions to ensure the bounded linear regularity property, and then conclude the linear convergence rate of the varying stepsize GPA. To the best of our knowledge, this is the first work to study the linear convergence for the SEP.     

An Algorithm for Continuous Type Optimal Location Problem

In this paper, we extend the ordinary discrete type facility location problems to continuous type ones. Unlike the discrete type facility location problem in which the objective function isn't everywhere differentiable, the objective function in the continuous type facility location problem is strictly convex and continuously differentiable. An algorithm without line search for solving the continuous type facility location problems is proposed and its global convergence, linear convergence rate is proved. Numerical experiments illustrate that the algorithm suggested in this paper have smaller amount of computation, quicker convergence rate than the gradient method and conjugate direction method in some sense.     

一类无需线性搜索的记忆梯度法

提出一类新的求解无约束优化问题的记忆梯度法,证明了算法的全局收敛性.当目标函数为一致凸函数时,对其线性收敛速率进行了分析.新算法在迭代过程中无需对步长进行线性搜索,仅需对算法中的一些参数进行预测估计,从而减少了目标函数及梯度的迭代次数,降低了算法的计算量和存储量.数值试验表明算法是有效的.     

Armijo线性搜索下的多步下降算法

本文研究无约束优化问题.利用前面多步迭代点的信息产生下降方向以及Armijo线性搜索产生步长,得到了一类新的多步下降算法,并且在较弱条件下证明了算法具有全局收敛性和线性收敛速率.初步的数值试验表明算法是有效的.     

A Rapidly Convergence Algorithm for Linear Search and its Application

The essence of the linear search is one-dimension nonlinear minimization problem, which is an important part of the multi-nonlinear optimization, it will be spend the most of operation count for solving optimization problem. To improve the efficiency, we set about from quadratic interpolation, combine the advantage of the quadratic convergence rate of Newton's method and adopt the idea of Anderson-Bjorck extrapolation, then we present a rapidly convergence algorithm and give its corresponding convergence conclusions. Finally we did the numerical experiments with the some well-known test functions for optimization and the application test of the ANN learning examples. The experiment results showed the validity of the algorithm.     

On quadratic andO\left( {\sqrt {nL} } \right) convergence of a predictor—corrector algorithm for LCP

Recently several new results have been developed for the asymptotic (local) convergence of polynomial-time interior-point algorithms. It has been shown that the predictor—corrector algorithm for linear programming (LP) exhibits asymptotic quadratic convergence of the primal—dual gap to zero, without any assumptions concerning nondegeneracy, or the convergence of the iteration sequence. In this paper we prove a similar result for the monotone linear complementarity problem (LCP), assuming only that a strictly complementary solution exists. We also show by example that the existence of a strictly complementarity solution appears to be necessary to achieve superlinear convergence for the algorithm.Research supported in part by NSF Grants DDM-8922636 and DDM-9207347, and an Interdisciplinary Research Grant of the University of Iowa, Iowa Center for Advanced Studies.     

On the rate of convergence of infinite horizon discounted optimal value functions

In this paper we investigate the rate of convergence of the optimal value function of an infinite horizon discounted optimal control problem as the discount rate tends to zero. Using the Integration Theorem for Laplace transformations we provide conditions on averaged functionals along suitable trajectories yielding quadratic pointwise convergence. From this we derive under appropriate controllability conditions criteria for linear uniform convergence of the value functions on control sets. Applications of these results are given and an example is discussed in which both linear and slower rates of convergence occur depending on the cost functional.