最小化非光滑复合函数的投影Hessian校正算法的收敛性

本文考虑复合函数 F(x)=f(x)+h(c(x))最小化问题,给出了校正矩阵逼近 Langrangian 函数的“单边投影 Hessian”的 Broyden-类型方法;此方法是 Q-超线性收敛的.文中还叙述了两个校正算法,并且证明了在合理的条件下,这两种算法都具有局部的两步 Q-超线性收敛性.     

关于乘子法的一种新算法

本文提出了关于增广乘子法的一种新算法.证明了该算法的合理性及其收敛速率为超线性的.对于非线性规划问题:(P)minf(x) x∈R~ns.t.h(x)=0,g(x)≤0.其中f:R~n→R~1;h:R~n→R~m;g:R~m→R~p均为二次连续可微.等式与不等式的有效约束的     

一类带非精确线性搜索的 DFP 算法

众所周知,以DFP和BFGS为代表的拟牛顿法是解无约束非线性规划问题:min{f(x);x∈R~n}的最常用和最有效的方法之一。但是在实际计算中,若选择步长因子时作的线性搜索“低精度”时,DFP算法的计算效果有时并不理想。而且,尽管1976年Powell证明了带非精确线性搜索的BFGS算法有一步超线性收敛率,1988年吴士泉采用重复使用原始正定矩阵的方法使得算法中用到的变尺度矩阵及其逆阵的迹有界,并且证明这类修改后的DFP算法,对一致凸目标函数,当线性搜索是非精确时,也具有一步超线性收敛率。但是对一般的DFP算法相应的结论是否成立,至今还是一个没有解决的问题。     

利用均值算法求解凸函数极小值的收敛性分析

郑权等在[1]-[3]中提出了一种求解无约束优化问题的均值算法，若假设目标函数f(x)是连续的，还讨论了均值算法的收敛性。若假设f(x) 有界闭集Ω上的凸函数，本文证明了求解凸函数极小值的均值算法是线性收敛的。     

一类拟可微函数的极小化算法

本文给出一类拟可微函数的极小化问题min f(x)=f₀(x)-maxf_i(x),x∈Rⁿ的算法,其中f₀是凸函数,f_i是连续可微函数,I是一个有限的指标集.算法的核心是对次微分作外接多面体近似.该算法属于下降算法.有关算法的理论作了详细的论述.     

一类变尺度算法的若干性质

Huang类变尺度算法包含3个独立参数。在Huang类基础上引进2个参数,由此得到一新算法类(有4个独立参数),并获得了:(1)新算法对目标函数F(x)的某种形式非线性变换L(F(x))具有不变性;(2)当F(x)为2次凸函数时,对适当范围的参数值,新算法用于L(F(x))仍是共轭方向法。另一方面,把Huang类扩大成有n 1个独立参数的新算法类,它用于2次凸函数F(x)时仍是共轭方向法。然而该类新算法一般不具有对L(F(x))的不变性;当F(x)为2次凸时用于L(F(x))一般也不是共轭方向法。     

一类由生成函数构成的可行方向算法

设非线性规划问题(P):min{f(x)|x∈R}。其中f:E~n→E~1,f(x)∈C~1,x∈E~n,R={x|A_x=b,x≥0},A为m×n阶矩阵,rankA=m,b∈E~m。 利用既约梯度建立可行方向算法目前在国内外已有不少,它们的特点在于:(1)将高维问题降为低维问题处理。此时的问题已近似于一个无约束的问题;(2)在计算的每一步上都是显式迭代,而不必去解一个复杂的线性的或二次的规划。这些特点使得算法变     

关于 Rosen 算法的注记

1960年,Rosen 提出一个求线性不等式组可行解的投影算法.1981年,Powell给出一个例子说明 Rosen 的算法会发生循环从而失效.本文证明,按照 Rosen 的算法,只要适当地做点修正,循环就可避免,从而算法必在有限步内找到解或发现无解.首先给出一些记号.所考虑的问题是求 n 维向量 x 满足     

分段线性规划算法的一个注记

求解分段线性规划问题inf S(x) s.t.Ax≤b 0≤x≤(?) (1)其中(?)=((?)_1,(?)_2,…,(?)_n)及 b=(b_1,b_2,…,b_m)~T 是已知向量,A 是已知的(m,n)矩阵,元素为 α_(ij)。目标函数 s(x)是分段线性函数。即对[0,(?)_j)(j=1,2,…,n)存在分划0=x_j~(0)相似文献   

基于核函数求解LCPs的全-Newton步不可行内点算法

本文对P_*(κ)线性互补问题设计了一种基于核函数的全-Newton步不可行内点算法,是对Mansouri等人提出的单调线性互补问题全-Newton步不可行内点算法的改进与推广.算法的主迭代由一个可行步和几个中心步构成且可行步采用小步校正.通过建立和应用一些新的技术性结果,证明了算法的多项式复杂性为O((1+2κ)~(3/2)(1og_2log_264(1+2κ))nlogmax{(x0)Ts0,||r0||}/ε),当k=0时,与当前单调线性互补问题的不可行内点算法最好的迭代复杂性界一致.最后,用Matlab数值实验验证了算法的可行性.     

不可微规划算法的实现

本文考虑如下的不可微规划问题其中目标函数f是局部Lipsohitz函数。根据可以定义方向导数f~0(x; d)和次微分集合(?)f(x)。现有的一些求解(NSP)的算法,例如[2],几乎都假定可以求得(?)f(x)或者(?)f(x)中的一个元素。然而,Shor指出既使f是凸函数,若(?)f(x)不是独点集,则不可能有算法保证对于ε>0,可以求得矢量g_a,使得当f是凸函数时,他同时给出一个求点x处近似次梯度的方法,即任意给定δ,δ>0,可以构造出矢量g,使得存在x∈B(x,δ),满足对于其他特殊情形,我们有如下结果。     

关于线性约束非线性规划的一个三角矩阵的逼近算法

1 引言 1981年J.Brauninger在[2]中给出了如下线性规划的一个有效算法: 其中x、C、a_i(i=1,2,…,m+p)均为n维列向量,m>0,n>0,P≥0,向量a_(m+1),…,a_(m+p) 线性无关,且(PL)中存在基可行解(见定义1)。为方便起见,我们把这一算法简称为三角矩阵法。受[1]中给出的算法的启发,本文给出了在用三角矩阵法求解(P_L)问题的基础上关于如下非线性规划问题(p_N)的一个可行方向算法: 其中f(x)为连续可微函数,R除具有(P_L)的约束集合的性质外还需具有下面的性质:对于R中的任何一个可行点x,R中的m+p个约束在x点最多能有n个等式成立。     

采用增广拉格朗日乘子形式的罚函数作线性搜索的递归等式约束二次逼近算法

1.引言 本文所讨论的问题如下: Min f(x) x∈R~n, s.t. c_i(x)=0,i=1,…,q,(1.1) c_i(x)≤0,i=q+1,…,p.解此问题的递归等式约束二次逼近算法,是由Murry(1969)提出,而后由Biggs(1972)发展的.此项研究是从罚函数的轨迹出发,建立一个只包含等式约束的二次规划子问题,从而可用代数的方法求得搜索方向.并沿该方向作线性搜索而完成一次迭代过程.Biggs将二次罚函数作为效应函数用于线性搜索,并证明了该算法具有全局收敛性和局部超线     

一个新的逐列正交化算法

本文讨论如下的最小二乘问题:min{S(x)=F(x)~TF(x)/2,x∈R~n},其中F(x)=(f_1(x),f_2(x),…,f_m(x)~T,m≥n.上述问题的求解,除了有以Levenberg-Marquardt为代表的各种阻尼最小二乘法外,还有一类逐列正交化算法.但在现有的逐列正交化算法中,对可行性、收敛性、收敛速度讨论得很少.本文提出了一个新的算法,并证明了其可行性、收敛性和收敛速度.文中附了计算实例,表明当用各种阻尼二乘法做不下去时,应用本算法还可能作出改进.本文主要结果如下:     

秦九韶算法的教学价值

人教A版<数学3>介绍了秦九韶算法:n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0. 当x=x0时,令v0=an,通过公式{v0=an,vk=vk-1x0=an-k(k=1,2,…,n)可求出f(x0)的值为vn. 它是我国古代数学中的著名算法,本文将从三个方面介绍该算法的教学价值.     

一个改进的Frank—Wolfe算法及其收敛性质

对于线性约束非线性规划其中,而A是-m×n矩阵, Frank-Wolfe曾对f(x)是二次函数的情形给出了(P)的一个算法,该算法结构简单,易于实现,是求解非线性网络问题的一个行之有效的方法。其后,许多学者对该方法做了大量的改进工作。但这些改进的方法本质上与Frank-Wolfe方法没有太大差别,其收敛定理与Frank-Wolfe方法一样,在算法产生的点列{x~n}有极限点的条件下,说明该极限点是(P)的-Kuhn-Tuoker点,而对的情形却没有任何结果。     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.     

对称线性互补问题的并行Schwarz算法

1引言考虑对称线性互补问题:求x∈R~N使得(1) Ax 6≥0,x≥0,x~T(Ax b)=0其中,A是给定的N×N实对称矩阵,b是N×1向量.目前求解该互补问题的迭代算法有很多(如Mangasarian(1977),Mangasarian,Leone (1987),Cottle(1992),曾金平,李董辉(1994)等).区域分解法以其将大问题化为若干子问     

广义线性模型组LASSO路径算法

广义线性模型组LASSO(least absolute shrinkage and selection operator)路径β(λ)的计算有两项核心内容:选择路径参数λ的取值;计算组LASSO估计,即给定λ值的β(λ).目前,在广义线性模型组LASSO路径的计算中,使用格点法选择λ值,基于广义线性模型似然函数一阶Taylor近似的坐标下降算法则常用于计算组LASSO估计.本文给出的广义线性模型组LASSO路径算法由两个子算法组成:第一个子算法的目的是选出使得活跃集恰好改变的λ值;第二个子算法是计算组LASSO估计的二阶近似坐标下降算法.模拟和实际数据分析均表明,第一个子算法能高效地发现使得活跃集恰好改变的λ值,相比基于广义线性模型似然函数一阶Taylor近似的坐标下降算法,本文的二阶近似算法有较明显的速度优势.     

BroWn-Broyden修正算法

1　引　　言求解非线性方程组F(x) =f1 (x1 ,… ,xn)廸n(x1 ,… ,xn)=0　　 F:D Rn→ Rn,(1.1)的 Brown方法 ,是将广义的 L U分解用于 Newton迭代过程 ,而形成的一类具有内外迭代形式的有效算法 .这类算法的特点是每步迭代的函数计算量仅仅为 Newton法的一半 ,而收敛速度则与 Newton法相同 .因此 ,按 Ostrowskii定义的效率指数去衡量 ,Brown方法为一效率较高的算法之一 ,是倍受推崇的 .本文 ,采用修正算法的思想 ,对 Brown方法作进一步改造 ,在不破坏原来的内外迭代形式下 ,使算法在每步迭代中的函数计值量由原来的 O(n2 )下降到 O(…