两个修改BFGS算法的收敛性

本文以下内容是这样安排的:第二节给出一个统一算法模型(GBFGS),并在假设目标函数一致凸的条件下证明该算法具有全局收敛性和局部超线性收敛性;作为第二节理论的应用,我们在第三节证明Biggs算法和Yuan算法的收敛性质.     

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

多层线性模型参数估计的MCEM算法

应用Monte Carlo EM(MCEM)算法给出了多层线性模型参数估计的新方法,解决了EM算法用于模型时积分计算困难的问题,并通过数值模拟将方法的估计结果与EM算法的进行比较,验证了方法的有效性和可行性.     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

基于经典逻辑系统的模糊推理方法

给出了一种基于经典二值逻辑系统的模糊推理方法.由于经典二值逻辑系统和我们提出的一种新的三段论原则是比较令人信服的,故我们的算法的基础是较为坚实的;同时在新的推理方法中避免了蕴合算子的选择,使得本算法不存在选择蕴含算子的困难;本算法具有还原性且计算简单;通过实例的计算结果与三Ⅰ算法和CRI算法的计算结果相比较,说明由新算法计算出的结果也是较为令人信服的,因此新算法是一种较好的算法.     

形如2kp+1的数的素性检验

本文初步探讨了如何快速检验一个大数n是素数(这里n-1含有大的素因子)的算法问题以及如何生成一个大素数p使得p-1有大的素因子q的算法问题.我们给出了形如n=2kp+1的数的素性检验的多项式时间算法,这里p是一个给定的大素数,k是正整数满足22k＜2kp.该算法的计算量为O(log32n).然后我们给出了生成一个大素数p使得p-1有大的素因子q的算法,其中q满足q＞(p-1)/log2(p-1).特别地,我们给出了判定并生成一个安全素数p的算法.     

亚定方程组的1_∞模极小解

;1引言 我们在文【1〕中提出了地震反演的一种模刑 。m in{lx{l、(1) 派工.刀戈一b其中月。R”‘x”,:a:Ik(川二,,:.在文〔2J中给出了解此问翘的系统算法,形成了软件.由J几l:模极小化原则对克服坏数据影响有独特的作用,在地震探矿资料处理上取得了‘,丁一弃的结果.但是如何估计鼓坏数据影响,使我们对反演结果有更深入的了解,那么就有必安研究知卜的l、模极小化问题: ;min{lx{l 木文将研究解决(2)的理论和方法.算法的基木思想是将(2)的等价线性规划问题化为其对偶问题,然后提出一些概念,定理,给出解(2)的对偶问题的算法,并给出算例.·152·…     

优化算法的复杂度分析

优化算法的收敛性分析是优化中很重要的一个领域,然而收敛性并不足以作为比较不同算法效率的标准,因此需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论,这套理论被称为优化算法的复杂度分析理论.本文共分为5个部分.第1节介绍复杂度分析的背景和理论框架,给出复杂度分析的定义、方法和例子,并总结本文中的复杂度结论.第2节介绍光滑优化问题的复杂度分析,给出不同优化问题的复杂度上界和下界,并给出加速梯度法收敛性分析的框架.第3节介绍非光滑优化问题的复杂度上界,介绍次梯度法、重心法、椭球法和近似点梯度法的复杂度分析.第4节介绍条件梯度法的复杂度分析,介绍条件梯度法的复杂度上界和下界,以及加速条件梯度法的框架.第5节介绍随机优化算法的复杂度分析,比较随机优化算法在凸和非凸问题下收敛的置信水平和复杂度.     

KIM算法的最优性

研究工件的就绪时间可以不相同、但是与交货期有＂一致性＂关系的误工问题.1978年Kise,Ibaraki,Mine提出算法（简称为KIM算法）,证明他们提出的KIM算法可以得到这个误工问题的最优解.最近李杉林、陈志龙、唐国春用反例指出Kise,Ibaraki,Mine证明最优性时提出的引理2是错误的,并用新的方法证明KIM算法的最优性.越民义则给出一个非常简洁的证明.本文分析引理2的错误所在,给出修改后的引理2’,由此似乎应该相应修改KIM算法,然而我们证明原来的KIM算法仍然可以得到最优解.     

分裂可行问题(SFP)的投影算法

本文探讨了分裂可行问题(SFP)的投影算法．我们先定义了(SFP)的反问题(ISFP), 然后利用正交投影性质,给出了(SFP)与(ISFP)及某些投影不动点问题之间的关系．随后, 给出了求解(SFP)的几种正交投影算法,其中包括精确和不精确投影格式．基于变分不等式中投影算法收敛性的证明思路和分裂可行问题的特有形式,证明了这几种算法的收敛性．最后通过几个算例对讨论的方法进行了初步比较．     

广义Lipschitz伪压缩映射黏滞迭代逼近方法的强收敛

K是Banach空间E的一个非空闭凸子集,T:K→K是一个广义Lipschitz伪压缩映射.对Lipschitz强伪压缩映射f:K→K和x_1∈K,序列{x_n}由下式定义:x_n+1=(1-α_n-β_n)x_n+α_nf(x_n)+β_nTx_n.在{α_n}与{β_n}满足合适条件的情况下,每当{z∈K;μ_n‖x_n-z‖~2=inf_(y∈K)μ_n‖x_n-y‖~2}∩F(T)≠φ时,{x_n}强收敛到T的某个不动点x~*.     

鞅的(Φ_1,Φ_2)-型倒向极大不等式

设Φ_1,Φ_2是非负凸函数,证明了鞅的倒向极大算子不等式‖f‖Φ_2≤C‖f*‖Φ_1对于任意鞅f=(f_n)_n≥0成立的充分必要条件是Φ_2(?)Φ_1;鞅的极大算子均方算子的极大极小不等式‖M(f)‖Φ_2≤C_1‖m(f)‖Φ_1及‖m(f)‖Φ_2≤C_2‖M(f)‖Φ_1成立的充分必要条件是Φ_2(?)Φ_1,这里M(f)=max{f*,S(f)},m(f)=min{f*,S(f)}分别是极大算子、均方算子的极大极小函数.     

Lp-Lq Estimates for a Linear Perturbed Klein-Gordon Equation

We consider L^p-L^q estimates for the solution u(t,x) to tbe following perturbed Klein-Gordon equation ∂_{tt}u - Δu + u + V(x)u = 0 \qquad x∈ R^n, n ≥ 3 u(x,0) = 0, ∂_tu(x,0) = f(x) We assume that the potential V(x) and the initial data f(x) are compact, and V(x) is sufficiently small, then the solution u(t,x) of the above problem satisfies ||u(t)||_q ≤ Ct^{-a}||f||_p for t > 1 where a is the piecewise-linear function of 1/p and 1/q.     

Higher Commutators of Pseudo-Differential Operator

In this paper the following result is established: For a_i,f\in \phi(R^K),i=1,\cdots,n and $T(a,f)(x)=w(x,D)()[\prod\limits_{i = 1}^n {{P_{{m_i}}}({a_i},x, \cdot )f( \cdot )} \]$ It holds that $||T(a,f)||_q\leq C||f||_p_0[\prod\limits_{i = 1}^n {||{\nabla ^{{m_i}}}|{|_{{p_i}}}} \]$ where a=(a_1,\cdots,a_n), q^-1=p^-1_0+[\sum\limits_{i = 1}^n {p_i^{ - 1} \in (0,1),\forall i,{p_i} \in (1,\infty )} \] or \forall i,p_i=\infinity,p_0\in (1,\infinity), for an integer m_i\geq 0, $P_m_m(a_i,x,y)=a_i(x)-[\sum\limits_{|\beta | < {m_i}} {\frac{{a_i^{(\beta )}(y)}}{{\beta !}}} {(x - y)^\beta }\]$ w(x,\xi) is a classical symbol of order |m|, m=(m_1,\cdots, m_n), |m|=m_1+\cdots+m_n, m_i are nonnegative integers. Besides, a representation theorem is given. The methods used here closely follow those developed by Coifman, R. and Meyer, Y. in [5] and by Cohen, J. in [3].     

On the approximation by de la Vallée Poussin sums and interpolatory polynomials in Lipschitz norms

ПустьM ^m,α - множество 2π-п ериодических функци йf с конечной нормой $$||f||_{p,m,\alpha } = \sum\limits_{k = 1}^m {||f^{(k)} ||_{_p } + \mathop {\sup }\limits_{h \ne 0} |h|^{ - \alpha } ||} f^{(m)} (o + h) - f^{(m)} (o)||_{p,} $$ где1 ≦ p ≦ ∞, 0≦α≦1. Рассмотр им средние Bалле Пуссе на $$(\sigma _{n,1} f)(x) = \frac{1}{\pi }\int\limits_0^{2x} {f(u)K_{n,1} (x - u)du} $$ и $$(L_{n,1} f)(x) = \frac{2}{{2n + 1}}\sum\limits_{k = 1}^{2n} {f(x_k )K_{n,1} } (x - x_k ),$$ де0≦l≦n и x _k=2kπ/(2n+1). В работе по лучены оценки для вел ичин \(||f - \sigma _{n,1} f||_{p,r,\beta } \) и $$||f - L_{n,1} f||_{p,r,\beta } (r + \beta \leqq m + \alpha ).$$      

CONVERGENCE RATE OF MULTIVARIATE K-NEAREST NEIGHBOR DENSITY ESTIMATES

Let be the collection of m-times continuously differentiable probability densities fon R~d such that 丨D~af(x_1)-D~af(x_2)丨≤M‖x_1-x_2‖~β for x_1,x_2∈R~d,[a]=m,where D~adenotes the differential operator defined by D~a=([a])/(x_1~a…x_d~a_d).Under rather weak conditionson K(x),the necessary and sufficient conditions for sup丨_n(x)-f(x)丨=0(((logn/n)~λ/(d+3λ),λ=m+β,f∈ are that ∫x~aK(xi)dx=0 for 0<[a]≤m.Finally the convergenco rate at apoint is given.     

APPROXIMATION PROPERTIES OF LAGRANGE INTERPOLATION POLYNOMIAL BASED ON THE ZEROS OF （1- x^2）cosnarccosx

We study some approximation properties of Lagrange interpolation polynomial based on the zeros of （1-x^2）cosnarccosx. By using a decomposition for f（x） ∈ C^τC^τ＋1 we obtain an estimate of ‖f（x） -Ln＋2（f, x）‖ which reflects the influence of the position of the x＇s and ω（f^（r＋1）,δ）j,j = 0, 1,... , s,on the error of approximation.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

LP[0,1](1＜p＜∞)空间正系数多项式倒数逼近的一个推广

本文推广了LP[0,1](1＜p＜∞)空间函数的正系数多项式的倒数逼近的结论,即证明了:设f(x)∈LP[0,1],1＜p＜∞,且在(0,1)内严格1次变号,则存在一点x0∈(0,1)及一个n次多项式Pn(x)∈∏n(+)使得‖f(x)-x-x0/Pn(x)‖LP[0,1]≤Cpω(f,n-1/2)LP[0,1],其中∏n(+)为次数不超过n的正系数多项式的全体.     

P_m×P_n的邻强均匀边色数

图G的一个k-正常着色满足相邻的点所关联的边的色集合不同,且任两色的边数之差不超过1称为G的k-邻强均匀边染色,图G邻强均匀边染色中最小的k称为图G的邻强均匀边色数.本文得到了P_m×P_n的邻强均匀边色数.