大型稀疏无约束优化的分划组修正算法

1 引言我们考虑求解无约束优化问题 (1) 其中f:Rn→R二次连续可微．f(x)的Hesse阵H(x)稀疏．为了求解问题(1),我们考虑下列Newton型方法     

一类非单调算法的收敛性质

1.搜索步长和搜索方向对于无约束最优化问题(?)f(x),其中f:R~n→R~1,f∈C~1,一般采用形如x_(k+1)=x_k+λ_kd_k(k=1,2,…)的迭代算法来求解,这里λ_k为搜索步长,d_k为搜索方向.     

一类非单调算法的收敛性质

1.搜索步长和搜索方向对于无约束最优化问题(?)f(x),其中f:R~n→R~1,f∈C~1,一般采用形如x_(k 1)=x_k λ_kd_k(k=1,2,…)的迭代算法来求解,这里λ_k为搜索步长,d_k为搜索方向.     

退化线性约束凸规划问题的变尺度法

考虑问题: (?)f(x) (NP)其中R={x∈R~n|a_i~Tx≤b_i,i=1,…,m},f(x)一阶连续可微且凸。本文在R退化条件下,给出了一个整体超线性收敛的变尺度法。记N={1,…,m),J(?)N,记A_J={a_i|i∈J}。当γ(A_J)=|J|时,R~n到 R_J={x∈R~n|a_i~Tx=0,i∈J}的正投影矩阵P_J=E_n-A_J(A_J~TA_J)~(-1)A_J~T。若{a_i|i∈I}和{a_i|i∈J}都是{a_i|i∈N′(?)N}的最大线性无关组,则P_J=P_I。x~k∈R,记N_k={i∈N|a_i~Tx~k=b_i},gk=▽f(x~k)。     

基于信赖域技术和修正拟牛顿方程的非单调共轭梯度算法

1引言考虑无约束最优化问题(?)其中f(x):R~n→R~1是一阶连续可微函数.求解问题(1)的非线性共轭梯度算法结构简单、收敛速度快、存储量小,适于求解大     

非光滑优化的二阶必要条件

1 引言 对无约束最优化问题,其必要条件要求在局部极小点x处沿任何方向的梯度为零,曲率为正。而对约束最优化问题,首先它的局部极小点必须是可行点,其次不仅要求验证局部 极小点的某个邻域内的二阶项(曲率),而且也要认识到约束曲率也起相当重要的作用。现实中存在这样的问题,在x点处G正定,而它不是局部极小点。因此必须考虑约束最优化问题的二阶必要性条件。 本文研究了非线性规划的二阶必要性条件,其约束函数的一阶导数为方向Lipschitz连续。 2 方向Lipschitz连续函数的性质 定义2.1 设f是R~n上的一个广义实值函数,f在x∈R~n处有限,称f在x处是方向Lipschitz连续的,如果至少存在一点y∈R~n使得 其中( 定义2.2 设f如定义2.1,定义f在R~n处的次导数集如下 其中 本文多次引用f↑(x;y),因此我们首先介绍f↑(x;y)的3个基本性质:     

线性约束非线性规划的梯度投影法

我们考虑问题(LNP) minf(x),x∈R={x|A~Tx≤b,x∈R~n},其中A是n×m矩阵,b为m维向量,R~n为n维欧氏空间f(x)∈C~1.记I(x)={i|a_i~Tx=b_i,i=1,…,m},P_(I(x))为R~n到U_(I(x))={x|a_i~Tx=0,i∈I(x)}的投影矩阵.特别记I_k=I(x~k),U_k=U(I_k),N(I_k)=(a_i~T,i∈I_k)~T.本文恒假定秩N_(I(x))=|I(x)|,(即I(x)中的元素个数).     

锥模型拟牛顿法

1 引 言 对于求解无约束最优化问题 min f(x),f:R~n→R,f∈C~2。Davidon提出了一类非二次模型方法,即锥函数近似模型 f(x)≈c(x)=f(x_k)+(f(x_k)~T(x-x_k))/((1-h_k~T(x-x_k))+1/2((x-x_k)~TA_k(x-x_k))/([1-h_k~T(x-x_k)]~2) (1.1)和共线调比变换     

带多项式相位的高维振荡积分算子的有界性

考虑如下的振荡积分算子:T_(m,k,n)f(x):=∫_(R~n)e~(i(x_1~2+…+x_n~2))~m(y_1~2+…+y_n~2)~kf(y)dy,其中函数f为定义在R~n上的Schwartz函数,并且满足m,k0.本文给出算子T_(m,k,n).从L~p(R~n)(1≤p∞)到L~q(R~n)有界的一个充分必要条件.此外,我们还证明了算子T_(m,k,n)把L~1(R~n)映到C_0(R~n).     

一种改进的随机次梯度方法的快速收敛性

1引言考虑如下优化问题: min f(x)=sum from i=1 to m f_i(x),s.t. x∈X (1)其中,f_i∶R~n→R是凸函数且f_i不可微,X是R~n上的非空闭凸子集．解(1)的主要方法     

A novel fast overrelaxation updating method for continuous-discontinuous cellular automaton

Because of its local property, cellular automaton method has been widely applied in different subjects, but the main problem is that the cellular updating is time-consuming. In order to improve its calculation efficiency, a fast successive relaxation updating method is proposed in this paper. Firstly, an accelerating factor ω is defined, and a fast successive relaxation updating theory and its corresponding convergence conditions are developed. In each updating step, the displacement increment is enlarged ω times as a new increment to replace the old one, similarly, the nodal forces for its neighbors caused by this displacement increment are also enlarged by the same accelerating factor, and do those updating operations until the convergence is achieved. By this method, the convergence rate is greatly improved, by a suitable accelerating factor, 90 to 98% of iteration steps are decreased compared to that of the traditional method. Besides, the influence factors for the accelerating factor are studied, and numerical studies show that the suitable accelerating factor is 1.85 < ω < 1.99, which is greatly influenced by cell stiffness, and the optimal accelerating factor is 1.96 < ω < 1.99. Finally, numerical examples are given to illustrate that the present method is effective and high convergence rate compared to the traditional method.     

Convergence analysis of multigrid methods with residual scaling techniques

In this paper, multigrid methods with residual scaling techniques for symmetric positive definite linear systems are considered. The idea of perturbed two-grid methods proposed in [7] is used to estimate the convergence factor of multigrid methods with residual scaled by positive constant scaling factors. We will show that if the convergence factors of the two-grid methods are uniformly bounded by σ (σ<0.5), then the convergence factors of the W-cycle multigrid methods are uniformly bounded by σ/(1−σ), whether the residuals are scaled at some or all levels. This result extends Notay’s Theorem 3.1 in [7] to more general cases. The result also confirms the viewpoint that the W-cycle multigrid method will converge sufficiently well as long as the convergence factor of the two-grid method is small enough. In the case where the convergence factor of the two-grid method is not small enough, by appropriate choice of the cycle index γ, we can guarantee that the convergence factor of the multigrid methods with residual scaling techniques still has a uniform bound less than σ/(1−σ). Numerical experiments are provided to show that the performance of multigrid methods can be improved by scaling the residual with a constant factor. The convergence rates of the two-grid methods and the multigrid methods show that the W-cycle multigrid methods perform better if the convergence rate of the two-grid method becomes smaller. These numerical experiments support the proposed theoretical results in this paper.     

求複數根的舗D法

<正> 一. 引言 代數方程f(x)=0的實數根的逐步接近法已有多種,其中計算簡單收斂最快的是用牛頓公式     

Improvement of convergence of an iterative method for finding polynomial factors of analytic functions

In this paper, we consider an iterative method for evaluating the coefficients of a monic factor of an analytic function using complex circular arithmetic. In a previous paper, the authors presented a factoring method that finds a cluster of zeros as a polynomial factor. We analyze the convergence behavior of this method and discuss a technique for improving convergence. Numerical examples illustrate the aspects of the improved method.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

一类各向异性外问题的非重叠型区域分解算法

In this paper, based on the natural integral operator on elliptic boundary, a nonoverlapping domain decomposition method is presented for a kind of anisotropic elliptic problem with constant coefficients in an exterior domain, and the convergence of the method is analyzed. The choice of the relaxition factor is discussed.Some numerical examples are given. Theoretical analysis as well as numerical examples show that our method is performance.     

关于Schwarz交替法的收敛因子

§1.Schwarz交替法的收敛因子 我们就二阶自共轭椭圆型方程的Dirichlet问题来讨论.设Ω?R~2为一多边形区域, a(u,v)=(f,v),v∈H_0~1(Ω),f∈H~(-1)(Ω), u∈H_0~1(Ω)是定义在其上的边值问题的变分形式,双线性型时a(·,·)满足     

Self-Adaptive Extrapolated Gauss-Seidel Iterative Methods

In this paper, we consider a self-adaptive extrapolated Gauss-Seidel method for solving the Hermitian positive definite linear systems. Based on optimization models, self-adaptive optimal factor is given. Moreover, we prove the convergence of the self-adaptive extrapolated Gauss-Seidel method without any constraints on optimal factor. Finally, the numerical examples show that the self-adaptive extrapolated Gauss-Seidel method is effective and practical in iteration number.     

一种改进灰狼优化算法研究及应用

针对灰狼算法易陷入局部最优、收敛精度不高、收敛速度慢等缺点,提出一种改进的灰狼算法.引入莱维飞行,扩大搜索范围,增强全局搜索能力,避免陷入局部最优;引入贪婪原理,提升种群优良性以提高算法收敛精度;引入自适应收敛因子,加快收敛速度;引入动态权重策略,制约全局搜索与局部搜索的相互影响.将改进算法与其他四种算法作对比,实验表明,改进算法在收敛速度与收敛精度上都有更好的性能.最后,应用于图像多阈值分割中,采用GWO-Otsu法可以克服传统Otsu法在多阈值分割时计算量大,实时性差的特点,不但能够取得最优解,且明显缩减计算时间.     

解不适定算子方程的一个定常二步隐式迭代法

On the basis of an implicit iterative method for ill-posed operator equations,we introduce a relaxation factor and a weighted factor , and obtain a stationarytwo-step implicit iterative method. The range of the factors which guarantee theconvergence of iteration is explored.We also study the convergence properties and ratesfor both non-perturbed andperturbed equations.An implementable algorithm is presented by using Morozov discrepancy principle.The theoretical results show that the convergence rates of the new methods always lead to optimal convergentrates which are superior to those of the original one after choosing suitable relaxation and weightedfactors. Numerical examplesare also given, which coincide well with the theoretical results.