关于一些凸规划问题的复杂性研究结果

目前,已发表了大量研究各类不同凸规划的低复杂度的障碍函数方法的文章. 利用自和谐理论,对不同的几类凸规划问题构造相应的对数障碍函数,通过两个引理证明这些凸规划问题相应的对数障碍函数都满足自和谐,根据Nesterov 和Nemirovsky的工作证明了所给问题的内点算法具有多项式复杂性.     

快速小波边界元的矩阵后压缩方法

介绍了一种基于传统边界元单元划分的小波 Galerkin 边界元法,该方法具有几乎线性(即 ON,N 为自由度)的求解复杂度。在准消失矩小波的框架下介绍了非标准型系数矩阵的压缩问题,提出了一种后压缩算法以降低小波边界元法的内存消耗。求解 Stokes 方程的算例表明,后压缩算法在保证结果收敛特性的情况下可以将系数矩阵的内存占用量降低 5 倍以上。     

Nonlinear stochastic interacting dynamics and complexity of financial gasket fractal-like lattice percolation

A novel nonlinear stochastic interacting price dynamics is proposed and investigated by the bond percolation on Sierpinski gasket fractal-like lattice, aim to make a new approach to reproduce and study the complexity dynamics of real security markets. Fractal-like lattices correspond to finite graphs with vertices and edges, which are similar to fractals, and Sierpinski gasket is a well-known example of fractals. Fractional ordinal array entropy and fractional ordinal array complexity are introduced to analyze the complexity behaviors of financial signals. To deeper comprehend the fluctuation characteristics of the stochastic price evolution, the complexity analysis of random logarithmic returns and volatility are preformed, including power-law distribution, fractional sample entropy and fractional ordinal array complexity. For further verifying the rationality and validity of the developed stochastic price evolution, the actual security market dataset are also studied with the same statistical methods for comparison. The empirical results show that this stochastic price dynamics can reconstruct complexity behaviors of the actual security markets to some extent.     

Interpreting non-random signatures in biomedical signals with Lempel-Ziv complexity

Lempel-Ziv complexity (LZ) [J. Ziv, A. Lempel, On the complexity of finite sequences, IEEE Trans. Inform. Theory 22 (1976) 75-81] and its variants have been used widely to identify non-random patterns in biomedical signals obtained across distinct physiological states. Non-random signatures of the complexity measure can occur under nonlinear deterministic as well as non-deterministic settings. Surrogate data testing have also been encouraged in the past in conjunction with complexity estimates to make a finer distinction between various classes of processes. In this brief letter, we make two important observations (1) Non-Gaussian noise at the dynamical level can elude existing surrogate algorithms namely: Phase-randomized surrogates (FT) amplitude-adjusted Fourier transform (AAFT) and iterated amplitude-adjusted Fourier transform (IAAFT). Thus any inference nonlinear determinism as an explanation for the non-randomness is incomplete (2) Decrease in complexity can be observed even across two linear processes with identical auto-correlation functions. The results are illustrated with a second-order auto-regressive process with Gaussian and non-Gaussian innovations. AR(2) processes have been used widely to model several physiological phenomena, hence their choice. The results presented encourage cautious interpretation of non-random signatures in experimental signals using complexity measures.     

Using the Renormalization Group to Classify Boolean Functions

This paper argues that the renormalization group technique used to characterize phase transitions in condensed matter systems can be used to classify Boolean functions. A renormalization group transformation is presented that maps an arbitrary Boolean function of N Boolean variables to one of N−1 variables. Applying this transformation to a generic Boolean function (one whose output for each input is chosen randomly and independently to be one or zero with equal probability) yields another generic Boolean function. Moreover, applying the transformation to some other functions known to be non-generic, such as Boolean functions that can be written as polynomials of degree ξ with ξ ≪ N and functions that depend on composite variables such as the arithmetic sum of the inputs, yields non-generic results. One can thus define different phases of Boolean functions as classes of functions with different types of behavior upon repeated application of the renormalization transformation. Possible relationships between different phases of Boolean functions and computational complexity classes studied in computer science are discussed.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

求分块鳞状因子循环矩阵逆矩阵的一种快速算法

给出了一种计算分块鳞状因子循环矩阵逆矩阵的快速算法,该算法主要利用了离散傅立叶变换和对角块矩阵求逆的递归算法,与标准的利用LU分解法求逆的算法相比,在计算复杂性上有很大的优势.     

组合优化若干经典问题新进展

组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支, 研究具有离散结构的优化问题解的性质和求解方法. 由于不同离散问题的结构差异, 出现了各种各样的研究手段和技巧. 针对组合优化的若干经典问题, 简述了算法和复杂性理论的研究进展.     

一种基于广义Duffing振子的水中弱目标检测方法

海洋环境中,在水下目标的线谱频率未知或者目标辐射噪声的连续谱很弱时,很难实现水中弱目标的准确检测,本文提出基于广义Duffing振子检测系统的水下目标辐射噪声检测方法.通过对传统周期扰动的Duffing振子信号检测系统的分析和推广,提出了一种可输入非周期、非平稳信号的广义Duffing振子检测系统,可检测输入的无先验信息目标信号.为实现广义Duffing振子系统运动状态的精确、有效判断,提出了一种相空间图形的离散分布列计算方法,通过类网格函数实现了利用统计复杂度对系统输出的嵌入式表征,从而实现了无先验信息时的水中弱目标的嵌入式检测.相同条件下与传统检测方法仿真对比可知,本文提出的方法可以检测到更低信噪比下的目标,并能满足水中检测实时性要求.     

线性规划的σj迭代计算方法

本提出并证明了求解线性规划（LP）的单纯形法中检验数（σj）的迭代计算方法的定理，由此定理得到的迭代计算方法比传统的按定义式计算法的渐近时间复杂度降了一级，同时简化了计算过程并提高了计算效率。