优化算法的复杂度分析

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

基于规范高阶累积量的盲分离算法

本文给出信号的r阶规范累积量定义,证明了在信号瞬时线性混叠情况下r阶规范累积量绝对值不超过最大源信号的r阶规范累积量,因此可以通过最大化r阶规范累积量的绝对值实现盲分离.最大化r阶规范累积量的绝对值可以得到两种盲分离算法,一种高效快速算法———特征值分解盲分离算法,另外一种盲提取算法.本文为高阶累积量盲分离奠定了严格的理论基础.仿真结果验证了理论的正确性和算法的有效性.     

顶点加权最大团问题的加权分治算法

分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656~np(n)),其中n代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656~np(n))降为O(1.3765~np(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度.     

含参数的七阶收敛Steffensen迭代算法

为了解决迭代过程中非线性函数不能求导或者计算导数增加计算复杂度的问题,利用中心差分方法近似逼近一阶导数,构造了一种新的含有参数的Steffensen型迭代算法,且收敛性分析证明它至少是七阶收敛的.最后,数值实验验证了新算法的可行性和优越性.     

等距丢失模型下的框架张量积重构方法

框架理论常应用于信号重构.当编码系数在传输过程中发生等距丢失时,基于框架张量积的一些性质,我们可以利用框架张量积对信号进行编码从而降低数据丢失对重构信号的影响.本文由此提出了一种等距丢失模型,并在此模型下,研究了数据等距丢失下的最优对偶框架张量积,得出了对偶框架和正则对偶框架的张量积是最优对偶框架张量积的两个充分必要条件.最后数值实验也说明了：在等距丢失模型下,最优对偶框架张量积比一般对偶框架张量积的信号重构结果更优.     

基于近似一阶信息的加速的bundle level算法

本文提出了四种加速的BL(bundle level)算法来分别求解凸光滑函数、强凸光滑函数的极小值问题和一类鞍点(saddle-point)问题.这些算法可以运用目标函数的近似的一阶信息来得到上述几类问题的近似解.本文重点研究了在一阶信息误差上界可自由选取和给定不变的两种情形下,所提出的算法中近似解能达到的最佳精度以及相应的迭代复杂度.     

关于矩阵乘法的一个改进算法的时间复杂度

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

精确覆盖问题的加权分治算法

精确覆盖问题是组合优化中经典的NP-Hard问题之一,其在诸多领域具有广泛的应用价值。本文首先研究了精确覆盖问题的数学性质,并根据数学性质提出相应的分支降阶规则以缩小问题的规模;接着设计了一个基于分支降阶的回溯算法求解该问题;然后运用常规技术分析得出该精确算法的时间复杂度为O(1.4656^k);最后运用加权分治技术对该算法的时间复杂度进行分析,将该算法的时间复杂度降为O(1.3842^k)。文章最后通过一个示例进一步阐述该算法的原理,并与其他精确算法进行了对比分析,研究结果表明该算法是可行的,也是有效的。     

基于分数间隔的四二阶归一化累积量盲均衡算法

针对目前分数间隔盲均衡算法存在的缺陷,提出了基于分数间隔的四二阶归一化累积量盲均衡算法.先对接收信号进行分数间隔采样,然后利用四二阶归一化累积量将盲均衡算法归结为无约束的极值问题,从而简化了算法,加快了收敛速度,降低了误码率.仿真验证了算法的有效性.     

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。     

噪声干扰下m~2OLS算法的稀疏重构分析

修正的多重正交最小二乘(modified multiple orthogonal least squares,m~2OLS)算法是在多重正交最小二乘算法(multiple orthogonal least squares,m OLS)的基础上提出的.利用m~2OLS算法能够从模型y=Ax+v中重构稀疏信号x.借助预选取规则,m~2OLS算法的复杂度低于m OLS.在三类噪声干扰下,本文给出保证m~2OLS算法每次迭代至少选取一个正确指标的充分条件.该条件是在约束等距性质(restricted isometry property,RIP)框架下给出的.在第一次迭代中,本文给出m~2OLS算法不能选取正确指标的条件.与现有的结果相比,本文中的结果具有一定优势.     

基于Spectral Tetris算法的框架的最佳稀疏性

当信号维数较大时,使用稀疏框架分解信号就能减少大量的加法和乘法运算,所以,研究稀疏框架很有意义.本文介绍有限框架的稀疏性,并研究基于Spectral Tetris算法构造的框架的稀疏性.首先,给出基于Spectral Tetris算法的框架的最佳稀疏性;其次,得到基于Spectral Tetris算法的可剖分紧框架的最佳稀疏性.     

高维带宽有限随机信号从平均过采样的指数阶逼近

本文中我们主要考虑利用有限的平均过采样值来重构高维带宽有限随机信号.我们给出了一个能够达到指数阶衰减逼近能力的重构算法.对于一般型和乘积型的采样测度,我们分别给出了对应的重构算法和指数阶衰减的重构误差估计.     

基于语言真值格值一阶逻辑系统Lv(n×2)F(X)中两种模型的不确定性推理

在语言真值格值一阶逻辑系统的框架下,讨论了两种推理模型中的不确定性推理理论与方法,并针对不同的推理规则得到了推理算法,其推理算法既有合理的语义解释又有严密的语法论证.     

充电站选址问题的降阶回溯算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-难问题.文章首先研究了该问题良好的数学性质并给予相应的证明,其中包括可以批量确定某些设施一定开设或一定不开设的性质,利用这些性质降低问题的规模,从而降低问题的求解难度;然后设计了上界子算法,下界子算法,分配子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解一个示例来进一步阐述文章算法的原理和执行过程,结果表明所提出的算法能够有效地降低时间复杂度.     

关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

高精度特征解及其外推求解位势方程

根据位势理论,基本边界特征值问题可转化为具有对数奇性的边界积分方程.利用机械求积方法求解特征值和特征向量,以及利用这些特征解求解Laplace方程.特征解和Laplace方程的解具有高精度和低的计算复杂度.利用Anselone聚紧和渐近紧理论,证明了方法的收敛性和稳定性.此外,还给出了误差的奇数阶渐近展开.利用h3-Richardson外推,不仅误差近似的精度阶大为提高,而且,得到的后验误差估计可以构造自适应算法.具体的数值例子说明了算法的有效性.     

周期pq的广义分圆二元序列线性复杂度（英文）

本文构造了一类周期为pq(p和q是不同的奇素数)的几乎平衡的二元序列,基于4阶Whiteman-广义分圆和2阶经典分圆我们确定了这类序列的线性复杂度.研究结果表明该类序列从线性复杂度的角度来看是非常好的.     

多输入多输出时间信号传输系统的优化

通讯网络系统是多回路复杂系统.文章研究多输入多输出时间信号传输网络系统的优化问题.首先建立多输入多输出时间信号传输网络系统模型,把信号发射器发射信号时间、信号传输时间和信号接收器运行时间之间的关联表示为极大-加线性方程系统,从而将信号传输网络系统的优化问题转化为极大-加线性方程系统的可解性问题.然后引入极大-加线性方程系统的可解元概念,给出极大-加线性方程系统唯一可解的一个充分必要条件,提出解决优化问题的一个多项式算法,并提供数值例子.     

基于分数阶Fourier变换的结构瞬时频率识别北大核心CSCD

为识别时变信号的瞬时频率,由分数阶Fourier变换定义推导出了一般信号的频率与单一变量旋转角度α的关系式,从理论上解释了分数阶Fourier变换本质上是一种普通Fourier变换结合伸缩平移窗的算法,进而在分数阶Fourier域建立了非平稳信号瞬时频率的一般表达式,实现了结构瞬时频率的识别.采用任意非线性调频信号仿真算例和三自由度有阻尼时变结构系统的数值算例对提出的方法进行了比较分析.结果表明,该文提出的方法与理论值吻合良好,并具有一定的抗噪性,验证了方法的可靠性和实用性,可以应用于时变结构瞬时频率的识别.