对称锥规划的邻域跟踪算法

本文把艾文宝的邻域跟踪算法推广到对称锥规划, 定义中心路径的宽邻域N(τ, β), 并证明该邻域的一个重要性质, 该性质在算法的复杂性分析中起到关键作用. 取宽邻域N(τ, β) 中一点为初始点并采用Nesterov-Todd (NT) 搜索方向, 则该算法的迭代复杂界为O(√r logε^-1), 其中, r是EuclidJordan 代数的秩, ε是允许误差. 这是对称锥规划的宽邻域内点算法最好的复杂界.     

线性互补问题的宽邻域预估校正算法

对线性互补问题提出了一种新的宽邻域预估校正算法,算法是基于经典线性规划路径跟踪算法的思想,将Maziar Salahi关于线性规划预估校正算法推广到线性互补问题中,给出了算法的具体迭代步骤并讨论了算法迭代复杂性,最后证明了算法具有多项式复杂性为O(ηlog(X~0)~Ts~0/ε)。     

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.     

一致P-函数非线性互补问题的宽邻域不可行内点算法及其计算复杂性

1引言与记号单调线性互补问题和线性规划问题的原始-对偶路径跟踪算法,1989年的文献[1、2]分别首先提出。以后又出现了一些改进的算法。早期的原始-对偶路径跟踪算法及其改进算法的迭代点列大都是在包含中心路径C的一个2-范数的窄邻域里,这种可行内点算法通常理论上具有最好的迭代复杂性O(n~(1/2)L),但是由于窄邻域极大地限制了迭代步长,实     

确定GF(pm)上周期为3n的序列线性复杂度的快速算法

设p是素数且3是p−1的因子, 证明了一个归约结果:有限域GF(p^m) (m是任意的正整数)上周期为3n (n与m互素)的序列的线性复杂度的计算可以简化成3个周期为n序列的线性复杂度的计算. 通过结合一些已知的算法如Games-Chan算法, Berlekamp-Massey算法,Xiao-Wei-Lam-Imamura算法, 可以更快速计算在GF (p^m)上任意周期为3n序列的线性复杂度.     

基于全牛顿步长求解凸二次规划问题的不可行内点算法

借助于全牛顿步长对凸二次规划问题提出了一种新的不可行内点算法.算法主要迭代由可行迭代步和中心路径邻域迭代步组成.其优点是线性搜寻方向是不需要的.最后证明算法迭代复杂性为O(nlogn/ε),与目前最好的不可行内点算法复杂性一致.     

一种新的求解凸二次规划的原始-对偶多项式内点算法

对凸二次规划问题提出了一种新的原始-对偶路径跟踪算法,算法迭代方向的求解是不同于传统的牛顿法,而是借助于一种新的工具找到搜寻方向.最后证明了算法具有多项式复杂性.     

基于全牛顿求解P*(κ)阵水平线性互补问题的内点算法

提出一种求解P_*(k)阵水平线性互补问题的全牛顿内点算法,全牛顿算法的优势在于每次迭代中不需要线性搜寻.当给定适当的中心路径邻域的阈值和更新势垒参数,证明算法中心邻域的全牛顿是局部二次收敛的,最后给出算法迭代复杂性O(√n)log(n+1+k)/εμ₀.     

行(或列)对称矩阵的QR分解

证明了行(或列)对称矩阵的Q矩阵和R矩阵与母矩阵的Q矩阵和R矩阵之间的定量关系, 给出了两种快速算法. 据此可大大降低一类具有该结构矩阵的QR分解的计算量和存储量.     

线性约束优化的信赖域仿射尺度算法

对线性约束优化问题提出一种信赖域仿射尺度算法，在没有非退化假设的条件下，证明了该算法产生的无限序列{x-k}的任一极限点都满足一阶必要条件，且至少存在一个极限点满足二阶必要条件.     

正交非均衡Procrustes问题的持续投影算法

研究正交约束下的Procrustes问题：给定矩阵A∈R^n×n, B∈ ^n×k, n>k, 找一个Q∈R^n×k}, 使得在列单位正交约束Q^TQ=I_k下, 残量‖AQ-B‖_F达到最小. 给出了求解该问题的持续投影算法, 该算法的每一次扫描由求解k个二次约束下的最小二乘问题以及一个扩充后的均衡Procrustes问题组成; 也给出了详细的收敛性分析. 文中的数值例子表明新的迭代算法优于已有的其他方法.     

一类P-函数非线性互补问题的宽邻域路径跟踪算法及其计算复杂性

对一致P-函数非线性互补问题,提出了一种新的宽邻域(N-∞(β))路径跟踪算法,并讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.     

非单调线性互补问题的高阶宽领域内点算法

本文研究了P(K)-阵线性互补问题宽邻域高阶内点算法.利用线性规划的原始-对偶仿射尺度算法来确定迭代方向,得到了算法的收敛性及迭代复杂性,其算法是有效可行的.     

P0函数非线性互补问题的非内部连续化算法

提出了一种新的光滑函数,它具有现存的一些光滑函数不具备的性质.基于此光滑函数,讨论了求解P₀函数非线性互补问题的光滑路径的存在性和连续性.在非线性互补问题的解集非空有界的假设下,利用新光滑函数的特性,研究了求解P₀函数非线性互补问题的非内部连续化算法得到的迭代序列的有界性.解集非空有界的条件弱于一些现存的求解非线性互补问题的连续化算法所要求的假设条件.     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .     

Fredholm算子扰动的零空间与退化同宿分岔

人们知道Fredholm 算子L的小扰动的零空间维数不大于L零空间的维数dimN(L). 证明了对任给正整数k≤dimN(L)存在一个L的扰动,它的零空间维数刚好是k. 我们的证明事实上给出了这个扰动的一个构造. 进而将所获得的结果应用到具有退化同宿轨的微分方程的具体例子, 指出有多少个独立的同宿轨可以从扰动中分岔出来.     

Tubular 代数与仿射Kac-Moody 代数

在Tubular代数A的退化合成Lie代数L(A)₁^C上构造商代数,证明商代数同构于对应的仿射Kac-Moody 代数.还证明了由单模生成的退化合成Lie代数L(A)₁^C与 由实根模生成的Lie代数 L_re(A)₁^C 是一致的.     

高次Koszul复形

推广了Koszul复形以及Koszul代数,引入了高次Koszul ( t -Koszul)复形和高次Koszul (t-Koszul)代数的概念, 其中t为不小于2的正整数. 证明了代数为高次Koszul代数当且仅当其相应的高次Koszul复形的高阶(≥1)同调群为0. 还通过引入t次对偶代数的概念, 对t-Koszul代数的上同调代数进行了具体的刻画, 证明了对任意的非负整数m, 其中L₀是L的所有单模的直和, 而L^!是L的t次对偶代数.     

关于半定规划的一种宽邻域不可行内点算法的注记

针对半定规划的宽邻域不可行内点算法, 将牛顿法和预估校正法进行结合, 构造出适当的迭代方向, 提出一个修正的半定规划宽邻域不可行内点算法, 并在适当的假设条件下, 证明了该算法具有O(\sqrt{n}L)的迭代复杂界．最后利用Matlab编程, 给出了基于KM方向和NT方向的数值实验结果．     

2×2 Hermite矩阵几何

设D是有对合a→的除环, 假设是D的真子域并且含在D的中心域中. 指出: 如果D的特征不等于2, 则D是F上可离二次扩域或者是F上广义四元数除环; 如果D的特征等于2, 则D是F上可离二次扩域, 因此迹映射Tr:D→F,恒为满射,从而已有的 Hermite矩阵几何的基本定理中关于D的假设(ii)可以删去. 万哲先已经证明了当D为域时2×2 Hermite矩阵几何的基本定理. 继续证明了当D为特征不等于2的广义四元数除环时,D上2×2 Hermite矩阵几何的基本定理.