数学家货郎问题的计算复杂性研究

货郎问题(TSP)是研究计算复杂性理论的经典问题.在货郎问题的基础上,提出"数学家货郎问题"(MTSP).经过研究发现,数学家货郎问题是一个典型的NP类问题,但它却不属于P类问题.因此,数学家货郎问题是一个NP类问题与P类问题不相等的例证.     

一种基于谱聚类分析的粒子群聚类算法

本文研究了谱聚类中NJW算法的样本最优划分问题.利用粒子群算法在聚类问题上搜索到的全局最优,获得了NJW算法对聚类样本的最优划分.推广了谱聚类算法在样本划分时的普适性和稳定性.实验对比验证该算法是有效的.     

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.     

无穷维Hilbert空间上框架的算子与范数

在框架理论研究中,哪类可逆算子能使得某些框架性质保持不变这个问题是基本和重要的,本文在无穷维Hilbert空间上对下述两个问题进行研究.问题1:哪类可逆算子能使得框架算子保持不变;问题2:哪类可逆算子能使得框架范数只相差一列常数.本文从抽象的算子理论和具体的构造方法两方面对问题1给出解答.利用框架的相容算子的概念,当把问题2中的可逆算子集换成一类较小的算子集时,得到了问题2的回答.     

一种新的聚类分析方法——自然聚类法

确定分类数成为聚类分析中的主要问题之一.针对该问题,文章提出了一种新的聚类分析方法即自然聚类法.首先,给出了一个新的类的定义.按该定义聚类,类和类的个数是确定的.相应地,设计了自然聚类的算法.最后通过模拟研究和两个实例分析了所提出方法的有效性.     

论有限群元素共轭类的平均长度

本文研究有限群元素共轭类的平均长度问题.利用初等群论方法和有限群特征标理论,在共轭类平均长度为某一定数时,获得了对有限群结构的刻划,且对有限群数量性质的研究是有意义的.     

k-平均问题及其变形的算法综述

k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.     

谱变形的非线性双曲型方程

文[1]研究了一个非线性双曲型方程 u_(xt) [(uu_xu_t)/(1-u~2)]-u(1-u~2)=0.方程(*)可以用来描述沿类脂膜扩张波的传播,它所对应的特征值问题的谱是不变的,随着科技的发展,非均匀介质中的传播问题日益受到重视。类问题相应的特征值问题是非保谱的,因此,在[2]中研究了谱变形的特征值问题和发展方程.这本文研究谱变形的非线性双曲型方程     

关于矩阵的复符号模式类的行列式值域的一个猜想

研究矩阵的复符号模式类的行列式值域是与复符号非异阵的刻画有关的一个问题.文中部分解决了邵嘉裕先生等人提出的一个猜想.     

参数优化的最优性及在控制问题中的一个应用

在Banach空间中,给出了含参数的单值映射的不变类凸,拟不变类凸和伪不变类凸的概念.在这类较弱凸性条件下,提出了参数优化问题弱有效解的几个最优性充分条件.作为应用,研究了一类状态约束最优控制问题的弱最优控制.     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

Tractability through increasing smoothness

We prove that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. This is demonstrated for the approximation problem defined over Korobov spaces and for the approximation problem of certain diagonal operators. For these two problems we show necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability. We prove that polynomial tractability is equivalent to strong polynomial tractability, and that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces of non-periodic functions with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending on the choice of the norm we can even lose weak tractability.     

Tractability of linear problems defined over Hilbert spaces

We study d$d$-variate approximation problems in the worst and average case settings. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. In the worst case setting, we obtain necessary and sufficient conditions for quasi-polynomial tractability and uniform weak tractability. Furthermore, we give an estimate of the exponent of quasi-polynomial tractability which cannot be improved in general. In the average case setting, we obtain necessary and sufficient conditions for uniform weak tractability. As applications we discuss some examples.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

Quasi-polynomial tractability of linear problems in the average case setting

We study d$d$-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For the absolute error criterion, we obtain the necessary and sufficient conditions in terms of the eigenvalues of its covariance operator and obtain an estimate of the exponent t^qpol-avg$t^{\text{qpol-avg}}$ of quasi-polynomial tractability which cannot be improved in general. For the linear tensor product problems, we find that the quasi-polynomial tractability is equivalent to the strong polynomial tractability. For the normalized error criterion, we solve a problem related to the Korobov kernels, which is left open in Lifshits et al. (2012).     

Integration and Approximation Based on Scramble Sampling in Arbitrary Dimensions

This paper considers integration in the worst case setting and approximation in the average case setting based on the scramble sampling scheme proposed by A. B. Owen (1995, Lecture Notes in Statistics, Vol. 106, pp. 299–317, Springer-Verlag, New York.) The tractability and strong tractability exponents are found for function spaces with reproducing/covariance kernels that are scramble-invariant. Integration and approximation for a space with a non-scramble-invariant kernel are no harder than the corresponding problems with the associated scramble-invariant kernel. This enables us to derive tractability results for weighted Sobolev spaces.     

Worst case tractability of linear problems in the presence of noise: Linear information

We study the worst case tractability of multivariate linear problems defined on separable Hilbert spaces. Information about a problem instance consists of noisy evaluations of arbitrary bounded linear functionals, where the noise is either deterministic or random. The cost of a single evaluation depends on its precision and is controlled by a cost function. We establish mutual interactions between tractability of a problem with noisy information, the cost function, and tractability of the same problem, but with exact information.     

Tractability and Strong Tractability of Linear Multivariate Problems

Linear multivariate problems are defined as the approximation of linear operators on functions of d variables. We study the complexity of computing an ϵ-approximation in different settings. We are particularly interested in large d and/or large ϵ⁻¹. Tractability means that the complexity is bounded by c(d) K(d, ϵ), where c(d) is the cost of one information operation and K(d, ϵ) is a polynomial in d and/or in ϵ⁻¹. Strong tractability means that K(d, ϵ) is a polynomial in ϵ⁻¹, independent of d. We provide necessary and sufficient conditions for linear multivariate problems to be tractable or strongly tractable in the worst case, average case, randomized, and probabilistic settings. This is done for the class Λ^all where an information operation is defined as the computation of any continuous linear functional. We also consider the class Λ^std where an information operation is defined as the computation of a function value. We show under mild assumptions that tractability in the class Λ^all is equivalent to tractability in the class Λ^std. The proof is, however, not constructive. Finally, we consider linear multivariate problems over reproducing kernel Hilbert spaces, showing that such problems are strongly tractable even in the worst case setting.     

Tractability of Integration in Non-periodic and Periodic Weighted Tensor Product Hilbert Spaces

We study strong tractability and tractability of multivariate integration in the worst case setting. This problem is considered in weighted tensor product reproducing kernel Hilbert spaces. We analyze three variants of the classical Sobolev space of non-periodic and periodic functions whose first mixed derivatives are square integrable. We obtain necessary and sufficient conditions on strong tractability and tractability in terms of the weights of the spaces. For the three Sobolev spaces periodicity has no significant effect on strong tractability and tractability. In contrast, for general reproducing kernel Hilbert spaces anything can happen: we may have strong tractability or tractability for the non-periodic case and intractability for the periodic one, or vice versa.